Gegeben sind ein verwurzelter Baum mit $n$ Knoten und $m$ geordnete Paare $(x_i,y_i)$, wobei $x_i,y_i$ Knoten des Baums sind.

Für Knoten $a,b$ des Baums sei $D(a,b)$ die Anzahl der Knoten, die im Teilbaum mit Wurzel $a$, aber nicht im Teilbaum mit Wurzel $b$ liegen.

Bestimme einen minimalen Spannbaum des vollständigen Graphen, dessen Knoten diese geordneten Paare sind. Das Gewicht der Kante zwischen $(x_i,y_i)$ und $(x_j,y_j)$ ist $D(x_i,x_j)+D(x_j,x_i)+D(y_i,y_j)+D(y_j,y_i)$.

Eingabe

Die Daten werden von der Standardeingabe gelesen.

Die erste Zeile enthält zwei Zahlen $n,m$.

Die nächste Zeile enthält $n-1$ Zahlen. Die $i$-te Zahl gibt den Vater $f_{i+1}$ des Knotens mit der Nummer $i+1$ an. Es gilt $f_{i+1}< i+1$.

Es folgen $m$ Zeilen. Die $i$-te Zeile enthält zwei Zahlen $x_i,y_i$, die ein gegebenes geordnetes Paar beschreiben.

Ausgabe

Schreibe die Ausgabe auf die Standardausgabe.

Gib eine ganze Zahl aus: die Summe der Kantengewichte des minimalen Spannbaums.

Beispiele

Eingabe 1

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

Ausgabe 1

7

Hinweis

Der minimale Spannbaum enthält die Kanten $(1,4,1),(2,3,3),(2,4,3)$. Jedes Tripel gibt die Nummer des ersten geordneten Paars, die Nummer des zweiten geordneten Paars und das Kantengewicht an. Die Summe der Kantengewichte ist $7$.

Teilaufgaben

Für $10\%$ der Testdaten gilt $1\le n,m\le 1000$.

Für weitere $10\%$ der Testdaten gilt $1\le m\le 2\times 10^4$.

Für weitere $10\%$ der Testdaten gilt $1\le m\le 5\times 10^4$.

Für weitere $20\%$ der Testdaten gilt $m=n^2$, und alle geordneten Paare sind voneinander verschieden.

Für weitere $10\%$ der Testdaten gilt für jedes $i=2\cdots n$, dass $f_i=i-1$.

Für weitere $10\%$ der Testdaten gilt für jedes $i=2\cdots n$, dass $f_i=1$.

Für $100\%$ der Testdaten gilt $1\le n\le 10^6,1\le m\le 10^5$. Für jedes $i=1,2,\dots n-1$ gilt $1\le f_{i+1} < i+1$. Für jedes $i=1,2,\dots m$ gilt $1\le x_i,y_i\le n$.