크리스마스 트리 장식

바이트랜드 파티 공장(Byteland Party Factory)에서 새로운 크리스마스 트리 장식을 출시하려고 한다. 이 장식의 시제품을 만들 때, 먼저 두 개의 전구를 전선으로 서로 연결한 뒤, $(N - 2)$번에 걸쳐 새 전구를 하나씩 가져와 이미 존재하는 전구 중 하나에 전선으로 연결하였다. 그 결과 $N$개의 색 전구로 이루어진 장식이 완성되었다. 공장에는 $K$가지 색의 전구가 있다.

첫 시제품이 완성되자 이를 장식 부서에 넘겼다. 장식 부서에서는 장식의 아름다움을 재는 척도로, 같은 색 전구 두 개를 잇는 전선의 개수를 사용하기로 하였다. 이후 이들은 $M$번에 걸쳐 기존 전구 하나를 다른 전구로 교체하였고, 매번 교체 후 장식의 아름다움이 얼마인지 알고자 하였다.

장식의 최초 시제품과 장식 부서가 수행한 교체 내역이 주어졌을 때, 각 교체 후 장식의 아름다움을 모두 구하는 프로그램을 작성하시오.

입력의 첫째 줄에는 세 정수가 주어진다: 장식에 있는 전구의 개수 $N$ ($2 \le N \le 300\,000$), 장식 부서가 수행한 교체 횟수 $M$ ($1 \le M \le 300\,000$), 전구가 가질 수 있는 색의 가짓수 $K$ ($1 \le K \le 10^9$).

둘째 줄에는 $N$개의 정수 $A_i$ ($1 \le A_i \le K$)가 주어지며, 이는 전구가 장식에 추가된 순서대로 각 전구의 색을 나타낸다.

셋째 줄에는 $N - 2$개의 정수 $P_i$ ($1 \le P_i \le i + 1$)가 주어진다. $P_i$는 $(i + 2)$번 전구가 몇 번 전구에 연결되었는지를 나타낸다.

이어지는 $M$개의 줄에는 각각 두 정수 $X_i$와 $Y_i$ ($1 \le X_i \le N$, $1 \le Y_i \le K$)가 주어지며, 이는 $i$번째 교체에서 $X_i$번 전구를 색이 $Y_i$인 전구로 바꾸었음을 나타낸다.

전구는 장식에 추가된 순서대로 $1$번부터 $N$번까지 번호가 매겨지며, $1$번과 $2$번 전구가 전선으로 이어진 최초의 두 전구이다.

정확히 $M$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 교체 후의 구성에서, 같은 색 전구 두 개가 전선으로 연결된 전구 쌍의 개수를 출력한다.