Teleporter

JOI 연구소에는 $N$개의 방이 있고, 각 방에는 1부터 $N$까지 번호가 붙어 있다. 방 $1$, 방 $2$, $\ldots$, 방 $N-1$에는 텔레포터가 여러 개 놓여 있다. 방 $i$ ($1 \le i \le N-1$)에는 $A_i$개의 텔레포터가 있다. 방 $i$의 $j$번째 ($1 \le j \le A_i$) 텔레포터의 행き先은 방 $P_{i,j}$ 또는 방 $Q_{i,j}$ 중 하나로 설정할 수 있다. 단, $P_{i,j} = Q_{i,j}$인 경우도 있다.

JOI 연구소 직원인 비타로와 비바코는 이 방들과 텔레포터를 사용해 게임을 한다. 게임은 다음과 같이 진행된다.

1. 비타로는 게임 시작 시 방 $1$에 있다.

2. 라운드가 반복된다. 각 라운드는 다음과 같이 진행된다.

   1. 비타로가 방 $x$에 있다고 하자. 비타로는 방 $x$에 있는 $A_x$개의 텔레포터 중 하나를 고른다.
   2. 비타로가 방 $x$의 $y$번째 텔레포터를 골랐다고 하자. 비바코는 그 텔레포터의 행き先을 방 $P_{x,y}$ 또는 방 $Q_{x,y}$로 설정한다. 라운드마다 다른 쪽을 고를 수 있다.
   3. 비타로가 방 $x$의 $y$번째 텔레포터를 이용한다. 비타로는 비바코가 고른 행き先으로 이동한다.
   4. 비타로가 방 $N$으로 이동하면, 또는 이 라운드가 $10^{100}$번째 라운드이면 게임이 끝난다.

이 게임에서 비타로의 목표는 게임이 끝날 때까지의 라운드 수를 최대한 적게 만드는 것이다. 비바코의 목표는 라운드 수를 최대한 많게 만드는 것이다.

JOI 연구소의 정보가 주어졌을 때, 두 사람이 최선을 다했을 때 몇 번째 라운드에 게임이 끝나는지 구하는 프로그램을 작성하라.

입력은 다음 형식으로 표준 입력에서 주어진다.

$N$

$A_1$

$P_{1,1}$ $Q_{1,1}$

$P_{1,2}$ $Q_{1,2}$

$\vdots$

$P_{1,A_1}$ $Q_{1,A_1}$

$A_2$

$P_{2,1}$ $Q_{2,1}$

$\vdots$

$A_{N-1}$

$P_{N-1,1}$ $Q_{N-1,1}$

$\vdots$

$P_{N-1,A_{N-1}}$ $Q_{N-1,A_{N-1}}$

두 사람이 최선을 다했을 때 몇 번째 라운드에 게임이 끝나는지 한 줄에 출력하라. 단, $10^{100}$번째 라운드에 게임이 끝나는 경우에는 대신 $-1$을 출력하라.

• $2 \le N \le 200\,000$.
• $A_i \ge 1$ ($1 \le i \le N-1$).
• $A_1 + A_2 + \cdots + A_{N-1} \le 200\,000$.
• $1 \le P_{i,j} \le N$ ($1 \le i \le N-1$, $1 \le j \le A_i$).
• $1 \le Q_{i,j} \le N$ ($1 \le i \le N-1$, $1 \le j \le A_i$).
• 입력되는 값은 모두 정수이다.