Find minimum reversals to orient edges away from root

You are given a connected graph with n nodes labeled 0..n-1 and n-1 directed edges. If you ignore edge directions, the edges form a tree.

Each directed edge is given as a pair (u, v) meaning the edge currently points from u to v.

You are also given a root node r.

In the rooted tree (rooted at r), every edge should point away from the root (i.e., from parent to child). You may reverse the direction of any edge; each reversal costs 1.

Return the minimum total number of edge reversals required so that, after reversals, all edges in the tree point away from r.

Input

• Integer n
• List of directed edges edges, length n-1, each as (u, v)
• Integer root r

Output

• Integer: minimum number of reversals

Example

Suppose n = 5, r = 0, and edges are:

• (1, 0), (0, 2), (3, 2), (3, 4)

Ignoring directions, the tree is 0-1, 0-2, 2-3, 3-4. To make all edges point away from 0, edges (1,0) and (3,2) must be reversed, so the answer is 2.

Constraints (typical)

• 1 <= n <= 2e5
• The undirected version of edges is a tree
• Nodes are 0..n-1

Note: With large n, recursive DFS may overflow the call stack in some languages; an iterative traversal may be required.