Background

This is a problem about spies and counter-spies in the old days of the Iron Curtain. CONTROL, the secret intelligence agency of the free world, must fight against KAOS, the international organization of evil.

CONTROL agents 82 through 85 have all died attempting to deliver the payroll for Control's freelance agents located behind the Iron Curtain. They all were killed by the mysterious and sinister KAOS agent Cirilo Krochanska, while traveling aboard the Orient Express. You are Maxwell Smart, agent 86, and you must board the train, make contact with agent B-12, give him the encrypted message "tnih sevig cilc thgir", deliver the payroll, and avoid becoming Krochanska's fifth victim!

But, where is Krochanska? We know he always travel by train; he is in some important train station in Europe, and is ready to reach immediately any destination where he is required.

If you do a bit of espionage, you will discover here that Cirilo Krochanska is...

The Problem

The railway network of Europe consists of a number of lines. Each line goes between two different stations; and there are also some intermediate stations uniformly distributed in each line. For example, if we enumerate the stations from 1 to 13, we can have the following three lines:

• Line 1. 1 - 2 - 3 - 4 - 5 - 6 - 7.
• Line 2. 8 - 9 - 4 - 10 - 13.
• Line 3. 11 - 2 - 12 - 9 - 6 - 7.

Trains travel in both directions of the lines. The time to travel from a station to the following (or the previous) station of the line is always 2 hours. As you can observe, some stations are used by different lines --we call them the important stations--, while other stations are only used by one line --the secondary stations--.

We believe Krochanska is situated in an important station where he can travel faster to any other station. In particular, he tries to minimize the average of the minimum times from his station to the rest of important stations. You can assume that there is no loss of time to switch from one line to another at a station.

You have to find out where Cirilo Krochanska is.

The Input

The input will contain several test cases. The first line indicates the number of test cases.

For each test case, the first line contains two integers: N and S. N is the total number of existing stations, and S is the number of lines. Stations are numbered from 1 to N; N is not greater than 10000; and S is not greater than 100. Next, we have S lines, one for each train line. These lines consist of a list of stations, separated by blank spaces, ending with a 0.

There will be between 1 and 100 important stations, inclusive. There is always a path between any pair of stations.

The Output

For each test case, you have to output the number of the resulting station, in the following format:

Krochanska is in: X

where X is the number of the station. If there are more than one important station with the minimum distance, then you have to output the one with the smallest number.

Sample Input

4
13 3
1 2 3 4 5 6 7 0
8 9 4 10 13 0
11 2 12 9 6 7 0
6 2
2 5 3 6 1 4 0
4 1 6 3 5 2 0
5 2
1 2 3 4 5 0
3 5 1 4 2 0
7 2
3 5 1 2 4 7 6 0
3 6 1 0

Sample Output

Krochanska is in: 9
Krochanska is in: 3
Krochanska is in: 4
Krochanska is in: 6

OMP'10
Facultad de Informatica
Universidad de Murcia (SPAIN)