Background

2020-2021 CTT optional problem.

Problem Description

You invited $n$ people to play a game. The $n$ people are numbered from $0$ to $n-1$, and they sit in a circle in order, where person $0$ is adjacent to person $n-1$.

You give each of these $n$ people a card with a number $\texttt{0}$ or $\texttt{1}$ written on it. Everyone can see the numbers on all cards except those of the two adjacent people, and they can also see their own card.

The game lasts for $m$ rounds. In round $i$, you announce $k_i$ pieces of information to everyone. Each piece of information is in the form: “In a certain set, there exists a card with some number.” After the announcements:

• If someone holds a card with $\texttt 0$, and they can deduce the value of the logical OR of the two adjacent people’s card numbers, then they must shout “Meltdown!”.
• If someone holds a card with $\texttt 1$, and they can deduce the value of the logical XOR of the two adjacent people’s card numbers, then they must shout “Meltdown!”.

Everyone knows the rules, and everyone has extremely strong reasoning ability: as long as they can deduce it from the information they already have, they must shout. Shouting happens simultaneously; they cannot wait to hear others shout and then continue reasoning. Then this round ends and the next round begins.

Other than this, these $n$ people have no communication at all. Now you are given everyone’s card numbers and all the information you announced. Find in which round each person shouts “Meltdown!” for the first time.

Input Format

The first line contains two positive integers $n,m$, representing the number of people and the number of rounds. The second line contains $n$ integers, representing the card numbers of people numbered $0$ to $n-1$. Then there are $m$ parts; part $i$ describes the information you announce in round $i$.

The first line of part $i$ contains a non-negative integer $k_i$, representing the number of pieces of information announced in round $i$. The next $k_i$ lines each start with a positive integer $p$, representing the size of the set, followed by $p$ distinct integers representing the IDs of all people in the set. The last integer is $c$, meaning that within this set, there exists a card whose number is $c$. The data guarantees that this information is correct.

Output Format

Output one line with $n$ integers, where the $i$-th integer represents the round number when person $i$ shouts “Meltdown!” for the first time. If they never shout “Meltdown!” throughout the whole game, output $-1$ for that person.

3 2
1 1 0
2
2 0 2 1
1 1 1
0

2 2 1

3 2
1 1 1
1
3 0 1 2 1
0

2 2 2

Hint

For $100\%$ of the data, $3\le n\le 16$，$\ 1\le m\le 100$，$0\le \sum k\le 2\times 10^3$。

Translated by ChatGPT 5