Just Ordinary Inventions 라는 회사를 알고 있는가? 이 회사의 사업은 "그저 평범한 발명품"을 만드는 것이다.

JOI 군은 Just Ordinary Inventions 가 개발한 최신 게임을 플레이하고 있다.

이 게임은 여러 개의 방과 여러 개의 길로 이루어진 던전을 탐험하는 게임이다. 길은 던전 내의 서로 다른 두 방을 연결하며 양방향으로 이동할 수 있다. 서로 다른 임의의 두 방 사이에는 최대 하나의 길만 연결되어 있으며, 양 끝이 같은 방인 길은 없다. 또한, 던전 내의 임의의 두 방은 몇 개의 길을 이용하여 서로 도달할 수 있음이 알려져 있다. 각 방은 다른 방들과 매우 비슷하게 생겼으며, 나가는 길의 개수가 같은 방들은 방의 외관만 보고서는 서로 구별할 수 없다.

이 게임에서는 탐험을 돕기 위해 각 방에 표식과 받침대가 설치되어 있다. 방에서 나가는 길들은 표식을 기준으로 1 번째, 2 번째, ... 길로 셀 수 있다. 게임 도중 던전의 구조는 변하지 않는다. 따라서 같은 방에서 같은 번호의 길을 이용해 이동하면 항상 같은 방에 도착한다. 받침대에는 플레이어가 색을 바꿀 수 있는 보석이 하나 장식되어 있다. 보석의 색은 색 1, 색 2, ..., 색 $X$ 중 하나이며, 게임 시작 시 각 방에 있는 보석의 색은 모두 색 1 이다. 보석의 색은 플레이어가 조작하지 않는 한 변하지 않는다.

JOI 군은 이 던전의 구조, 즉 방들이 길로 어떻게 연결되어 있는지를 알 수 있다면 이 게임을 쉽게 클리어할 수 있다는 것을 깨달았다. 하지만 JOI 군이 아무리 노력해도 던전의 구조를 알아낼 수 없었다. 그래서 당신은 JOI 군을 대신하여 던전의 구조를 알아내는 프로그램을 작성하기로 했다.

과제

던전을 탐험하여 그 구조를 알아내는 프로그램을 작성하라. 단, JOI 군은 던전의 구조가 완전히 밝혀지는 것을 원하지 않았기 때문에, 프로그램은 던전의 구조를 직접 답하는 대신 1 부터 $R$ 까지의 각 정수 $i$ 에 대하여 "최소 $i$ 개의 길만을 사용하여 도달할 수 있는 방의 쌍이 몇 개 있는지"(방의 순서를 바꾼 쌍은 같은 쌍으로 간주한다)의 값을 답해야 한다.

던전을 탐험하기 위해 다음 동작을 수행하는 라이브러리가 제공된다:

• 현재 방에서 나가는 길이 몇 개인지 알 수 있다.
• 현재 방의 받침대에 장식된 보석의 색을 알 수 있다.
• 현재 방의 받침대에 장식된 보석의 색을 지정한 색으로 변경한다(현재와 같은 색을 지정할 수도 있다). 그 후, 방에서 나가는 길 중 하나를 선택하여 그 길을 통해 다른 방으로 이동한다.
• 마지막으로 사용한 길이 현재 방에서 나가는 길들 중 몇 번째 길이었는지 알 수 있다.

구현 세부사항

JOI 군이 답하기 위한 방법을 구현한 하나의 프로그램을 작성해야 한다. 프로그램은 dungeon2.h 를 포함해야 한다.

프로그램은 다음 루틴을 구현해야 한다:

• void Inspect(int R)
  • 이 루틴은 처음에 정확히 한 번 호출된다.
  • 인자 $R$ 은 1 부터 $R$ 까지의 각 정수 $i$ 에 대하여 "최소 $i$ 개의 길만을 사용하여 도달할 수 있는 방의 쌍이 몇 개 있는지"의 값을 답해야 함을 나타낸다.

또한, 질문에 답하기 위해 다음 루틴을 호출해야 한다:

• void Answer(int D, int A)
  • 인자 $D$ 와 $A$ 는 이 호출에서 "최소 $D$ 개의 길만을 사용하여 도달할 수 있는 방의 쌍이 $A$ 개 있다"고 답하고 있음을 나타낸다.

단, Answer 의 호출은 다음 조건을 만족해야 한다:

