정올국에는 0번부터 N-1번까지 N개의 마을이 있다.

정올국 과학부장관인 준혁이는 몇 개의 양방향 통신 케이블을 마을 간에 유치할 것이다. 현재, 정올국에는 케이블이 하나도 없다.

준혁이는 C일 간의 케이블 건설 계획이 있다. i번째 날(0 <= i <= C-1)의 계획은 세 정수 Ti, Xi, Yi로 나타난다.

- Ti = 0인 경우, 마을 Xi와 Yi를 잇는 케이블을 건설한다. (현재 이러한 케이블이 없음이 보장된다.)

- Ti = 1인 경우, 마을 Xi와 Yi를 잇는 케이블을 제거한다. (현재 이러한 케이블이 있음이 보장된다.)

정올국에는 절벽 붕괴가 자주 일어난다.

만약 마을 x와 마을 x+1 사이에서 붕괴가 일어난다면(0 <= x < N-1), x 이하의 마을과 x+1 이상의 마을을 잇는 모든 케이블이 붕괴된다.

절벽 붕괴를 대비하여, 준혁이는 몇 개의 마을에 긴급용 발전기를 놓기로 하였다.

긴급용 발전기는 모든 마을에서 케이블을 통해 긴급용 발전기에 도달할 수 있도록 설치되어야 한다.

준혁이는 건설 과정 중 절벽 붕괴가 일어날 것을 우려하여, 상황에 따라 몇 개의 발전기가 필요한지에 대하여 생각하고자 한다.

준혁이는 Q개의 질문이 있다.

j번째 질문(0 <= j < Q)은 두 정수 Wj, Pj로 나타내어진다.

이는 만약 Wj번째 날의 저녁에 마을 Pj와 Pj+1 사이에서 붕괴가 일어날 시, 몇 개의 발전기가 필요한가?라는 질문이다.

여러분이 준혁이를 도와, 준혁이의 질문을 해결해 주자.

붕괴 timer 6s memory 512MB

붕괴 6s 512MB