解題區/出題解題

[ACM 題目] 災難再臨

contents

  1. 1. Description
    1. 1.1. Background
    2. 1.2. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. Solution

Description

Background

還記得那些年我們已經經歷的災難嗎？PTC201410D！ZJOI 2012 DAY2！如果不記得，接著請聽我捏造個故事。

Problem

危險種這一類的怪物，不斷地在村莊肆虐作亂，並且不斷地靠近帝國首都，艾斯德斯大人受令狩獵帝國周圍的危險種。

根據情報顯示，危險種移動的路徑預估為有向無環圖，牠們的數個巢穴坐落於地圖的末端 (也就是不會在有別的地點抵達這個地方)，而在首都前將有數個要塞，要塞正牠們的目標之地。為了阻止牠們到來，身為艾斯德斯大人的下屬，必須派軍隊前往危險種前往要塞的必經之地，即使抵達的位置無法阻止所有巢穴的危險種，但能對艾斯德斯大人貢獻一份心力便已足夠。

由於必經之地很多，好不容易在地圖上標記起來，卻又不知道哪個地點比較好 (可以阻止最多巢穴前往要塞)。正在困擾的同時，艾斯德斯大人已經將全部危險種給剷除了 …

「還沒一瞬間就將怪物解決，艾斯德斯大人啊！ <(_ _)>」

不過報告書還是得寫 …

Input

輸入有多組測資。

每組測資第一行會有一個整數 N (N < 32767)。

接下來會有 N 行，第 i 行上會有數個整數 x，直到 0 表示結束，表示有一條邊從 i 到 x。

Output

對於每組測資，輸出可以埋伏地點以及埋伏的最佳收穫情況。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
5
0
1 0
1 0
2 3 0
2 0
17
10 13 0
9 12 0
9 14 11 0
10 0
12 0
17 0
0
0
13 14 0
11 0
15 0
15 0
16 0
7 0
16 0
17 0
8 0

Sample Output

1
2
1 1
6 4

Solution

1