제목 상세 정보

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$를 초과하지 않으며 인증서가 입력한 푸드넷에는 루프가 없습니다.