## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] DFS Trees Codeforces Solution | Solution Codeforces

E. DFS Trees
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a connected undirected graph consisting of $n$ vertices and $m$ edges. The weight of the $i$-th edge is $i$.

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
Solution Click Below:-  👉
👇👇👇👇👇

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)

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

The first line of the input contains two integers $n$$m$ ($2\le n\le {10}^{5}$$n-1\le m\le 2\cdot {10}^{5}$) — the number of vertices and the number of edges in the graph.

Each of the following $m$ lines contains two integers ${u}_{i}$ and ${v}_{i}$ ($1\le {u}_{i},{v}_{i}\le n$${u}_{i}\ne {v}_{i}$), describing an undirected edge $\left({u}_{i},{v}_{i}\right)$ in the graph. The $i$-th edge in the input has weight $i$.

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

Output

You need to output a binary string $s$, where ${s}_{i}=1$ if findMST(i) creates an MST, and ${s}_{i}=0$ otherwise.