시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 157 67 33 39.759%

문제

N개의 정점으로 구성된 트리가 있다. 각 정점은 1번부터 N번까지 번호가 매겨져있고, 1 이상 10만 이하의 자연수로 표현되는 색깔을 하나 갖고 있다. 루트는 1번 정점이고, 트리이기 때문에 임의의 서로 다른 두 정점을 잇는 경로는 반드시 한 개 존재한다.

정점 u와 v를 잇는 경로가 존재하면 u에서 v로 갈 수 있다고 하자.

이 문제에서 주어지는 트리의 정점은 각각 하나의 색깔을 갖고 있다. 여러분은 아래 두 가지 질의(쿼리)를 처리해야 한다.

  • 1 a : 정점 a와 a의 부모 정점을 연결하는 간선을 제거한다. (해당 간선이 존재하는 경우에만 주어진다.)
  • 2 a : 정점 a에서 갈 수 있는 정점들의 색깔 중, 색깔의 종류의 개수를 출력한다.

입력

첫 번째 줄에는 정점의 개수 N(1 ≤ N ≤ 100,000)과 2번 쿼리의 개수 Q(1 ≤ Q ≤ 1,000,000)가 주어진다.

다음 N-1개 줄의 i번째 줄에는 정점 i+1의 부모 정점을 나타내는 정수 p(1 ≤ p ≤ N)가 주어진다.

다음 N개 줄의 i번째 줄에는 정점 i의 색깔을 나타내는 정수 c(1 ≤ c ≤ 100,000)가 주어진다.

다음 N+Q-1개의 줄에는 여러분이 처리해야 할 쿼리가 주어지는데, 1번 쿼리는 N-1개, 2번 쿼리는 Q개 주어진다.

쿼리는 한 줄에 하나씩 쿼리의 종류를 나타내는 X(1 ≤ X ≤ 2)와 쿼리에서 처리할 정점의 번호 a(1 ≤ a ≤ N)가 주어진다.

입력은 모두 자연수로 주어진다.

출력

Q개의 2번 쿼리에 대한 답을 순서대로 한 줄에 하나씩 출력한다.

예제 입력 1

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

예제 출력 1

3
3
2
2

출처