Probability of Correct DFS Shortest Paths

We are given an undirected unweighted graph with (n) vertices and (m) edges. Consider the following randomized depth‐first search (DFS) algorithm that computes an array (dis[\cdot]) claiming to be the shortest‐path distances from vertex 1. The pseudocode is given below in LaTeX (with the randomization explained):

[ \begin{array}{lcl} \texttt{solve():} && \[5pt] \quad \text{for } i=1 \text{ to } n:&\quad dis[i] = -1,; vis[i] = 0, \[5pt] \quad &\quad dis[1] = 0, \[5pt] \quad &\quad dfs(1) ; .\[5pt] \end{array} ]

[ \begin{array}{lcl} \texttt{dfs(u):} && \[5pt] \quad vis[u] = 1, \[5pt] \quad \text{Let } S = { ;v ;:; (u, v) \in E \text{ and } vis[v]=0 }, \[5pt] \quad \text{randomly permute } S ;\bigl(\text{each ordering with probability }\frac{1}{|S|!}\bigr), \[5pt] \quad \text{for each } v \text{ in } S: &\quad {\quad dis[v] = dis[u] + 1 \quad \text{and} \quad dfs(v)} ; .\[5pt] \end{array} ]

The array (dis[\cdot]) is said to be completely correct if for every vertex (i), (dis[i]) equals the true shortest‐path distance from vertex 1 to (i) (with the convention that if 1 cannot reach (i) then the distance is (-1)).

A careful analysis shows that because the DFS does not “correct” a vertex’s distance once it is set, the only way that the DFS can return the correct distances on the connected component containing 1 is if the DFS traverses the vertices in exactly the same way as a breadth‐first search (BFS) would. In other words, the DFS must end up producing a DFS tree that exactly coincides with the unique BFS tree of the reachable component from 1. It can be proved that this happens if and only if the subgraph induced on the set (R) of vertices reachable from 1 is a tree (i.e. it contains exactly (|R| - 1) edges). (Notice that edges in the graph not lying in the BFS tree – for example, an edge connecting two vertices at the same level or an edge connecting a vertex with one at a non‐parent level – will necessarily cause the DFS to “mis‐route” and assign an incorrect (dis[\cdot]) value.)

Your task is to compute the probability that a call to (solve()) yields a completely correct (dis[\cdot]). Under the above analysis, the answer is (1) if the connected component of vertex 1 (i.e. the set (R)) induces a tree and (0) otherwise.

The input format is as follows. The first line contains two integers (n) and (m). Each of the next (m) lines contains two integers (u) and (v) (with (1 \le u, v \le n) and (u \ne v)), representing an undirected edge.

Input Example:

3 3
1 2
2 3
1 3

In the above example, the reachable component from 1 (namely, vertices 1, 2 and 3) has 3 edges, which is more than (3-1=2); hence a DFS (using the above randomized strategy) will never yield the correct shortest–path array, and the answer is 0.

Output: Output a single number: 1 if the DFS returns the correct (dis[\cdot]) (i.e. the reachable component forms a tree), or 0 otherwise.

Note: Vertices that are not reachable from 1 are expected to have (dis[i] = -1) (which is considered correct). Only the reachable part can be affected by the DFS order.

inputFormat

The first line contains two integers (n) and (m) (for example, (1 \le n \le 10^5) and (0 \le m \le 10^5)). Each of the next (m) lines contains two integers (u) and (v) (with (1 \le u, v \le n) and (u \ne v)), representing an undirected edge.

outputFormat

Output a single number: 1 if the DFS algorithm returns the correct shortest–path distances (i.e. the subgraph of vertices reachable from 1 is a tree), or 0 otherwise.

sample

3 2
1 2
2 3

1