Informatica Online Judge

  게임북 [2207 / 089F]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 21   Total Tried : 22


The Champion of this Problem (C++) : gs17003 - 0ms / 762byte
My Best Submission (C++) : N/A

[CCC 2018 Junior]

Background

게임북이라는 종류의 책이 있다.

책을 읽어가는 도중 어떤 순간에 선택할 수 있는 것이 주어지고, 그것들 중에서 선택함에 따라 다른 페이지로 이동하면서 다른 이야기로 전개되는 종류의 책이다.


예를 들어, 게임북의 첫 페이지에서 이야기가 쓰여 있고, 그 다음에 “이 돌을 집어들겠습니까? 아니면 그대로 두겠습니까?”라는 질문에서 “돌을 집어들면 47페이지로 이동”, “돌을 그대로 두면 18페이지로 이동” 과 같이 쓰여 있으며, 그렇게 계속 선택이 주어지고 그 선택에 따라 페이지를 바꿔 이동하게 된다.


어떤 페이지들은 그러한 선택이 주어지지 않는데, 그러한 페이지들은 이야기의 마지막이 나와 있는 엔딩 페이지이다. 엔딩은 여러 가지가 있을 수 있다. 어떤 경우는 “영웅이 보물을 찾았습니다”와 같은 좋은 결말이고, 어떤 경우는 “영웅은 2001년에 버려진 샌드위치를 발견했습니다.”와 같은 결말이 되기도 한다.


이러한 게임북이 있을 때 다음과 같은 속성을 확인해야한다.

- 모든 페이지에 도달할 수 있는지 확인해야 한다. 그렇지 않으면 그 페이지는 인쇄할 필요가 없기 때문이다.

- 가장 짧게 이야기가 끝나는 페이지 이동 횟수를 알아내야 한다. 읽는 사람들이 어떤 이야기로 결말이 끝낼 때까지의 최소 시간을 알고 싶어 할 수 있기 때문이다.

게임북에 대한 데이터가 주어질 때, 위의 2가지 속성을 확인해보자.

Input

첫 번째 줄에는 게임북의 전체 페이지수(N)가 입력된다.
그 다음 N개의 줄에 걸쳐 각 i번째 페이지에서 주어지는 선택의 개수(Mi)와 그 선택에 따라 이동해야하는 페이지들의 번호가 순서대로 공백을 두고 입력된다.

어떤 페이지에서의 선택 개수(Mi)가 0이면, 그 페이지는 엔딩 페이지이고, 게임북에 적어도 1개 이상 있다.

게임북은 1페이지에서 시작하고, 선택에 따라 페이지를 이동하면 순환할 수도 있다.

[입력값의 정의역]

1<=N<=10000
1<=i<=N
0<=Mi<=N

Output

첫 번째 줄에는 모든 페이지에 접근이 가능하면 Y를 출력하고, 아니면 N을 출력한다.
두 번째 줄에는 게임북을 가장 빨리 끝낼 수 있는 페이지 이동 횟수를 출력한다.

IO Example

입력 예시1
3
2 2 3
0
0

출력 예시1
Y
2

입력 예시2
3
2 2 3
0
1 1

출력 예시2
Y
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]