CF1707C 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](https://en.wikipedia.org/wiki/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.
                            

N/A

N/A

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.