Ancient Bird Gathering

In ancient times, the scenic Jinxianghe region was home to flocks of Archaeopteryx, a species known for its strong social bonds. Nowadays, there is a specialty store selling Archaeopteryx memorabilia, and the birds are gathering for parties at two locations: upstream and downstream.

There are \(N\) Archaeopteryxes numbered from \(1\) to \(N\). For the \(i\)-th bird, there are \(M_i\) birds that it knows (its acquaintances) with indices \(F_{i,1}, F_{i,2}, \dots, F_{i,M_i}\). Note that the friendship is one‐directional. That is, if bird \(s\) knows bird \(t\), bird \(t\) does not necessarily know bird \(s\).

You must assign each bird to one of the two party locations such that for every bird, the number of its acquaintances (from its given list) assigned to the same party is even. Every bird must attend exactly one of the two parties. Your task is to output any valid assignment by reporting the list of birds (i.e. their indices) that attend the upstream party.

Hint: Let \(a_i\) be a binary variable representing the party assignment (e.g. \(1\) for upstream and \(0\) for downstream). The condition for bird \(i\) is that the number of acquaintances in the same party, i.e.,

\[ \sum_{j \in F(i)} \mathbf{1}_{\{a_i = a_j\}} \equiv 0 \pmod{2}, \]

must hold. Using the observation that \(\mathbf{1}_{\{a_i = a_j\}} = 1 + a_i + a_j\) in \(\mathbb{F}_2\), one may transform the condition into a system of linear equations over \(\mathbb{F}_2\) which has a solution guaranteed by the problem.

inputFormat

The first line contains an integer \(N\) representing the number of birds.

Then \(N\) lines follow. The \(i\)-th line begins with an integer \(M_i\) (the number of acquaintances for bird \(i\)), followed by \(M_i\) integers \(F_{i,1}, F_{i,2}, \dots, F_{i,M_i}\) representing the indices of the birds it knows.

outputFormat

Output a single line containing the indices (separated by spaces) of the birds assigned to the upstream party. Any valid assignment is accepted.

sample

3
1 2
1 3
0

2

</p>