a523. 12442 - Forwarding Emails
Tags :
Accepted rate : 154人/218人 ( 71% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-09-19 13:49

Content

「...務必轉寄給十個人,以證明你相信國王有新衣。」

 這種 email 很討人厭,不是嗎?

火星人也有這種郵件,但他們有個新奇的方式來處理它。他們既不亂寄,也不會不寄,而是只寄給一個朋友,不多也不少,(而且不會寄給自己)。現在火星部落酋長要發一封 email 出去,他很固執只肯發給一個人。身為酋長,他設法查出了誰會轉信給誰,現在他想知道:他的信要寄給誰才能讓最多的火星人看到?

Input

輸入的第一行有一個 T (≤ 20) 表示測資筆數。

每筆測資的第一行有一個整數 N (2 ≤ N ≤ 50000) 表示社群中火星人的數量。以下 N 行每行有兩個整數:u v (1 ≤ u, v ≤ N, u ≠ v) 代表火星人 u 會把 email 轉給火星人 v

Output
對於每筆測資,印出測資編號及一個整數 m,代表酋長應該把初始郵件寄達的那個火星人。如果正確答案不止一個,輸出最小的數字。
Sample Input #1
3
3
1 2
2 3
3 1
4
1 2
2 1
4 3
3 2
5
1 2
2 1
5 3
3 4
4 5
Sample Output #1
Case 1: 1
Case 2: 4
Case 3: 3
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :
Tags:
出處:
UVa12442 [管理者: snail (蝸牛) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
38615 wrr606@gmail ... (Function) a523
DFS+剪枝
220 2023-12-10 18:07