11792 - Krochanska is Here!

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