Problem D
Judo Championship

There are $n$ judokas participating in the judo championship. Each judoka is assigned a unique number from $1$ to $n$. There are currently $m$ scheduled matches. The $i$-th match is between judokas $u_ i$ and $v_ i$.

A judoka $s$ will say that they are stronger than judoka $t$ if at least one of the following conditions is satisfied:

• Judoka $s$ beats judoka $t$ in a match.

• Judoka $s$ beats judoka $u$ in a match, and judoka $u$ says that they are stronger than judoka $t$.

Unfortunately, by this definition, it is possible for both judokas $s$ and $t$ to say that they are stronger than the other. The ambiguity of the results of the judo championship is the number of pairs of judokas $s$ and $t$ such that judoka $s$ says that they are stronger than judoka $t$, and judoka $t$ says that they are stronger than judoka $s$.

Since the matches have not been played yet, you, the judge, wonder what’s the maximum possible ambiguity of the results of the judo championship. After all, you do not want the results to be too ambiguous!

Input

The first line contains two integers $n$ and $m$, denoting the number of judokas and the number of scheduled matches ($2 \leq n \leq 100\, 000$; $1 \leq m \leq 100\, 000$).

The next $m$ lines each contain two integers $u_ i$ and $v_ i$, denoting the judokas participating in the $i$-th match ($1 \leq u_ i, v_ i \leq n$; $u_ i \neq v_ i$).

Output

Output a binary string of length $m$, denoting a possible result of the scheduled matches which results in the maximum possible ambiguity. The $i$-th character of the string should be 0 if judoka $u_ i$ wins the $i$-th match, and 1 if judoka $v_ i$ wins the $i$-th match. You do not need to output the ambiguity of the results of the judo championship.

2 2
1 2
1 2

01

4 4
1 2
2 3
3 1
3 4

0000