405684: GYM102035 H Zuhair and the Dag

Memory limit is set to 4 mb.

Kilani has a directed graph with $$$n$$$ nodes and $$$m$$$ edges, where there could be at most one edge between any pair of nodes, and it contains no self loops. It doesn't have to be a connected graph.

Kilani thinks that Zuhair is a very smart person so he decided to give him a problem on that graph.

Zuhair should choose a sub-set of edges and flip them, so if the edges were going from node $$$u$$$ to node $$$v$$$, it becomes from node $$$v$$$ to $$$u$$$.

He should choose a sub-set of edges in order to make the graph a DAG.

D$$$_{iricted}$$$A$$$_{cyclic}$$$G$$$_{raph}$$$ is a directed graph without any cycles.

First line contains 2 integers $$$n$$$ and $$$m$$$, which are the number of nodes and the number of edges $$$(2 \leq n \leq 10 ^{6})$$$ $$$(1 \leq m \leq 10 ^{6})$$$. The next $$$m$$$ lines , will contains 2 integers for each, $$$u$$$ and $$$v$$$ $$$(1 \leq u , v \leq n)$$$ $$$(u \neq v)$$$, which means that there is a one way edge goes from node $$$u$$$ to node $$$v$$$.

you should print a string with length $$$m$$$, the $$$i_{th}$$$ character should be '0' if you want the $$$i_{th}$$$ edge to go from node $$$u$$$ to $$$v$$$, and '1' to go from $$$v$$$ to $$$u$$$.

4 4
1 2
2 3
3 4
4 1

0100

First Sample :

Before flipping

After flipping