28022번 - Teleporter 서브태스크다국어

JOI 研究所には部屋が $N$ 部屋あり，各部屋には $1$ から $N$ までの番号が付けられている．これらの部屋の うち，部屋 $1$，部屋 $2$，. . . ，部屋 $N - 1$ にはいくつかのテレポーターが置かれている． 部屋 $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}$ となる場合もあることに注意せよ．

JOI 研究所の職員であるビ太郎とビバ子は，これらの部屋とテレポーターを使ってゲームを行う．ゲーム は以下のように進行する．

1. ビ太郎はゲーム開始時，部屋 $1$ にいる．
2. ラウンドが繰り返し行われる．それぞれのラウンドは以下のように進行する．
   1. 現在，ビ太郎が部屋 $x$ にいるとする．ビ太郎は部屋 $x$ に置かれている $A_x$ 個のテレポーターのう ちの $1$ つを選ぶ．
   2. ビ太郎が部屋 $x$ の $y$ 番目のテレポーターを選んだとする．ビバ子はそのテレポーターの行き先 を部屋 $P_{x,y}$ または部屋 $Q_{x,y}$ に設定する．どちらを選ぶかはラウンドごとに異なっていてもよい．
   3. ビ太郎が部屋 $x$ の $y$ 番目のテレポーターを利用する．ビ太郎はビバ子によって選ばれた行き先 （部屋 $P_{x,y}$ または部屋 $Q_{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}$

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

$\vdots$

$P_{2,A_2}$ $Q_{2,A_2}$

$\vdots$

$\vdots$

$A_{N-1}$

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

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

$\vdots$

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

標準出力に，両者が最善を尽くしたとき何ラウンド目にゲームが終了するかを $1$ 行で出力せよ．ただし， $10^{100}$ ラウンド目にゲームが終了する場合は，代わりに -1 を出力せよ．

• $2 ≦ N ≦ 200\,000$．
• $A_i ≧ 1$ ($1 ≦ i ≦ N - 1$)．
• $A_1 + A_2 + \cdots + A_{N-1} ≦ 200\,000$．
• $1 ≦ P_{i, j} ≦ N$ ($1 ≦ i ≦ N - 1$, $1 ≦ j ≦ A_i$)．
• $1 ≦ Q_{i, j} ≦ N$ ($1 ≦ i ≦ N - 1$, $1 ≦ j ≦ A_i$)．
• 入力される値はすべて整数である．