Background
這是一個在古老的鐵幕時代，有關間諜以及反間諜的問題。
在自由世界的一個秘密情報局 CONTROL，必須與邪惡的國際組織 KAOS 對抗。為了將帳冊送至 CONTROL 在鐵幕的獨立機構中，特務 82 到特務 85 在東方快車 (Orient Express) 的車廂上，被神秘且邪惡的 KAOS 特工 Cirilo Krochanska 所暗殺。而你，Maxwell Smart，特務 86，必須搭上火車和特務 B-12 接觸，將加密的訊息「tnih sevig cilc thgir」傳給他，並且避免成為 Krochanska 手下第五位犧牲者！
但是，Krochanska 在哪裡呢？我們知道他總是用火車來旅行，通常在歐洲某些重要的車站上，而且他已經準備好馬上去他想到達的目的地。
（如果你做過一點點情報工作的話，你將會發現 Cirilo Krochanska 其實是 …）
The Problem
歐洲鐵路網有數條路線所構成，每條路線有它的起訖車站，路線中還有數個中繼站均勻分布在路線中。舉例來說，如果我們列舉出車站 1 至車站 13 所有的車站，我們可以列出以下三條路線：
- 第一條 1 - 2 - 3 - 4 - 5 - 6 - 7。
- 第二條 8 - 9 - 4 - 10 - 13。
- 第三條 11 - 2 - 12 - 9 - 6 - 7。
在每條路線中火車是雙向行進的，從某一站行進下一站的時間恆為 2 個小時。就像你所看到的，有些車站出現在不同路線上，我們稱呼它為「重點車站」，而其餘的稱呼為「次要車站」。我們相信 Krochanska 位在一個去其他地方都是最快的重點車站，尤其是，從他座落的重點車站到其他重點車站，行進時間的平均值會達到最小。你可以假設從一條路線切換到另一條路線不會耗時，你必須找出 Cirilo Krochanska 在哪裡。
The Input
輸入包含數筆測資，第一行代表輸入的測資數。
對於每組測試資料，第一行包括兩個整數 N 和 S，N 代表所有車站的數量，S 代表路線的數量。車站將編號為 1 至 N，而 N 不大於 10000，S 不大於 100。接下來的 S 行為火車行經的路線，每行有數個由空白分開的數字，並且以 0 代表結束。
重點車站介於 1 至 100 個，任兩個車站間都會有一條路徑可以抵達。
The Output
對於每組測資，您必須輸出Krochanska藏身的車站，格式為：
Krochanska is in: X
而 X 代表車站的編號，如果有多於一個重點車站有最小距離，請輸出編號最小的車站。
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