On vous donne un arbre enraciné à $n$ sommets, ainsi que $m$ couples $(x_i,y_i)$, où $x_i,y_i$ sont des sommets de l'arbre.

Pour deux sommets $a,b$ de l'arbre, on définit $D(a,b)$ comme le nombre de sommets appartenant au sous-arbre enraciné en $a$, mais pas au sous-arbre enraciné en $b$.

Vous devez trouver un arbre couvrant de poids minimal du graphe complet dont les sommets sont ces couples, où le poids de l'arête entre $(x_i,y_i)$ et $(x_j,y_j)$ est $D(x_i,x_j)+D(x_j,x_i)+D(y_i,y_j)+D(y_j,y_i)$.

Entrée

Les données sont lues sur l'entrée standard.

La première ligne contient deux nombres représentant $n,m$.

La ligne suivante contient $n-1$ nombres. Le $i$-ème nombre représente le parent $f_{i+1}$ du sommet numéro $i+1$. Il est garanti que $f_{i+1}< i+1$.

Les $m$ lignes suivantes décrivent les couples donnés : la $i$-ème ligne contient deux nombres $x_i,y_i$.

Sortie

Écrivez sur la sortie standard.

Affichez un entier représentant la somme des poids des arêtes d'un arbre couvrant de poids minimal.

Exemples

Entrée 1

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

Sortie 1

7

Remarque

L'arbre couvrant de poids minimal contient les arêtes $(1,4,1),(2,3,3),(2,4,3)$. Chaque triplet indique le numéro du premier couple, le numéro du second couple et le poids de l'arête. La somme des poids est $7$.

Sous-tâches

Pour $10\%$ des données, $1\le n,m\le 1000$.

Pour $10\%$ supplémentaires des données, $1\le m\le 2\times 10^4$.

Pour $10\%$ supplémentaires des données, $1\le m\le 5\times 10^4$.

Pour $20\%$ supplémentaires des données, $m=n^2$ et tous les couples sont distincts.

Pour $10\%$ supplémentaires des données, pour tout $i=2\cdots n$, $f_i=i-1$.

Pour $10\%$ supplémentaires des données, pour tout $i=2\cdots n$, $f_i=1$.

Pour $100\%$ des données, $1\le n\le 10^6,1\le m\le 10^5$. Pour tout $i=1,2,\dots n-1$, $1\le f_{i+1} < i+1$. Pour tout $i=1,2,\dots m$, $1\le x_i,y_i\le n$.