34846번 - 이웃 마을

문제

한양 나라에는 $N$개의 마을과 $M$개의 도로가 있다. 각 마을에는 1ドル$부터 $N$까지의 서로 다른 번호가 붙어 있으며, 각 도로는 서로 다른 두 마을을 양방향으로 연결한다. 초기에 모든 마을에는 아무것도 건설되어 있지 않다.

어떤 마을의 이웃 마을이란, 그 마을과 도로로 직접 연결된 마을을 의미한다.

당신은 다음 쿼리 $Q$개를 처리해야 한다.

• 1 i: $i$번 마을에 지하철 역을 건설한다.
• 2 i: $i$번 마을의 이웃 마을 중 지하철 역이 하나 이상 건설된 마을이 몇 개인지 출력한다.

입력

첫째 줄에 마을의 수 $N,ドル 도로의 수 $M,ドル 쿼리의 수 $Q$가 공백으로 구분되어 주어진다. (2ドル \le N \le 200,000円$; 1ドル \le M \leq \min \!\left( \frac{N(N-1)}{2}, 200,000円 \right)$; 1ドル \le Q \le 200,000円$)

이후 $M$개의 줄에 걸쳐 각 도로가 연결하는 두 마을의 번호 $u, v$가 공백으로 구분되어 주어진다. (1ドル \leq u, v \leq N; u \ne v$)

이후 $Q$개의 줄에 걸쳐 각 쿼리를 나타내는 정수 $q, i$가 공백으로 구분되어 주어진다. (1ドル \le q \le 2$; 1ドル \le i \le N$)

두 마을을 연결하는 도로의 수는 최대 1ドル$개이다.

2번 쿼리는 한 번 이상 주어진다.

출력

각 2번 쿼리에 대해 쿼리의 결과를 한 줄에 하나씩 출력한다.

제한

노트