该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Statement

In the Elden Ring, there's a well-known landmark called the "Royal City Sewers." This complex structure is a must-see for many experienced soul Ass and novice tarnished. It consists of $n$ rooms and a number of two-way corridors. Each room has up to three doors, and corridors lead from behind the room doors to other rooms. All corridors in each room lead to different rooms. The entire sewer is interconnected, meaning you can travel between any two rooms, though you may need to pass through other rooms.

You need help labeling the doors to make exploration easier. The idea is that if a room $u$ has $d_u$ doors leading to other rooms, these doors will be labeled $1, 2, \cdots, d_u$, and then all players will follow a simple procedure. If they are in room $u$ at the start of their exploration, they will choose the door labeled 1 and go through the corresponding corridor. If they are in room $u$ and enter from the corridor through a door labeled $i$, they will choose the door labeled with the next number (i.e., $i + 1$ if $i < d_u$, or 1 if $i = d_u$) and go through the corresponding corridor.

Now that we have the labeling set, you need to find the number of different corridors that the players will go through if they start their exploration from each room, assuming they follow the rules and walk long enough.

Input

The first line contains an integer $n$ ($3 \leq n \leq 2 \times 10^5$), which represents the number of rooms in the sewers.

The next $n$ lines contain descriptions of all the corridors, with line $u$ describing the corridor connecting room $u$ to the others. It begins with an integer $d_u$ ($1 \leq d_u \leq 3$), indicating the number of doors in that room. Next are $d_u$ integers $v_1, v_2 , \cdots, v_{d_u}$, giving the room numbers $(1 \leq v_i \leq n, v_i \neq u,$and $v_i \neq v_j$ if $i \neq j$) to which these doors lead, in the order of their assigned numbers.

Note that all corridors are bidirectional, so if there is a door from room $u$ to room $v$, then there is also a door from room $v$ to room $u$.

Output

Output $n$ lines, where line $i$ contains the number of different corridors the player will visit if they start in room $i$.

Samples

6
3 4 2 3
3 5 1 3
3 6 1 2
1 1
1 2
1 3

5
4
5
5
4
5

Notes

The figure below shows the player's path starting from node 1. The numbers marked on the dark blue and light blue arrows indicate the player's path in step $i$. This shows that the player passes through five different corridors.