Dane jest ukorzenione drzewo o $n$ wierzchołkach oraz $m$ par $(x_i,y_i)$, gdzie $x_i,y_i$ są wierzchołkami drzewa.

Dla wierzchołków $a,b$ definiujemy $D(a,b)$ jako liczbę wierzchołków należących do poddrzewa o korzeniu $a$, lecz nienależących do poddrzewa o korzeniu $b$.

Należy znaleźć minimalne drzewo rozpinające grafu pełnego, którego wierzchołkami są te pary, a waga krawędzi między $(x_i,y_i)$ i $(x_j,y_j)$ wynosi $D(x_i,x_j)+D(x_j,x_i)+D(y_i,y_j)+D(y_j,y_i)$.

Wejście

Dane należy odczytać ze standardowego wejścia.

Pierwszy wiersz zawiera dwie liczby $n,m$.

Następny wiersz zawiera $n-1$ liczb. Liczba na pozycji $i$ oznacza rodzica $f_{i+1}$ wierzchołka o numerze $i+1$. Gwarantowane jest $f_{i+1}< i+1$.

W kolejnych $m$ wierszach wiersz $i$ zawiera dwie liczby $x_i,y_i$, opisujące jedną z danych par.

Wyjście

Wynik należy wypisać na standardowe wyjście.

Wypisz jedną liczbę całkowitą — sumę wag krawędzi minimalnego drzewa rozpinającego.

Przykład

Wejście 1

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

Wyjście 1

7

Uwagi

Minimalne drzewo rozpinające zawiera krawędzie $(1,4,1),(2,3,3),(2,4,3)$. Trójka oznacza kolejno numer pierwszej pary, numer drugiej pary i wagę krawędzi. Suma wag wynosi $7$.

Podzadania

Dla $10\%$ danych zachodzi $1\le n,m\le 1000$.

Dla kolejnych $10\%$ danych zachodzi $1\le m\le 2\times 10^4$.

Dla kolejnych $10\%$ danych zachodzi $1\le m\le 5\times 10^4$.

Dla kolejnych $20\%$ danych zachodzi $m=n^2$, a wszystkie pary są różne.

Dla kolejnych $10\%$ danych dla każdego $i=2\cdots n$ zachodzi $f_i=i-1$.

Dla kolejnych $10\%$ danych dla każdego $i=2\cdots n$ zachodzi $f_i=1$.

Dla $100\%$ danych zachodzi $1\le n\le 10^6,1\le m\le 10^5$. Dla każdego $i=1,2,\dots n-1$ zachodzi $1\le f_{i+1} < i+1$. Dla każdego $i=1,2,\dots m$ zachodzi $1\le x_i,y_i\le n$.