Given an undirected graph $G = (V, E)$, partition $V$ into two sets $S$ and $T$ such that $S \cap T = \emptyset$ and $S \cup T = V$. Define the cut as:

$$Cut(S, T) = \{e = (x, y) \in E \mid x \in S, y \in T\}$$

Find $S$ and $T$ such that $|Cut(S, T)| \geq \frac{1}{2}|E|$. If there are multiple solutions, output any one of them.

Input

The first line contains two integers $n$ and $m$, representing the number of vertices and edges in $G$, respectively.

Each of the next $m$ lines contains two integers $x$ and $y$, representing an edge.

Output

Output a single line containing $n$ digits (0 or 1). A 1 indicates that the $i$-th vertex is in set $S$, otherwise it is in set $T$.

It is guaranteed that a solution always exists; output any valid solution.

Constraints

It is guaranteed that there are no self-loops. Note that multiple edges must be counted repeatedly.

• For 30% of the data, $n \leq 20$.
• For another 20% of the data, $G$ is a bipartite graph.
• For 100% of the data, $n \leq 10^5$, $m \leq 2 \times 10^5$.

Examples

Input 1

4 6
1 2
1 3
1 4
2 3
2 4
3 4

Output 1

0011