递归回溯?

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

元旦将至,G购买了n块巧克力,并将这些巧克力编号为123….n,然后将这些巧克力堆在一起,保证每块巧克力最多压着两块巧克力(如图1)

保证不存在巧克力A压着BB又压着A的情况,保证不存在A压着BCBC下面的情况。一块巧克力可能被多块巧克力压着(如图2)。

现在问题来了,G想知道每块巧克力的下面各有多少块巧克力。

X压着YY压着Z,那么YZ都是位于在X的下面的巧克力。若YX下面,ZY下面,那么Z也是位于在X的下面的巧克力(如图3)。

Input

 多组输入。

对于每组数据:

首先输入一个n1 <= n <= 1000),代表有n块巧克力。

接下来的n行,每行的第一个数x(1 <= x <= n,任意两个x不相等)为巧克力的编号,接下来的一个正整数y(0 <= y <= 2),代表巧克力x压着y块巧克力,接下来y个数,代表y个巧克力的编号。

Output

 对于每组输入,输出n个整数代表答案,两个数之间用空格隔开。

Sample Input

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

Sample Output

1 0 2 0 0

Hint

 

Source

zmx