Problem E: CCC18J5 Choose your own path

Problem E: CCC18J5 Choose your own path

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 37  Solved: 3
[Submit] [Status] [Web Board] [Creator:]

Description

English:
There is a genre of fiction called choose your own adventure books. These books allow the reader to make choices for the characters which alters the outcome of the story. For example, after reading the first page of a book, the reader may be asked a choice, such as “Do you pick up the rock?” If the reader answers “yes”, they are directed to continue reading on page 47, and if they choose “no”, they are directed to continue reading on page 18. On each of those pages, they have further choices, and so on, throughout the book. Some pages do not have any choices, and thus these are the “ending” pages of that version of the story. There may be many such ending pages in the book, some of which are good (e.g., the hero finds treasure) and others which are not (e.g., the hero finds a leftover sandwich from 2001). You are the editor of one of these books, and you must examine two features of the choose your own adventure book:   


1. ensure that every page can be reached – otherwise, there is no reason to pay to print a page which no one can ever read;  
 
2. find the shortest path, so that readers will know what the shortest amount of time they need to finish one version of the story.    
 
Given a description of the book, examine these two features.


Chinese:
有一种小说类型叫做“选择自己的冒险书”。这些书使读者可以选择能够改变故事结局的人物。例如,阅读完本书的第一页后,可能会要求读者选择,例如“您捡起石头了吗?”如果读者回答“是”,则指示他们继续阅读第47页,如果选择“否”,则指示他们继续阅读第18页。在这些页面的每一个上,他们还有更多选择,依此类推。 整本书中。有些页面没有任何选择,因此这些是该故事版本的“结尾”页面。书中可能有许多这样的结尾页面,其中有些很好(例如,英雄发现了宝藏),而有些则没有了(例如,英雄发现了2001年的剩饭三明治)。您是其中一本书的编辑,您必须检查选择自己的冒险书的两个功能:

1.确保可以到达每一页–否则,没有理由支付打印任何人都无法阅读的页面的费用; 

2.找到最短的路径,以便读者知道完成故事的一个版本所需的最短时间。

给了本书的描述,请检查这两个功能。

Input

The first line of input contains N (1 ≤ N ≤ 10000), the number of pages in the book. Each of the next N lines contain an integer Mi (1 ≤ i ≤ N; 0 ≤ Mi ≤ N), which is the number of different options from page i, followed by Mi space-separated integers in the range from 1 to N, corresponding to each of the pages to go to next from page i. It will also be the case M+ M2 + · · · + Mn is at most 10000. 
If Mi = 0, then page i is an ending page (i.e., there are no choices from that page). There will be at least one ending page in the book. 
Note that you always begin the book on page 1. 
For 4 of the available 15 marks, N ≤ 100, M≤ 10 for 1 ≤ i ≤ N. 
For an additional 3 of the available 15 marks, the book is guaranteed to have no cycles. 
For an additional 4 of the available 15 marks, N ≤ 1000, M≤ 25 for 1 ≤ i ≤ N.


输入的第一行包含N(1≤N≤10000),即书中的页数。 接下来的N行中的每行都包含一个整数Mi(1≤i≤N; 0≤Mi≤N),是第i页上不同选项的数目,后跟Mi分隔的整数,范围从1到N, 对应于要从页面i转到下一页的每个页面。 M1 + M2 +··+ + Mn最多为10000。
如果Mi = 0,则第i页是结束页(即该页面没有选择)。 书中至少会有一页结尾。
请注意,您总是从第1页开始。


对于27%的测试数据,N≤100,1≤i≤N的Mi≤10。
对于额外20%的测试数据,保证该书没有周期。
对于另外27%的测试数据,N≤1000,Mi≤25表示1≤i≤N.

Output

The output will be two lines. The first line will contain Y if all pages are reachable, and N otherwise.

The last line will contain a non-negative integer K, which is the shortest path a reader can take while reading this book. There will always be a finite shortest path.



输出将是两行。 如果所有页面均可访问,第一行将包含Y,否则将包含N。
最后一行将包含一个非负整数K,这是读者阅读本书时可以采用的最短路径。 总会有一条最短的有限路径。

Sample Input Copy

Sample Input 1:
3
2 2 3
0
0

Sample Input 2:
3
2 2 3
0
1 1

Sample Output Copy

Sample Output 1:
Y
2

Sample Output 2:
Y
2

HINT

Explanation for Sample Output 1

Since we start on page 11, and can reach both page 22 and page 33, all pages are reachable. The only paths in the book are 1→21→2 and 1→31→3, each of which is 22 pages in length. 

Explanation for Sample Output 2

Every page is reachable, since from page 11, we can reach pages 22 and 33. The shortest path is the path 1→21→2, which contains two pages. 



样例输出1说明
因为我们从第11页开始,并且可以同时到达第22页和第33页,所以所有页面都可以访问。 本书中唯一的路径是1→21→2和1→31→3,每个路径长22页。

样例输出2说明
每个页面都是可访问的,因为从页面11开始,我们可以访问页面22和33。最短路径是路径1→21→2,其中包含两个页面。