B - テレポーター (Teleporter) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

JOI 研究所には部屋が N 部屋あり,各部屋には 1 から N までの番号が付けられている.これらの部屋のうち,部屋 1,部屋 2,\ldots,部屋 N - 1 にはいくつかのテレポーターが置かれている.部屋 i (1 \leqq i \leqq N - 1) には A_{i} 個のテレポーターが置かれている.部屋 i の j 番目 (1 \leqq j \leqq 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 \leqq N \leqq 200\,000.
  • A_{i} \geqq 1 (1 \leqq i \leqq N - 1).
  • A_{1} + A_{2} + \cdots + A_{N - 1} \leqq 200\,000.
  • 1 \leqq P_{i,j} \leqq N (1 \leqq i \leqq N - 1,1 \leqq j \leqq A_{i}).
  • 1 \leqq Q_{i,j} \leqq N (1 \leqq i \leqq N - 1,1 \leqq j \leqq A_{i}).
  • 入力される値はすべて整数である.

小課題

  1. (13 点) P_{i,j} = Q_{i,j} (1 \leqq i \leqq N - 1,1 \leqq j \leqq A_{i}).
  2. (19 点) P_{i,j} > i,Q_{i,j} > i (1 \leqq i \leqq N - 1,1 \leqq j \leqq A_{i}).
  3. (22 点) N \leqq 2\,000,A_{1} + A_{2} + \cdots + A_{N - 1} \leqq 2\,000.
  4. (30 点) A_{i} = 1 (1 \leqq i \leqq N - 1).
  5. (16 点) 追加の制約はない.

入力例 1

3
2
2 2
3 2
1
3 3

出力例 1

2

両者が最善を尽くしたとき,例えば以下のようにゲームは進行する.

  • 最初,ビ太郎は部屋 1 にいる.
  • 1 回目のラウンドは以下のように進行する.
    • ビ太郎は部屋 1 の 2 番目のテレポーターを選ぶ.このテレポーターの行き先は部屋 3 または部屋 2 に設定できる.
    • ビバ子は部屋 1 の 2 番目のテレポーターの行き先を部屋 2 に設定する.
    • ビ太郎は部屋 1 の 2 番目のテレポーターを利用する.ビ太郎は部屋 2 に移動する.
  • 2 回目のラウンドは以下のように進行する.
    • ビ太郎は部屋 2 の 1 番目のテレポーターを選ぶ.このテレポーターの行き先は部屋 3 または部屋 3 に設定できる.
    • ビバ子は部屋 2 の 1 番目のテレポーターの行き先を部屋 3 に設定する.
    • ビ太郎は部屋 2 の 1 番目のテレポーターを利用する.ビ太郎は部屋 3 に移動する.
    • ビ太郎が部屋 3 に移動したため,ゲームが終了する.

このとき,ゲームは 2 ラウンド目に終了するため,2 を出力する.

この入力例は小課題 2, 3, 5 の制約を満たす.

入力例 2

2
1
1 2

出力例 2

-1

両者が最善を尽くしたとき,ゲームは 10^{100} ラウンド目に終了するため,-1 を出力する.

この入力例は小課題 3, 4, 5 の制約を満たす.

入力例 3

5
3
4 4
2 2
1 1
1
3 3
2
1 1
5 5
2
5 5
3 3

出力例 3

2

この入力例は小課題 1, 3, 5 の制約を満たす.


Source Name

JOIG 2022/2023 春季トレーニング Contest Day1 問題2