• $D$ 는 1 이상 $R$ 이하의 정수여야 한다. 이를 만족하지 않으면 오답 [1] 로 판정된다.
• 같은 인자 $D$ 로 Answer 를 두 번 이상 호출해서는 안 된다. 이를 만족하지 않으면 오답 [2] 로 판정된다.
• Answer 는 정확히 $R$ 번 호출되어야 한다. 이를 만족하지 않으면 오답 [3] 으로 판정된다.
• $A$ 는 최소 $D$ 개의 길만을 사용하여 도달할 수 있는 방의 쌍의 개수여야 한다. 이를 만족하지 않으면 오답 [4] 로 판정된다.

Answer 의 호출이 오답으로 판정되면, 이후의 프로그램 실행이 중단될 수 있다.

추가로, 프로그램 내에서 다음 루틴들을 호출할 수 있다:

• void Move(int I, int C)
  • 인자 $I$ 는 플레이어가 이동하기 위해 선택한 길의 번호이다. 이 호출 직후 플레이어는 현재 방에서 나가는 $I$ 번째 길을 이용하여 다른 방으로 이동한다.
  • 인자 $C$ 는 다른 방으로 이동하기 전에 현재 방의 받침대에 장식된 보석의 색을 색 $C$ 로 변경함을 나타낸다.

단, Move 의 호출은 다음 조건을 만족해야 한다:

• 인자 $I$ 는 1 이상 $K$ 이하의 정수여야 한다. 여기서 $K$ 는 플레이어가 현재 위치한 방에서 나가는 길의 개수이다. 이를 만족하지 않으면 오답 [5] 로 판정된다.
• 인자 $C$ 는 1 이상 $X$ 이하의 정수여야 한다. 여기서 $X$ 는 보석 색의 종류 수이다. $X$ 의 값은 각 서브태스크마다 정해져 있다. 이를 만족하지 않으면 오답 [6] 으로 판정된다.

• Move 는 1,500,000 번을 초과하여 호출해서는 안 된다. 이를 초과하여 호출하면 오답 [7] 로 판정된다.

• int NumberOfRoads()

  • 이 함수는 플레이어가 현재 위치한 방에서 나가는 길의 개수를 반환한다.

• int LastRoad()

  • 이 함수는 마지막으로 사용한 길이 현재 방에서 나가는 길들 중 몇 번째 길이었는지를 반환한다. 단, Move 가 한 번도 호출되기 전에 이 함수가 호출되면 -1 을 반환한다.

• int Color()

  • 이 함수는 플레이어가 현재 위치한 방의 받침대에 장식된 보석의 색을 반환한다.

루틴 Inspect 의 호출이 끝난 후 정답 여부가 판정된다.

내부적인 용도로 다른 루틴을 구현하거나 전역 변수를 선언하는 것은 자유이다. 그러나 제출한 프로그램은 표준 입력/표준 출력이나 다른 어떤 파일과도 상호작용해서는 안 된다.

컴파일 및 실행

대회 사이트에서 다운로드할 수 있는 아카이브에 샘플 그레이더가 제공된다. 이 아카이브에는 제출해야 하는 파일의 샘플도 포함되어 있다.

샘플 그레이더는 단일 파일 grader.c 또는 grader.cpp 로 구성된다. 프로그램을 테스트하려면 다음 명령어를 실행하라:

• C 의 경우: gcc -std=c11 -O2 -o grader grader.c dungeon2.c -lm
• C++ 의 경우: g++ -std=c++11 -O2 -o grader grader.cpp dungeon2.cpp

컴파일이 성공하면 grader 라는 이름의 실행 파일이 생성된다.

실제 채점에 사용되는 그레이더는 샘플 그레이더와 다르다는 점에 유의하라. 샘플 그레이더는 단일 프로세스로 실행되며, 표준 입력에서 입력을 읽고 표준 출력에 결과를 출력한다.

샘플 그레이더 입력

샘플 그레이더는 표준 입력으로부터 다음 데이터를 읽어들인다:

