Problem Statement

mai has an undirected graph consisting of $n$ vertices and $m$ edges.

Each vertex of the graph is assigned a distinct non-negative integer from $0$ to $n-1$.
The $j$-th edge is incident to the vertices $a_j$ and $b_j$.

When Maiha was thinking of buying edges from mai, mai made the following proposal.

• The price of the vertex assigned the non-negative integer $i$ is $2^i$ yen.
• When you buy a vertex, the edges incident to that vertex come with it as a set.
• Purchased vertices and edges are removed from mai's graph and are never replenished.
• You cannot buy edges alone.

Maiha is hungry for edges, so he wants to buy all the edges mai has.
His wealth is infinite, so he can buy a vertex no matter how expensive it is, but he wants to keep the cost as low as possible.

Output the minimum amount Maiha must pay in binary.

Input

$n$ $m$
$a_1$ $b_1$
$a_2$ $b_2$
...
$a_m$ $b_m$

$ 2 \le n \le 100000$
$\lceil n/2 \rceil \le m \le \min \{100000 ,n(n-1) / 2 \}$
$0 \le a_i \lt b_i \le n-1$
No graph containing a vertex that is not incident to any edge is given.
There are no multiple edges (if $i \neq j$, then $a_i \neq a_j$ or $b_i \neq b_j$ holds).

A test case's file name may indicate additional constraints on $n$ and $m$ in the form "s#{number}".
The corresponding additional constraints are as follows.

• s12 : $n \le 12$ holds
• s1000 : $n \le 1000$ and $m \le 1000$ hold
• s100000 : $n$ or $m$ is extremely close to the upper limit of the constraints

Output

Output in binary the minimum amount Maiha must pay to obtain all the edges.
Do not output extra 0s (for example, 0010).

Print a newline at the end.

Sample

4 5
0 1
0 2
0 3
1 2
2 3

101

6 5
0 4
1 2
1 5
2 5
3 4

1111

10 15
0 1
0 2
0 3
1 4
1 8
2 5
2 9
3 4
3 5
4 6
5 7
6 8
6 7
7 9
8 9

110011101