Natural Park

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

The JOI island has N places and several roads. The places are numbered from 0 to N − 1. Every road connects two different places, and you can travel it in both directions. Each place has at most 7 roads connecting it with other places. Between any two different places, there is at most one road. You can travel from any place to any other place by passing 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. IOI-chan has high athletic ability, so she will explore the JOI island, and you will determine the structure of the JOI island from IOI-chan's reports.

You give IOI-chan two places A and B and several possibilities for intermediate places, and ask whether it is possible to travel from place A to place B while passing only through some of the given intermediate places. IOI-chan then explores the JOI island and reports the results to you.

Since the investigation cannot take too much time, the number of queries must be at most 45 000.

Write a program that communicates with IOI-chan and determines the structure of the JOI island.

The sample grader reads the following data from standard input.

• The first line contains an integer T, the subtask number.
• The second line contains an integer N, the number of places.
• The third line contains an integer M, the number of roads.
• 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 place Ai and place Bi, and you can travel it in both directions.

When the program terminates successfully, the sample grader writes the following information to standard output. (The quotation marks are not written in reality.)

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

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

• 1 ≤ T ≤ 5.
• 2 ≤ N ≤ 1 400.
• 1 ≤ M ≤ 1 500.
• Each place has at most 7 roads connecting it with other places.
• You can travel from any place to any other place by passing through several roads.
• Between any two different places, there is at most one road.