DFS Trees
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 ns := a set of edgesfunction 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.
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)$$$ which has weight $$$1+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)$$$;  add edge $$$(1,2)$$$ into the edge set s, calling dfs(2):   vis[2] := true  iterate through each edge $$$(2,1),(2,3),(2,4)$$$;  because vis[1] = true, ignore the edge $$$(2,1)$$$;  add edge $$$(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)$$$ with total weight $$$1+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.
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 $$$(u_i,v_i)$$$ 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.
You need to output a binary string $$$s$$$, where $$$s_i=1$$$ if findMST(i) creates an MST, and $$$s_i = 0$$$ otherwise.
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (s, t) = (get_root(s), get_root(t))
    if s == t:
        return
    if rank[s] < rank[t]:
        (s, t) = (t, s)
    if rank[s] == rank[t]:
        rank[s] += 1
    root[t] = s
    size[s] += size[t]
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False

def get_size(s):
    return size[get_root(s)]

def make_graph(n, m):
    s = [0] * (n + 3)
    for i in x:
        s[i + 2] += 1
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G = [0] * (2 * m)
    for i in range(2 * m):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)

def bfs(s):
    q = [s]
    dist = [inf] * (n + 1)
    dist[s] = 0
    parent = [-1] * (n + 1)
    for k in range(n):
        i = q[k]
        di = dist[i]
        for v in range(s0[i], s0[i + 1]):
            j = G[v]
            if dist[j] == inf:
                q.append(j)
                dist[j] = di + 1
                parent[j] = i
    return (q, dist, parent)

def f(u, v):
    return u * (n + 1) + v
(n, m) = map(int, input().split())
root = [i for i in range(n + 1)]
rank = [1 for _ in range(n + 1)]
size = [1 for _ in range(n + 1)]
(x, y) = ([], [])
for _ in range(m):
    (u, v) = map(int, input().split())
    if not same(u, v):
        unite(u, v)
        x.append(u)
        x.append(v)
    else:
        y.append(u)
        y.append(v)
(G, s0) = make_graph(n, n - 1)
inf = pow(10, 9) + 1
(p, dist, parent) = bfs(1)
l = (n + 1).bit_length()
pow2 = [1]
for _ in range(l):
    pow2.append(2 * pow2[-1])
dp0 = [0] * ((n + 1) * l)
for i in range(2, n + 1):
    dp0[i] = parent[i]
for i in range(1, l):
    for j in range(2, n + 1):
        dp0[f(i, j)] = dp0[f(i - 1, dp0[f(i - 1, j)])]
dp = [0] * (n + 1)
m = len(y) // 2
for i in range(m):
    (u, v) = (y[2 * i], y[2 * i + 1])
    if dist[u] < dist[v]:
        (u, v) = (v, u)
    w = u
    (d, i) = (dist[u] - dist[v] - 1, 0)
    while d > 0:
        if not d & pow2[i]:
            i += 1
            continue
        w = dp0[f(i, w)]
        d ^= pow2[i]
    if dist[w] ^ dist[v] and parent[w] == v:
        dp[1] += 1
        dp[w] -= 1
        dp[u] += 1
    else:
        dp[u] += 1
        dp[v] += 1
for i in p[1:]:
    dp[i] += dp[parent[i]]
ans = ['1' if dp[i] == m else '0' for i in range(1, n + 1)]
sys.stdout.write(''.join(ans))
import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m) = map(int, input().split())
EDGE = [tuple(map(int, input().split())) for i in range(m)]
Group = [i for i in range(n + 1)]
Nodes = [1] * (n + 1)

def find(x):
    while Group[x] != x:
        x = Group[x]
    return x

def Union(x, y):
    if find(x) != find(y):
        if Nodes[find(x)] < Nodes[find(y)]:
            Nodes[find(y)] += Nodes[find(x)]
            Nodes[find(x)] = 0
            Group[find(x)] = find(y)
        else:
            Nodes[find(x)] += Nodes[find(y)]
            Nodes[find(y)] = 0
            Group[find(y)] = find(x)
USE = [0] * m
for i in range(m):
    (x, y) = EDGE[i]
    if find(x) == find(y):
        USE[i] = 0
    else:
        USE[i] = 1
        Union(x, y)
E = [[] for i in range(n + 1)]
OK = [0] * (n + 1)
for i in range(m):
    if USE[i] == 1:
        (x, y) = EDGE[i]
        E[x].append(y)
        E[y].append(x)
        OK[x] = 1
        OK[y] = 1
N = n + 1
ROOT = 1
QUE = [ROOT]
Parent = [-1] * (N + 1)
Height = [-1] * (N + 1)
Parent[ROOT] = N
Height[ROOT] = 0
Child = [[] for i in range(N + 1)]
TOP_SORT = []
while QUE:
    x = QUE.pop()
    TOP_SORT.append(x)
    for to in E[x]:
        if Parent[to] == -1:
            Parent[to] = x
            Height[to] = Height[x] + 1
            Child[x].append(to)
            QUE.append(to)
Children = [1] * (N + 1)
for x in TOP_SORT[::-1]:
    Children[Parent[x]] += Children[x]
USE = [0] * N
Group = [i for i in range(N)]
for x in TOP_SORT:
    USE[x] = 1
    MAX_children = 0
    select_node = 0
    for to in E[x]:
        if USE[to] == 0 and Children[to] > MAX_children:
            select_node = to
            MAX_children = Children[to]
    for to in E[x]:
        if USE[to] == 0 and to == select_node:
            Group[to] = Group[x]

