A directed graph contains n nodes numbered from 1 to n and n - 1 directed edges, forming a tree.

Choose any node as the root. Every edge must ultimately point away from the root. You may reverse the direction of any edge, where each reversal costs 1.

Find the minimum possible number of edge reversals over all possible choices of the root.

Function Signature

int getMinInversions(int g_nodes,
                     vector<int> g_from,
                     vector<int> g_to);

Parameters

• g_nodes: number of nodes.
• g_from[i]: starting node of the i-th directed edge.
• g_to[i]: ending node of the i-th directed edge.

Returns

• int: minimum number of edge reversals required.

Example

g_nodes = 4
g_from = [1, 2, 3]
g_to   = [4, 4, 4]

Output:
2

Explanation:

Choosing node 2 as the root requires reversing edges (1 → 4) and (3 → 4).