P3429 [POI 2005] DWA-Two Parties

The Byzantine king is going to host two large parties and hopes to invite more residents. From his rich experience, the king knows that if a resident meets an even number of friends at the party, they will be very happy. Therefore, he asks you to assign the country's residents to two parties so that as many people as possible have an even number of friends at the party they attend. Acquaintance is a symmetric relation: if $A$ knows $B$, then $B$ also knows $A$.

There are $N+1$ lines in total. The first line contains an integer $N$ ($1 \le N \le 200$), the number of residents. In the next $N$ lines, the $(i+1)$-th line contains an integer $l_i$, the number of friends of the $i$-th resident, followed by $l_i$ integers, which are the indices of the $i$-th resident’s friends. We assume no one is their own friend. If $B$ appears in $A$’s friend list, then $A$ also appears in $B$’s list.

The first line contains an integer $M$, the number of people attending the first party. The second line contains $M$ integers, which are the indices of the residents going to the first party; the remaining residents go to the second party. If there are multiple valid answers, output any one of them.

Translated by ChatGPT 5