Choose your own path
면접 대비시간 제한2초메모리 제한512 MB
1번 페이지에서 시작하는 이야기 페이지의 방향 그래프가 주어질 때, 모든 페이지에 도달할 수 있는지 확인하고 결말 페이지까지의 최단 거리를 구한다.
문제
선택에 따라 이야기가 달라지는 소설 장르가 있다. 이런 책에서는 독자가 등장인물 대신 선택을 하면서 이야기의 결말이 달라진다.
예를 들어 책의 첫 페이지를 읽고 나면 "돌을 주울 것인가?"와 같은 선택을 요구받을 수 있다. 독자가 "예"라고 답하면 47페이지에서 계속 읽으라고 안내하고, "아니요"를 고르면 18페이지에서 계속 읽으라고 안내한다. 그 각각의 페이지에서도 다시 선택이 이어지고, 이런 식으로 책 전체가 구성된다. 어떤 페이지에는 선택이 없으며, 그런 페이지가 그 이야기 버전의 "결말" 페이지가 된다. 책에는 이런 결말 페이지가 여러 개 있을 수 있고, 어떤 것은 좋은 결말이며(예: 주인공이 보물을 찾는다), 어떤 것은 그렇지 않다(예: 주인공이 2001년에 남은 샌드위치를 찾는다).
당신은 이런 책의 편집자이고, 다음 두 가지를 살펴봐야 한다.
- 모든 페이지에 도달할 수 있는지 확인한다. 아무도 읽을 수 없는 페이지를 인쇄하는 데 돈을 쓸 이유는 없다.
- 가장 짧은 경로를 찾는다. 독자가 이야기 한 버전을 끝내는 데 걸리는 최소 시간을 알아야 하기 때문이다.
책의 설명이 주어졌을 때, 이 두 가지를 살펴보자.
입력
첫째 줄에는 책의 페이지 수 N(1 ≤ N ≤ 10000)이 주어진다. 그다음 N개의 줄 각각에는 i번 페이지에서 나가는 선택의 수 Mi(1 ≤ i ≤ N; 0 ≤ Mi ≤ N)가 주어지고, 이어서 i번 페이지에서 다음으로 갈 수 있는 페이지에 해당하는 1부터 N까지 범위의 정수 Mi개가 공백으로 구분되어 주어진다. M1 + M2 + ... + MN은 10000 이하이다.
Mi = 0이면 i번 페이지는 결말 페이지이다. 즉, 그 페이지에서는 선택이 없다. 책에는 결말 페이지가 적어도 하나 있다.
책은 항상 1번 페이지에서 시작한다.
배점 15점 중 4점에 대해 N ≤ 100, 1 ≤ i ≤ N인 모든 i에 대해 Mi ≤ 10이다.
추가로 3점에 대해 책에 사이클이 없음이 보장된다.
추가로 4점에 대해 N ≤ 1000, 1 ≤ i ≤ N인 모든 i에 대해 Mi ≤ 25이다.
출력
출력은 두 줄이다. 첫째 줄에는 모든 페이지에 도달할 수 있으면 Y, 그렇지 않으면 N을 출력한다.
마지막 줄에는 독자가 이 책을 읽으면서 지날 수 있는 가장 짧은 경로의 길이인 음이 아닌 정수 K를 출력한다. 유한한 최단 경로가 항상 존재한다.