題目詳情

https://www.lydsy.com/JudgeOnline/upload/zjoi2012.pdf

題目描述

阿米巴是小强的好朋友。 阿米巴和小强在草原上捉螞蚱。 小强突然想，如果螞蚱被他們捉滅絕了，那麼吃螞蚱的小鳥就會餓死，而捕食小鳥的猛禽也會跟著滅絕，從而引發一系列的生態災難。

學過生物的阿米巴告訴小强，草原是一個極其穩定的生態系統。 如果螞炸滅絕了，小鳥照樣可以吃別的蟲子，所以一個物種的滅絕並不一定會引發重大的災難

我們現在從專業一點的角度來看這個問題。 我們用一種叫做食物網的有向圖來描述生物之間的關係：

一個食物網有$N$個點，代表$N$種生物，如果生物$x$可以吃生物$y$，那麼從$y$向$x$連一個有向邊。 這個圖沒有環。

圖中有一些點沒有連出邊，這些點代表的生物都是生產者，可以通過光合作用來生存； 而有連出邊的點代表的都是消費者，它們必須通過吃其他生物來生存。

如果某個消費者的所有食物都滅絕了，它會跟著滅絕.

我們定義一個生物在食物網中的“災難值”為，如果它突然滅絕，那麼會跟著一起滅絕的生物的種數。

舉個例子：在一個草場上，生物之間的關係是：

如果小强和阿米巴把草原上所有的羊都給嚇死了，那麼狼會因為沒有食物而滅絕，而小强和阿米巴可以通過吃牛、牛可以通過吃草來生存下去。 所以，羊的災難值是$1$。 但是，如果草突然滅絕，那麼整個草原上的$5$種生物都無法倖免，所以，草的災難值是$4$。

給定一個食物網，你要求出每個生物的災難值。

輸入格式

輸入檔案catas.in的第一行是一個正整數$N$，表示生物的種數。 生物從$1$標號到$N$。

接下來$N$行，每行描述了一個生物可以吃的其他生物的清單，格式為用空格隔開的若干個數位，每個數位表示一種生物的標號，最後一個數位是$0$表示清單的結束。

輸出格式

輸出檔案catas.out包含$N$行，每行一個整數，表示每個生物的災難值，

樣例

5
0
1 0
1 0
2 3 0
2 0

4
1
0
0
0

樣例說明

樣例輸入描述了題目描述中舉的例子。

數據規模與約定

對於$50\%$的數據，$N\le 10000$。

對於$100\%$的數據，$1\le N\le 65534$。

輸入檔案的大小不超過$1MB$，證輸入的食物網沒有環。