# DFS Trees Solution Codeforces

## DFS Trees Solution Codeforces

You are given a connected undirected graph consisting of nn vertices and mm edges. The weight of the ii-th edge is ii.

Here is a wrong algorithm of finding a minimum spanning tree (MST) of a graph:

vis := an array of length n
s := a set of edges

function dfs(u):
vis[u] := true
iterate through each edge (u, v) in the order from smallest to largest edge weight
if vis[v] = false
add edge (u, v) into the set (s)
dfs(v)

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

Each of the calls findMST(1)findMST(2), …, findMST(n) gives you a spanning tree of the graph. Determine which of these trees are minimum spanning trees.

## Input DFS Trees Solution Codeforces

The first line of the input contains two integers nnmm (2n1052≤n≤105n1m2105n−1≤m≤2⋅105) — the number of vertices and the number of edges in the graph.

Each of the following mm lines contains two integers uiui and vivi (1ui,vin1≤ui,vi≤nuiviui≠vi), describing an undirected edge (ui,vi)(ui,vi) in the graph. The ii-th edge in the input has weight ii.

It is guaranteed that the graph is connected and there is at most one edge between any pair of vertices.

### Output DFS Trees Solution Codeforces

You need to output a binary string ss, where si=1si=1 if findMST(i) creates an MST, and si=0si=0 otherwise.

Examples
input

Copy
5 5
1 2
3 5
1 3
3 2
4 2

output

Copy
01111

input

Copy
10 11
1 2
2 5
3 4
4 2
8 1
4 5
10 5
9 5
8 2
5 7
4 6

output

Copy
0011111011


## Note DFS Trees Solution Codeforces

Here is the graph given in the first example.

There is only one minimum spanning tree in this graph. A minimum spanning tree is (1,2),(3,5),(1,3),(2,4)(1,2),(3,5),(1,3),(2,4) which has weight 1+2+3+5=111+2+3+5=11.

Here is a part of the process of calling findMST(1):

• reset the array vis and the edge set s;
• calling dfs(1);
• vis[1] := true;
• iterate through each edge (1,2),(1,3)(1,2),(1,3);
• add edge (1,2)(1,2) into the edge set s, calling dfs(2):
• vis[2] := true
• iterate through each edge (2,1),(2,3),(2,4)(2,1),(2,3),(2,4);
• because vis[1] = true, ignore the edge (2,1)(2,1);
• add edge (2,3)(2,3) into the edge set s, calling dfs(3):

In the end, it will select edges (1,2),(2,3),(3,5),(2,4)(1,2),(2,3),(3,5),(2,4) with total weight 1+4+2+5=12>111+4+2+5=12>11, so findMST(1) does not find a minimum spanning tree.

It can be shown that the other trees are all MSTs, so the answer is 01111.