Problem : 55 - 情報網

Problem Statistics

Solved Member: 25　　Submission: 145　　User Tried: 26

Statement:

你在附中各個地點(諸如廁所,辦公室之類的)N個點(1 <= N <= 100000)建立了你的情報網，剛開始，你因為沒有錢只有架了一點點的線路。每條線路連接2個地點，有一定的傳輸方向。

每當要發送情報的時候，你需要將情報傳送給其中一個點，接著情報會隨著情報網自動傳到各個互相連接的點。

漸漸的，你變有錢了，你決定升級你的設備，你想要計算下面的問題：

1.剛開始，若想將情報傳遍各個點，你至少需要手動傳送幾次情報。
2.你想讓你的情報網只需要手動傳至任意一個點，情報就會自動流到各地。至少需要再增加幾條線路？

Input:Output:

第1行有1個整數N，代表點的個數。
接下來有N行，每行有任意個整數，第i+1行的數字代表第i點連接到的點。每一行最後會以0做結束。
並且你可以假設連接的線路總數<=500000。

其中有50%的測資，n<=100。

請你輸出2行數字，分別代表上面2小題的答案。

Sample Input:Sample Output:

5
2 4 3 0
4 5 0
0
0
1 0

1
2

Source:

IOI 1996

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	500ms	131072kb
1	500ms	131072kb	5
2	500ms	131072kb	5
3	500ms	131072kb	5
4	500ms	131072kb	5
5	500ms	131072kb	5
6	500ms	131072kb	5
7	500ms	131072kb	5
8	500ms	131072kb	5
9	500ms	131072kb	5
10	500ms	131072kb	5
11	1500ms	131072kb	5
12	1500ms	131072kb	5
13	1500ms	131072kb	5
14	1500ms	131072kb	5
15	1500ms	131072kb	5
16	1500ms	131072kb	5
17	1500ms	131072kb	5
18	1500ms	131072kb	5
19	1500ms	131072kb	5
20	1500ms	131072kb	5