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 
