시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

The JOI island is a sightseeing area. The whole island is designated as a natural park.

There are N places and several roads in the JOI island. The places are numbered from 0 to N − 1. Every road connects two different places, and we can pass it in both directions. For each place, there are at most 7 roads connecting it with other places. For each pair of two different places, there is at most one road connecting them. We can travel from every place to any other places if we pass through several roads.

You and your friend IOI-chan will investigate the JOI island. To investigate it efficiently, you need to figure out the structure of the JOI island. The JOI island is dangerous because there are many wild animals. Since IOI-chan has high athletic ability, she will explore the JOI island, and you will specify the structure of the JOI island according to IOI-chan’s reports.

You will give two places A, B and several possibilities of intermediate places to IOI-chan, and ask whether it is possible to travel from the place A to the place B if we can pass through some of the given intermediate places only. Then, IOI-chan will explore the JOI island, and reports the results to you.

Since they can not take too much time for investigation, the number of queries should be less than or equal to 45 000.

Write a program which communicates with IOI-chan and specifies the structure of the JOI island.

입력

The sample grader reads the following data from the standard input.

  • The first line of input contains an integer T, the subtask number.
  • The second line of input contains an integer N, the number of places.
  • The third line of input contains an integer M, the number of roads.
  • In the i-th line (1 ≤ i ≤ M) of the following M lines contains two space separated integers Ai, Bi. This means there is a road connecting the place Ai and the place Bi, and we can pass it in both directions.

출력

When the program terminates successfully, the sample grader writes the following information to the standard output. (The quotation mark is not written actually.)

  • If your program is considered as correct, the sample grader writes “Accepted.”
  • If your program is considered as Wrong Answer, the sample grader writes its type in the following form “Wrong Answer [1],” and your program is terminated.

If your program is considered as several types of Wrong Answer, the sample grader reports one of them only.

제한

  • 1 ≤ T ≤ 5.
  • 2 ≤ N ≤ 1 400.
  • 1 ≤ M ≤ 1 500.
  • For each place, there are at most 7 roads connecting it with other places.
  • We can travel from every place to any other places if we pass through several roads.
  • For each pair of two different places, there is at most one road connecting them.

구현

You need to write a program which implements the way to specify the structure of the JOI island. Your program should include park.h.

Your program should implement the following routine.

  • void Detect(int T, int N)
    This function is called only once.
  • The parameter T is the subtask number, and N is the number of places.

Your program should output the structure of the JOI island specified by it using the following function:

  • void Answer(int A, int B)
    The number of calls to this function should be the same as the number of roads in the JOI island.
    • The parameters A, B denote there is a road connecting the place A and the place B.

The parameters should satisfy the following conditions:

  • A, B should satisfy 0 ≤ A < B ≤ N − 1. If this condition is not satisfied, your program is considered as Wrong Answer [1].
  • If the function is called with parameters (A, B), there must be a road connecting the place A and the place B. If this condition is not satisfied, your program is considered as Wrong Answer [2].
  • The function should not be called more than once with the same parameter (A, B). If this condition is not satisfied, your program is considered as Wrong Answer [3].

Moreover, your program can call the following function:

  • int Ask(int A, int B, int Place[])
    This function is used to ask IOI-chan.
    • Place is the pointer of an array of possible intermediate places. For each i (0 ≦ i ≦ N − 1), Place[i] = 1 is we can pass through the place i, and Place[i] = 0 is we can not pass through the place i.
    • The return value of this function is 1 if we can travel from the place A to the place B if we can pass through some of the places specified by the array Place[] only. Otherwise, the return value is 0.

The parameters should satisfy the following conditions:

  • 0 ≤ A < B ≤ N − 1.
  • 0 ≤ Place[i] ≤ 1 (0 ≦ i ≦ N − 1).
  • Place[A] = 1.
  • Place[B] = 1.

If these conditions are not satisfied, your program is considered as Wrong Answer [4]. However, the behavior of the function is not guaranteed if the length of the array Place[] is not equal to N.

The function Ask should not be called more than 45 000 times. If it exceeds, your program is considered as Wrong Answer [5].

When the function Detect terminates, if there is a road which is not a parameter of the previous calls to the function Answer, your program is considered as Wrong Answer [6].

Your program can implement other functions for internal use, or use global variables. Your program should not use standard input and standard output. Your program should not communicate with other files by any methods.

서브태스크 1 (10점)

  • T = 1.
  • N ≤ 250.

서브태스크 2 (10점)

  • T = 2.
  • M = N − 1.
  • For the place 0 or N − 1, there is exactly one road connecting it with another place. For every other place, there are exactly 2 roads connecting it with other places.

서브태스크 3 (27점)

  • T = 3.
  • M = N − 1.
  • For every i (1 ≤ i ≤ N − 1), we can travel from the place 0 to the place i if we pass through at most 8 other places.

서브태스크 4 (30점)

  • T = 4.
  • M = N − 1.

서브태스크 5 (23점)

  • T = 5.

예제

Here is a sample input for sample grader and corresponding function calls.

Sample Input Sample Calls
Call Return
1
6
7
0 1
0 3
1 2
1 4
2 4
2 5
3 4
Ask(3, 5, {0,0,1,1,1,1}) 1
Answer(2, 4)  
Answer(2, 5)  
Answer(3, 4)  
Ask(0, 4, {1,0,1,0,1,0}) 0
Answer(0, 1)  
Answer(0, 3)  
Answer(1, 4)  
Answer(1, 2)  

Note that the function calls in this example do not necessarily have meaning.

In this example, the function Detect is called with parameters T = 1, N = 6.

In this example, the structure of the JOI island is as follows:

The structure of the JOI island.

The circles and numbers denote the places and their numbers. The line segments denote the roads.

  • The first call to the function Ask asks whether we can travel from the place 3 to the place 5 if we can pass through the places 2, 3, 4, 5 only. Because it is possible, the function Ask returns 1.
  • The second call to the function Ask asks whether we can travel from the place 0 to the place 4 if we can pass through the places 0, 2, 4 only. Because it is impossible, the function Ask returns 0.

첨부

제출할 수 있는 언어

C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.