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

서브태스크

힌트