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 free- lance 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 se- vig cilc thgir”, deliver the payroll, and avoid becom- ing Krochanska’s fifth victim! If you do a bit of espionage, you will discover here that Cirilo Krochanska is... 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. 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. 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.
2/2 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 12345670 8 9 4 10 13 0 11 2 12 9 6 7 0 62 2536140 4163520 52 123450 351420 72 35124760 3610 Sample Output Krochanska is in: 9 Krochanska is in: 3 Krochanska is in: 4 Krochanska is in: 6