Background

Warning: Abusing this problem to hack the judge will result in an account ban.

Problem Description

You are given a rooted tree with $n$ vertices, and $m$ ordered pairs $(x_i,y_i)$, where $x_i,y_i$ are vertices of the tree.

For vertices $a,b$ in the tree, define $D(a,b)$ as the number of vertices that are in the subtree rooted at $a$, but not in the subtree rooted at $b$.

You need to find the minimum spanning tree of the complete graph whose vertices are these ordered pairs. The edge weight between $(x_i,y_i)$ and $(x_j,y_j)$ is $D(x_i,x_j)+D(x_j,x_i)+D(y_i,y_j)+D(y_j,y_i)$.

Input Format

The first line contains two integers $n,m$.

The next line contains $n-1$ integers. The $i$-th integer denotes the parent $f_{i+1}$ of node $i+1$, and it is guaranteed that $f_{i+1}< i+1$.

Then follow $m$ lines. The $i$-th line contains two integers $x_i,y_i$, representing a given ordered pair.

Output Format

Output one integer, the sum of edge weights of the minimum spanning tree.

5 4
1 2 3 3
3 5
2 2
5 2
2 5

7

Hint

Explanation of the sample:

The minimum spanning tree contains edges $(1,4,1),(2,3,3),(2,4,3)$. Each triple means: the index of the first ordered pair, the index of the second ordered pair, and the edge weight. The total weight is $7$.

Constraints:

For $10\%$ of the testdata, $1\le n,m\le 1000$.

For another $10\%$ of the testdata, $1\le m\le 2\times 10^4$.

For another $10\%$ of the testdata, $1\le m\le 5\times 10^4$.

For another $20\%$ of the testdata, $m=n^2$, and all ordered pairs are distinct.

For another $10\%$ of the testdata, for all $i=2\cdots n$, $f_i=i-1$.

For another $10\%$ of the testdata, for all $i=2\cdots n$, $f_i=1$.

For $100\%$ of the testdata, $1\le n\le 10^6,1\le m\le 10^5$. For all $i=1,2,\dots n-1$, $1\le f_{i+1}<i+1$. For all $i=1,2,\dots m$, $1\le x_i,y_i\le n$.

Translated by ChatGPT 5