JOI 왕국에는 직선 형태의 깊은 계곡을 따라 N개의 마을이 있다.

마을은 바다에서부터의 거리 순서대로 0, 1, ... , N - 1 까지의 번호가 붙어 있다.

JOI 왕국 과학 위원회의 의장인 준혁이는, 마을 사이를 잇는 케이블을 통해 양방향 통신을 유지하려고 계획중이다.

현재, JOI 왕국에는 케이블이 하나도 없다.

준혁이는 C일 동안의 케이블 건설 계획이 있다.

i + 1일(0 ≤ i ≤ C − 1)의 계획은 세 정수 T_i, X_i, Y_i로 이루어져 있다.

- T_i = 0일 때, 마을 X_i와 마을 Y_i를 잇는 케이블을 건설한다. (i + 1일이 시작할 때, 마을 X_i와 마을 Y_i를 잇는 케이블이 존재하지 않음이 보장된다.)

- T_i = 1일 때, 마을 X_i와 마을 Y_i를 잇는 케이블을 철거한다. (i + 1일이 시작할 때, 마을 X_i와 마을 Y_i를 잇는 케이블이 존재함이 보장된다.)

JOI 왕국에서는 절벽 붕괴가 자주 일어난다.

마을 x(0 ≤ x ≤ N − 2)와 마을 x + 1 사이에 붕괴가 일어났다면, x 이하의 번호를 가진 마을과 x + 1 이상의 번호를 가진 마을 사이에 이어진 모든 케이블이 끊어진다.

붕괴가 일어날 시, JOI 왕국은 몇 개의 마을을 골라 기지국을 건설한다.

기지국은 어떤 마을에서 시작하더라도 유효한 케이블을 이용하여 도달할 수 있도록 건설되어야 한다.

준혁이는 건설 기간 동안 붕괴가 일어났을 때 몇 개의 기지국을 건설해야 하는지 구하여야 한다.

준혁이는 Q개의 상황이 궁금하다: j + 1번째 상황은 두 정수 W_j, P_j로 이루어진다.

이는 준혁이가 W_j + 1번째 날에 마을 P_j와 마을 P_j + 1 사이에 붕괴가 일어났을 시 필요한 기지국의 개수의 최솟값을 알고싶어한다는 뜻이다.

당신은 준혁이의 비서로서, 준혁이가 궁금해하는 각 상황에 대하여 답을 구하는 프로그램을 만들자.

Collapse timer 6s memory 512MB

Collapse 6s 512MB