페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#2508

[고등부] 2025 KOI 1차대회 대비 모의고사 (5주차)

텔레포터
서브태스크
2초 1024MB

문제

정보 연구소에는 방이 N개 있으며, 각 방에는 1부터 N까지의 번호가 붙어 있다.

이들 방 중, 방 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}가 같은 경우도 있다는 점에 유의하라.

정보 연구소의 직원인 정올이와 한글이는, 이들 방과 텔레포터를 사용하여 게임을 진행한다. 게임은 다음과 같이 진행된다.

  • 정올이는 게임 시작 시, 방 1에 있다.

  • 라운드가 반복해서 진행된다. 각각의 라운드는 다음과 같이 진행된다.

    • 현재, 정올이가 방 x에 있다고 하자. 정올이는 방 x에 배치된 A_x개의 텔레포터 중 하나를 선택한다.

    • 정올이가 방 x의 y번째 텔레포터를 선택했다고 하자. 한글이는 그 텔레포터의 행선지를 방 P_{x, y} 또는 방 Q_{x, y} 중 하나로 설정한다. 어느 쪽을 선택할지는 라운드마다 달라도 된다.

    • 정올이는 방 x의 y번째 텔레포터를 이용한다. 정올이는 한글이에 의해 선택된 행선지(방 P_{x, y} 또는 방 Q_{x, y} 중 하나)로 이동한다.

    • 정올이가 방 N으로 이동한 경우, 또는 이 라운드가 10^{100}라운드인 경우, 게임이 종료된다.

정올이의 목적은 게임이 종료되기까지 진행되는 라운드 수를 최대한 적게 하는 것이며, 반면 한글이의 목적은 게임이 종료되기까지 진행되는 라운드 수를 최대한 많게 하는 것이다.

정보 연구소의 정보가 주어졌을 때, 양쪽이 최선을 다했을 경우 몇 라운드에서 게임이 종료되는지를 구하는 프로그램을 작성하라.


입력

입력은 다음 형식으로 표준 입력을 통해 주어진다.

N
A_1
P_{1, 1} Q_{1, 1}
P_{1, 2} Q_{1, 2}
…
P_{1, A_1} Q_{1, A_1}
A_2
P_{2, 1} Q_{2, 1}
P_{2, 2} Q_{2, 2}
…
P_{2, A_2} Q_{2, A_2}
…
…
A_(N-1)
P_{N-1, 1} Q_{N-1, 1}
P_{N-1, 2} Q_{N-1, 2}
…
P_{N-1, A_{N-1}} Q_{N-1, A_{N-1}}

제한

  • 2 ≤ N ≤ 200,000

  • A_i ≥ 1 (1 ≤ i ≤ N-1)

  • A_1 + A_2 + … + 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)

  • 입력되는 값은 모두 정수이다.


출력

표준 출력에, 양쪽이 최선을 다했을 때 몇 라운드에서 게임이 종료되는지를 한 줄에 출력하라.

단, 10^{100}라운드에서 게임이 종료되는 경우에는 대신 -1을 출력하라.


부분문제

번호 점수 조건
#113점

P_{i, j} = Q_{i, j} (1 ≤ i ≤ N-1, 1 ≤ j ≤ A_i)

#219점

P_{i, j} > i,\ Q_{i, j} > i (1 ≤ i ≤ N-1, 1 ≤ j ≤ A_i)

#322점

N ≤ 2,000, A_1 + A_2 + … + A_(N-1) ≤ 2,000

#430점

A_i = 1 (1 ≤ i ≤ N-1)

#516점

추가 제약 조건 없음


예제 #1

3
2
2 2
3 2
1
3 3
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
-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
2

이 입력 예제는 소과제 1, 3, 5의 제한을 만족한다.

로그인해야 코드를 작성할 수 있어요.