Algorithm Class - Depth-First Search 5

Seojun is once again working as a teaching assistant for the depth-first search (DFS) class. Let us check through a problem whether the students understood what his father taught in class.

An undirected graph with N vertices and M edges is given. The vertices are numbered 1 to N, and every edge has weight 1. The tree produced by depth-first search starting from vertex R is called the depth-first search tree. Let di* be the depth of node i in the depth-first search tree. The depth of the starting vertex R is 0, and the depth of an unvisited node is -1. When nodes are visited by depth-first search starting from vertex R, let ti* be the visit order of node i. The visit order of the starting vertex is 1, and the visit order of a node that cannot be reached from the starting vertex is 0. Find the sum of di* × ti* over all nodes.

The pseudocode for depth-first search is as follows. Adjacent vertices are visited in ascending order.

dfs(V, E, R) {  # V : vertex set, E : edge set, R : starting vertex
    visited[R] <- YES;  # mark starting vertex R as visited.
    for each x ∈ E(R)  # E(R) : set of vertices adjacent to vertex R. (visit in ascending vertex number order)
        if (visited[x] = NO) then dfs(V, E, x);
}

The first line gives the number of vertices N (5 ≤ N ≤ 100,000), the number of edges M (1 ≤ M ≤ 200,000), and the starting vertex R (1 ≤ R ≤ N).

The next M lines give edge information u v, representing an undirected edge of weight 1 between vertex u and vertex v. (1 ≤ u < v ≤ N, u ≠ v) Every (u, v) pair is distinct.

On the first line, print the sum of di* × ti* over all nodes.