K2. MST(a.k.a. Most Stupid Technique)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

During a programming contest, Mr. Search Tree (a.k.a. MST) forgot how to implement Kruskal's and Prim's algorithms. In a moment of desperation, he wrote a DFS that always follows the smallest available edge first. Strangely enough, it passed.

Now he wonders: for which starting nodes does his "Most Stupid Technique" accidentally produce a correct minimum spanning tree$$$^\dagger$$$ ?

Formally, given a connected undirected graph with $$$n$$$ nodes and $$$m$$$ edges, the $$$i$$$-th edge has weight $$$i$$$, and here is the algorithm he used:

vis := array of n booleans
s := set of edges

function dfs(u):
    vis[u] := true
    for each edge (u, v) connected to u in increasing order of edge weight:
        if not vis[v]:
            add edge (u, v) to s
            dfs(v)

function findMST(u):
    reset vis to all false
    clear the edge set s
    dfs(u)
    return s

In other words, findMST(u) performs a DFS starting from vertex $$$u$$$, always choosing the smallest-weight unvisited edge from the current node and includes it in the tree.

Although this always produces a spanning tree, it doesn't always yield a minimum one.

Your task is to determine, for each node $$$i$$$ from $$$1$$$ to $$$n$$$, whether findMST(i) returns a minimum spanning tree.

$$$^\dagger$$$ A minimum spanning tree (MST) of a connected undirected graph is a subset of the edges that forms a tree connecting all the vertices and has the minimum possible total edge weight among all such trees.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^5, n - 1 \leq m \leq 2 \cdot 10^5$$$), denoting the number of vertices and edges.

For the following $$$m$$$ lines, the $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n, u_i \neq v_i$$$), denoting an undirected edge between $$$u_i$$$ and $$$v_i$$$.

The $$$i$$$-th edge ($$$1$$$-based index in input) has weight $$$i$$$.

It's guaranteed that the graph is connected and contains no duplicate edges.

Output

Output one line containing a binary string of length $$$n$$$.

The i-th character should be '$$$1$$$'(without quotes) if the tree produced by running the algorithm above starting from node i is a minimum spanning tree, and '$$$0$$$'(without quotes) otherwise.

Examples
Input
5 5
1 2
1 3
2 3
2 4
2 5
Output
01111
Input
8 9
1 2
6 7
3 7
3 5
5 8
1 4
2 4
2 3
1 6
Output
00010100
Note

The sample case is shown below:

The graph for the sample

The only minimum spanning tree (MST) of this graph includes the edges with weights $$$1$$$, $$$2$$$, $$$4$$$, and $$$5$$$, which has a total edge weight of 12.

We simulate the algorithm findMST(u) for each $$$u$$$ from $$$1$$$ to $$$5$$$:

  • findMST(1) starts from node $$$1$$$ and visits edge $$$1$$$ first (to node $$$2$$$). Then at node $$$2$$$, the smallest unvisited adjacent edge is edge $$$3$$$ (to node $$$3$$$), so it is selected instead of edge $$$2$$$. As a result, edge $$$3$$$ (which has higher weight than edge $$$2$$$) is included in the result, and the resulting tree includes the edges with weights $$$1$$$, $$$3$$$, $$$4$$$, and $$$5$$$, which has a total edge weight of 13; so it doesn't construct the MST of the graph.
  • findMST(2), findMST(3), findMST(4), and findMST(5) all happen to construct the correct MST.

Thus, the output is 01111.