Hide

# Problem JJudo 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.

Sample Input 1 Sample Output 1
2 2
1 2
1 2

01

Sample Input 2 Sample Output 2
4 4
1 2
2 3
3 1
3 4

0000