• 첫째 줄에는 공백으로 구분된 정수 $N, X, R$ 이 주어진다. 이는 던전에 방 1, 방 2, ..., 방 $N$ 의 $N$ 개의 방이 있고, 보석 색의 종류가 $X$ 가지이며, 프로그램이 $R$ 개의 값을 답해야 함을 나타낸다.
• 이어지는 $2N$ 개의 줄 중 $(2i - 1)$ 번째 줄($1 \le i \le N$)에는 방 $i$ 에서 나가는 길이 $D_i$ 개 있음을 나타내는 정수 $D_i$ 가 주어진다. $2i$ 번째 줄($1 \le i \le N$)에는 공백으로 구분된 $D_i$ 개의 정수 $T_{i1}, T_{i2}, \dots, T_{iD_i}$ 가 주어진다. 이는 방 $i$ 에서 나가는 $j$ 번째 길($1 \le j \le D_i$)을 따라 이동하면 방 $T_{ij}$ 에 도착함을 나타낸다.
• 이어지는 $R$ 개의 줄 중 $j$ 번째 줄($1 \le j \le R$)에는 정수 $A_j$ 가 주어진다. 이는 최소 $j$ 개의 길만을 사용하여 도달할 수 있는 방의 쌍이 $A_j$ 개 있음을 나타낸다. 즉, 각 $j$ ($1 \le j \le R$)에 대하여 인자 $D$ 를 $j$, 인자 $A$ 를 $A_j$ 로 하여 Answer 를 호출하면 샘플 그레이더는 정답으로 판정하고, 그렇지 않으면 오답으로 판정한다.

샘플 그레이더는 플레이어의 초기 위치를 방 1 로 하여 당신의 루틴을 호출한다.

샘플 그레이더 출력

프로그램 실행이 정상적으로 종료되면, 샘플 그레이더는 표준 출력의 한 줄에 다음 정보를 출력한다(따옴표는 실제로 출력되지 않는다):

• 정답인 경우, 함수 Move 의 호출 횟수가 Accepted : #move = 8 과 같이 출력된다.
• 오답인 경우, 오답의 종류가 Wrong Answer [1] 과 같이 출력된다.

제한

모든 입력 데이터는 다음 조건을 만족한다. $N, D_i, T_{ij}$ 의 의미는 '샘플 그레이더 입력' 섹션을 참고하라.

• $2 \le N \le 200$
• $3 \le X \le 100$
• $1 \le R \le 200$
• $1 \le D_i \le N - 1$ ($1 \le i \le N$)
• $1 \le T_{ij} \le N$ 이고 $T_{ij} \neq i$ ($1 \le i \le N, 1 \le j \le D_i$)
• $T_{i1}, T_{i2}, \dots, T_{iD_i}$ ($1 \le i \le N$)는 서로 다르다.
• 각 $i, j$ ($1 \le i \le N, 1 \le j \le D_i$)에 대하여, $T_{T_{ij}k} = i$ 를 만족하는 $k$ ($1 \le k \le D_{T_{ij}}$)가 존재한다.
• 임의의 두 방은 몇 개의 길을 이용하여 서로 도달할 수 있다.

서브태스크

아래에서 입력 데이터의 던전에 있는 방의 개수를 $N$, 길의 개수를 $M$ 이라고 하자.

서브태스크 1 [17점]

다음 조건을 만족한다:

• $N \le 50$
• $M \le 100$
• $X = 100$

서브태스크 2 [27점]

다음 조건을 만족한다:

• $N \le 50$
• $M \le 100$
• $X = 3$

서브태스크 3 [56점]

• $X = 3$ 을 만족한다.

이 서브태스크에서 점수는 다음과 같이 결정된다:

• 이 서브태스크의 모든 테스트 케이스에 대하여 다음 값의 최댓값을 $L$ 이라고 하자:
  • $\frac{C}{M}$ (여기서 $C$ 는 Move 의 호출 횟수이다).
• 이때 이 서브태스크의 점수는 다음과 같다:
  • $L \le 14$ 이면 56 점.
  • $14 < L \le 32$ 이면 $\lfloor 70 - L \rfloor$ 점.
  • $32 < L \le 64$ 이면 $\lfloor 54 - \frac{L}{2} \rfloor$ 점.
  • $64 < L$ 이면 0 점.

여기서 $\lfloor x \rfloor$ 는 $x$ 를 넘지 않는 가장 큰 정수를 나타낸다.

예제

입력 1

4 3 3
1
2
3
1 3 4
2
2 4
2
2 3
4
2
0

출력 1

Inspect(3)
NumberOfRoads() -> 1
LastRoad() -> -1
Move(1,2)
Color() -> 1
LastRoad() -> 1
NumberOfRoads() -> 3
Move(1,3)
Color() -> 2
Answer(1,4)
Answer(2,2)
Answer(3,0)

참고

이 예제의 함수 호출들은 반드시 의미 있는 호출인 것은 아니다.