Problem J
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.
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 