After a severe earthquake, the city government has collected connectivity data of its emergency communication network.
There are `N` emergency stations in the city, numbered from `0` to `N-1`. Some pairs of stations are connected by communication links. The collected network can be represented as an undirected graph, where each station is a vertex and each communication link is an edge.
The city government would like to analyze the connectivity of the emergency communication network using Depth-First Search (DFS).
Your task is to write a C/C++ program to perform DFS on the given connectivity data and determine the total number of connected components. In addition, for diagnostic purposes your program should also output the DFS visiting order.
The DFS follows these rules:
1. Start from vertex `0`.
2. Mark the current vertex as visited.
3. If there are multiple unvisited adjacent vertices, always visit the vertex with the smallest number first.
4. Continue the DFS until there are no unvisited adjacent vertices, then backtrack.
5. If there are still unvisited vertices after the current connected component is finished, start a new DFS from the smallest-numbered unvisited vertex.
6. Continue until all vertices have been visited.
There is no restriction on the use of the C/C++ Standard Library.
1 <= N <= 100000
0 <= E <= 200000
0 <= u, v < N
The first line contains an integer `M`, representing the number of graphs.
For each graph, the first line contains two integers `N` and `E`, representing the number of vertices and the number of edges.
The following `E` lines each contain two integers `u` and `v`, indicating that there is an undirected edge between vertex `u` and vertex `v`. There are no self-loops or duplicate edges.
The first line should contain the vertices in the order they are visited by DFS, separated by spaces.
The second line should contain one integer representing the number of connected components