*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$""_(i r i c t e d)$A$""_(c y c l i c)$G$""_(r a p h)$ 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 <= n <= 10^6)$ $(1 <= m <= 10^6)$. The next $m$ lines , will contains 2 integers for each, $u$ and $v$ $(1 <= u, v <= n)$ $(u eq.not 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_{t h}$ character should be '0' if you want the $i_{t h}$ edge to go from node $u$ to $v$, and '1' to go from $v$ to $u$.
First Sample :
Before flipping
After flipping
## Input
First line contains 2 integers $n$ and $m$, which are the number of nodes and the number of edges $(2 <= n <= 10^6)$ $(1 <= m <= 10^6)$. The next $m$ lines , will contains 2 integers for each, $u$ and $v$ $(1 <= u, v <= n)$ $(u eq.not v)$, which means that there is a one way edge goes from node $u$ to node $v$.
## Output
you should print a string with length $m$, the $i_(t h)$ character should be '0' if you want the $i_(t h)$ edge to go from node $u$ to $v$, and '1' to go from $v$ to $u$.
[samples]
## Note
First Sample :Before flipping After flipping
**Definitions**
Let $ G = (V, E) $ be a directed graph with:
- $ V = \{1, 2, \dots, n\} $, $ n \in \mathbb{Z}^+ $, $ 2 \leq n \leq 10^6 $: set of nodes.
- $ E = \{e_1, e_2, \dots, e_m\} $, $ m \in \mathbb{Z}^+ $, $ 1 \leq m \leq 10^6 $: set of directed edges, where each $ e_i = (u_i, v_i) $, $ u_i, v_i \in V $, $ u_i \ne v_i $, and no self-loops or multiple edges between same pair.
Let $ x_i \in \{0, 1\} $ for $ i = 1, \dots, m $: binary variable indicating whether edge $ e_i $ is flipped:
- $ x_i = 0 $: edge remains $ u_i \to v_i $,
- $ x_i = 1 $: edge is flipped to $ v_i \to u_i $.
Let $ G' = (V, E') $ be the resulting directed graph after applying flips $ \{x_i\} $, where each edge $ e_i $ becomes $ (u_i, v_i) $ if $ x_i = 0 $, or $ (v_i, u_i) $ if $ x_i = 1 $.
**Constraints**
1. $ G' $ must be a DAG: it contains no directed cycles.
**Objective**
Find a binary string $ s = x_1 x_2 \dots x_m \in \{0,1\}^m $ such that $ G' $ is a DAG.