시간 제한메모리 제한제출정답맞은 사람정답 비율
3 초 256 MB0000.000%

문제

There are $n$ elephants living in the grassland, numbered from $1$ to $n$. Each elephant is either black or white. Unfortunately, you forgot all their individual colors.

You have observed these elephants for $m$ days. On the $i$-th day, there was a group of $k_i$ elephants $x_{i 1}, x_{i 2}, \ldots, x_{i k_i}$ hanging out. The thing you remember is that the absolute difference between the numbers of black and white elephants in each such group was at most $1$.

You have also noticed that the elephants have a pattern of social activities. For any three elephants $a, b, c$, if $a$ hangs out with $b$ on day $i$ and $a$ hangs out with $c$ on day $j$, then $a$ hangs out with $c$ on day $i$ or $a$ hangs out with $b$ on day $j$, or both.

Can you find a possible coloring for all elephants?

입력

The first line of input contains two integers $n$ and $m$, the number of elephants and the number of days ($1 \leq n \leq 10^6$, $0 \leq m \leq 10^6$).

Each of the following $m$ lines contains an integer $k_i$ followed by $k_i$ distinct integers $x_{i 1}, x_{i 2}, \ldots, x_{i k_i}$ ($1 \leq k_i \leq n$, $\sum k_i \leq 10^6$, $1 \leq x_{i j} \leq n$).

출력

Print a single line containing $n$ binary digits separated by spaces. The $i$-th digit denotes the color of the $i$-th elephant: $0$ for white or $1$ for black.

If there are several possible solutions, print any one of them.

If there are no solutions, print a single integer $-1$ instead.

예제 입력 1

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

예제 출력 1

1 0 1 1 0