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$)．
• 入力される値はすべて整数である．