정보 연구소에는 방이 N개 있으며, 각 방에는 1부터 N까지의 번호가 붙어 있다.

이들 방 중, 방 i (1 ≤ i ≤ N-1)에는 A_i개의 텔레포터가 배치되어 있다. 방 i의 j번째 (1 ≤ j ≤ A_i) 텔레포터의 행선지는 방 P_{i, j} 또는 방 Q_{i, j} 중 하나로 설정할 수 있다.

단, P_{i, j}와 Q_{i, j}가 같은 경우도 있다는 점에 유의하라.

정보 연구소의 직원인 정올이와 한글이는, 이들 방과 텔레포터를 사용하여 게임을 진행한다. 게임은 다음과 같이 진행된다.

정올이는 게임 시작 시, 방 1에 있다.
라운드가 반복해서 진행된다. 각각의 라운드는 다음과 같이 진행된다.
- 현재, 정올이가 방 x에 있다고 하자. 정올이는 방 x에 배치된 A_x개의 텔레포터 중 하나를 선택한다.
- 정올이가 방 x의 y번째 텔레포터를 선택했다고 하자. 한글이는 그 텔레포터의 행선지를 방 P_{x, y} 또는 방 Q_{x, y} 중 하나로 설정한다. 어느 쪽을 선택할지는 라운드마다 달라도 된다.
- 정올이는 방 x의 y번째 텔레포터를 이용한다. 정올이는 한글이에 의해 선택된 행선지(방 P_{x, y} 또는 방 Q_{x, y} 중 하나)로 이동한다.
- 정올이가 방 N으로 이동한 경우, 또는 이 라운드가 10^{100}라운드인 경우, 게임이 종료된다.

정올이의 목적은 게임이 종료되기까지 진행되는 라운드 수를 최대한 적게 하는 것이며, 반면 한글이의 목적은 게임이 종료되기까지 진행되는 라운드 수를 최대한 많게 하는 것이다.

정보 연구소의 정보가 주어졌을 때, 양쪽이 최선을 다했을 경우 몇 라운드에서 게임이 종료되는지를 구하는 프로그램을 작성하라.

텔레포터 timer 2s memory 1024MB

텔레포터 2s 1024MB