Ald

트리가 주어진다. 트리는 $1$부터 $n$까지 번호가 붙은 $n$개의 정점으로 이루어져 있다.

정점 $a$와 $b$ 사이의 경로를 $(a, b)$로 나타낸다. 경로의 $d$-집합은 경로 위의 정점 중 하나로부터 거리가 $\le d$인 트리의 모든 정점으로 이루어진 집합이다. 예를 들어 경로의 $0$-집합은 경로의 정점 집합 자체이다. 두 정점 사이의 거리는 두 정점을 잇는 경로의 간선 수이다.

$S$를 트리 경로들의 다중집합이라고 하자. 처음에 $S$는 비어 있다. 다음 쿼리를 처리하라.

• 1 $u$ $v$: 경로 $(u, v)$를 $S$에 추가한다 ($1 \le u, v \le n$).
• 2 $u$ $v$: $S$에서 경로 $(u, v)$ 하나를 삭제한다 ($1 \le u, v \le n$). $(u, v)$와 $(v, u)$는 같은 경로를 나타낸다. 예를 들어 $S=\{(2, 3), (2, 3)\}$일 때 2 3 2 쿼리를 수행하면 $S=\{(2, 3)\}$이 된다. 이 쿼리를 수행하기 전에 $(u, v)$ 또는 $(v, u)$가 $S$에 적어도 하나 있음이 보장된다.
• 3 $d$: $S$에 있는 모든 경로의 $d$-집합의 교집합 크기를 출력한다 ($0 \le d \le n$). $S$가 비어 있으면 $0$을 출력한다.

첫 줄에 테스트 케이스의 수 $t$가 주어진다 ($1 \le t \le 10^4$). 각 테스트 케이스의 첫 줄에는 정점의 수 $n$과 쿼리의 수 $q$가 주어진다 ($1 \le n, q \le 10^5$). 이어서 $n-1$개의 줄에 $i$번째 간선의 양 끝점 $u_i$, $v_i$가 주어진다. 마지막으로 $q$개의 줄에 위에서 설명한 형식의 쿼리가 주어진다. 모든 테스트 케이스에 걸쳐 $n$의 합은 $10^5$를 넘지 않으며, $q$의 합도 $10^5$를 넘지 않는다.

3번 유형의 쿼리마다 답을 한 줄에 하나씩 출력한다.