붕괴

JOI 국에는 깊고 긴 계곡을 따라 $N$개의 마을이 일렬로 놓여 있다. 마을은 바다와 가까운 순서대로 $0, 1, \ldots, N-1$번의 번호가 붙어 있다. 조합위원회 위원장 I씨는 마을 사이의 양방향 통신 케이블을 관리한다. 처음에는 케이블이 하나도 없다.

I씨에게는 $C$일 동안의 케이블 공사 계획이 있다. $i+1$번째 날($0 \le i \le C-1$)의 계획은 세 정수 $T_i$, $X_i$, $Y_i$로 주어지며, 다음을 뜻한다.

• $T_i = 0$이면 마을 $X_i$와 마을 $Y_i$를 잇는 케이블을 설치한다. 그 날 시작할 때 두 마을을 잇는 케이블은 없다.
• $T_i = 1$이면 마을 $X_i$와 마을 $Y_i$를 잇는 케이블을 제거한다. 그 날 시작할 때 두 마을을 잇는 케이블이 있다.

JOI 국에서는 절벽 붕괴가 자주 일어난다. 마을 $x$와 마을 $x+1$ 사이($0 \le x \le N-2$)에서 붕괴가 일어나면, 번호가 $x$ 이하인 마을과 $x+1$ 이상인 마을을 잇는 케이블은 모두 사용할 수 없게 된다. 붕괴가 일어나면 일부 마을을 골라 기지국을 설치한다. 기지국은 모든 마을이 사용 가능한 케이블을 따라 기지국에 도달할 수 있도록 설치해야 한다.

I씨에게는 $Q$개의 질문이 있다. $j+1$번째 질문은 두 정수 $W_j$, $P_j$로 주어진다. 이는 $W_j+1$일째 날이 끝난 뒤 마을 $P_j$와 마을 $P_j+1$ 사이에서 붕괴가 일어날 때 필요한 기지국의 최소 개수를 묻는다.

첫째 줄에 $N$, $C$, $Q$가 주어진다. 이어지는 $C$개의 줄에는 $T_i$, $X_i$, $Y_i$가 주어진다. 이어지는 $Q$개의 줄에는 $W_j$와 $P_j$가 주어진다.

$Q$개의 줄을 출력한다. $j+1$번째 줄에는 $j+1$번째 질문의 답을 출력한다.

마을이 5개인 경우를 생각하자. 아래에서 $(x, y)$는 마을 $x$와 마을 $y$를 잇는 케이블을 뜻한다.

• 마을 1과 마을 2 사이에서 붕괴가 일어날 때 케이블이 $(0, 1)$, $(1, 3)$, $(2, 4)$, $(4, 0)$의 4개 있다고 하자. $(1, 3)$과 $(4, 0)$은 사용할 수 없게 되고 $(0, 1)$과 $(2, 4)$만 남는다. 마을 0, 2, 3에 기지국을 설치하면 되므로 최소 개수는 3이다.
• 마을 3과 마을 4 사이에서 붕괴가 일어날 때 케이블이 $(0, 1)$, $(0, 3)$, $(1, 2)$, $(2, 4)$, $(4, 0)$, $(4, 3)$의 6개 있다고 하자. $(2, 4)$, $(4, 0)$, $(4, 3)$은 사용할 수 없게 되고 $(0, 1)$, $(0, 3)$, $(1, 2)$만 남는다. 마을 0과 마을 4에 기지국을 설치하면 되므로 최소 개수는 2이다.