def LCA(a, b):
    while Group[a] != Group[b]:
        if Children[Parent[Group[a]]] < Children[Parent[Group[b]]]:
            a = Parent[Group[a]]
        else:
            b = Parent[Group[b]]
    if Children[a] > Children[b]:
        return a
    else:
        return b
Parents = [Parent]
for i in range(30):
    X = [-1] * (N + 1)
    for i in range(N + 1):
        X[i] = Parents[-1][Parents[-1][i]]
    Parents.append(X)

def LCA_mae(x, y):
    while Height[x] > Height[y] + 1:
        for i in range(30):
            k = Parents[i][x]
            if k == -1 or k >= n or Height[k] <= Height[y]:
                x = Parents[i - 1][x]
                break
    return x
UP = [0] * (N + 1)
DOWN = [0] * (N + 1)
score = 0
for (x, y) in EDGE:
    if OK[x] == 1 and OK[y] == 1:
        if Parent[x] == y or Parent[y] == x:
            continue
        k = LCA(x, y)
        if k == x:
            DOWN[y] += 1
            k = LCA_mae(y, x)
            DOWN[k] -= 1
        elif k == y:
            DOWN[x] += 1
            k = LCA_mae(x, y)
            DOWN[k] -= 1
        else:
            score += 1
            DOWN[x] += 1
            DOWN[y] += 1
for x in TOP_SORT[1:]:
    DOWN[x] += DOWN[Parent[x]]
for x in TOP_SORT[1:][::-1]:
    UP[Parent[x]] += UP[x]
ANS = [0] * N
for i in range(N):
    if OK[i] == 1 and UP[i] + DOWN[i] == score:
        ANS[i] = 1
print(''.join(map(str, ANS[1:N])))
import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m) = map(int, input().split())
EDGE = [tuple(map(int, input().split())) for i in range(m)]
Group = [i for i in range(n + 1)]
Nodes = [1] * (n + 1)

def find(x):
    while Group[x] != x:
        x = Group[x]
    return x

def Union(x, y):
    if find(x) != find(y):
        if Nodes[find(x)] < Nodes[find(y)]:
            Nodes[find(y)] += Nodes[find(x)]
            Nodes[find(x)] = 0
            Group[find(x)] = find(y)
        else:
            Nodes[find(x)] += Nodes[find(y)]
            Nodes[find(y)] = 0
            Group[find(y)] = find(x)
USE = [0] * m
for i in range(m):
    (x, y) = EDGE[i]
    if find(x) == find(y):
        USE[i] = 0
    else:
        USE[i] = 1
        Union(x, y)
E = [[] for i in range(n + 1)]
OK = [0] * (n + 1)
for i in range(m):
    if USE[i] == 1:
        (x, y) = EDGE[i]
        E[x].append(y)
        E[y].append(x)
        OK[x] = 1
        OK[y] = 1
N = n + 1
ROOT = 1
QUE = [ROOT]
Parent = [-1] * (N + 1)
Height = [-1] * (N + 1)
Parent[ROOT] = N
Height[ROOT] = 0
Child = [[] for i in range(N + 1)]
TOP_SORT = []
while QUE:
    x = QUE.pop()
    TOP_SORT.append(x)
    for to in E[x]:
        if Parent[to] == -1:
            Parent[to] = x
            Height[to] = Height[x] + 1
            Child[x].append(to)
            QUE.append(to)
Children = [1] * (N + 1)
for x in TOP_SORT[::-1]:
    Children[Parent[x]] += Children[x]
USE = [0] * N
Group = [i for i in range(N)]
for x in TOP_SORT:
    USE[x] = 1
    MAX_children = 0
    select_node = 0
    for to in E[x]:
        if USE[to] == 0 and Children[to] > MAX_children:
            select_node = to
            MAX_children = Children[to]
    for to in E[x]:
        if USE[to] == 0 and to == select_node:
            Group[to] = Group[x]

def LCA(a, b):
    while Group[a] != Group[b]:
        if Children[Parent[Group[a]]] < Children[Parent[Group[b]]]:
            a = Parent[Group[a]]
        else:
            b = Parent[Group[b]]
    if Children[a] > Children[b]:
        return a
    else:
        return b
Parents = [Parent]
for i in range(30):
    X = [-1] * (N + 1)
    for i in range(N + 1):
        X[i] = Parents[-1][Parents[-1][i]]
    Parents.append(X)

def LCA_mae(x, y):
    while Height[x] > Height[y] + 1:
        for i in range(30):
            k = Parents[i][x]
            if k == -1 or k >= n or Height[k] <= Height[y]:
                x = Parents[i - 1][x]
                break
    return x
DOWN = [0] * (N + 1)
score = 0
for (x, y) in EDGE:
    if OK[x] == 1 and OK[y] == 1:
        if Parent[x] == y or Parent[y] == x:
            continue
        k = LCA(x, y)
        if k == x:
            DOWN[y] += 1
            k = LCA_mae(y, x)
            DOWN[k] -= 1
        elif k == y:
            DOWN[x] += 1
            k = LCA_mae(x, y)
            DOWN[k] -= 1
        else:
            score += 1
            DOWN[x] += 1
            DOWN[y] += 1
for x in TOP_SORT[1:]:
    DOWN[x] += DOWN[Parent[x]]
ANS = [0] * N
for i in range(N):
    if OK[i] == 1 and DOWN[i] == score:
        ANS[i] = 1
print(''.join(map(str, ANS[1:N])))