스크리머

경찰은 도시의 주요 범죄자 대부분을 구금하려는 대규모 작전을 준비하고 있다. 정보 유출을 막기 위해 경찰 측의 정보 흐름은 최대한 통제되어야 한다. 작전에 참여하는 각 수사관(DO)은 엄격한 규정을 따른다.

수사관들 사이에서 공유되는 정보는 이른바 드롭(drop)의 형태를 띤다. 드롭은 항상 말로 전달되며, 전자 기기, 종이 등 어떤 매체에도 기록되어서는 안 된다. 각 수사관은 자신과 양방향 연결을 공유하는 특정 수사관에게만 드롭을 전달할 수 있다. 각 수사관은 드롭을 받은 즉시 변경 없이, 드롭을 받은 수사관을 제외하고 자신과 연결을 공유하는 모든 동료에게 전달해야 한다.

수석 감독관(CI)은 어떤 수사관 쌍이 연결을 공유할지 선택해야 한다. 이렇게 최종적으로 선택된 연결 집합을 최종 그룹(final group, FG)이라고 한다. 최종 그룹에는 추가적인 FG 규칙이 적용된다. 어떤 수사관이 동료들에게 드롭을 전달한 뒤 일정 시간이 지나 그 드롭이 자신에게 되돌아오는 상황은 발생해서는 안 된다. 이는 FG 네트워크에 불필요한 연결이 너무 많다는 뜻이다.

각 폴더가 특정 수사관 쌍 사이의 연결 하나를 설명하는 폴더 더미가 있다. FG의 선택은 두 단계로 이루어진다. 먼저 CI는 정수 S와 T를 고르고, 둘은 같은 값일 수도 있으며, 더미에서 S번째 폴더 위의 모든 폴더와 T번째 폴더 아래의 모든 폴더를 제거한다.

다음으로 CI는 남은 폴더에 대해 같은 작업을 반복한다. 정수 U와 V를 고르고, 둘은 같은 값일 수도 있으며, 남은 더미에서 U번째 폴더 위의 모든 폴더와 V번째 폴더 아래의 모든 폴더를 제거한다.

CI는 남은 폴더의 모든 연결을 FG에 사용하려고 한다. 하지만 FG 규칙 때문에 연결들이 반드시 FG를 이룰 수 있는 것은 아니다. CI는 이 규칙을 자주 잊는 편이다.

CI의 직업 습관을 고칠 수는 없다. 그의 조수는 프로그래머를 고용해 이 과정을 점진적으로 전산화하려 하며, 그 첫 번째 작업은 CI가 처음 두 값 S와 T를 고른 뒤 선택할 수 있는 서로 다른 FG의 개수를 계산하는 것이다. 이 계산은 다양한 S와 T 값에 대해 효율적이어야 한다.

첫 입력 줄에는 수사관의 수 N과 CI의 더미에 있는 폴더의 수 M이 주어진다. (1 ≤ N, M ≤ 105) 수사관은 1부터 N까지의 정수로 구분된다. 다음 M개 줄에는 폴더 하나씩이 주어지며, 각 줄에는 폴더가 설명하는 연결의 수사관 쌍 A, B가 주어진다. (1 ≤ A < B ≤ N) 줄의 순서는 더미에서 위에서 아래로 놓인 폴더의 순서와 같다.

다음 줄에는 질의의 수 Q가 주어진다. (1 ≤ Q ≤ 105) 다음 Q개 줄에는 질의 하나씩이 주어지며, 각 줄에는 FG 선택의 첫 단계에서 CI가 고르는 수 S, T가 주어진다. (1 ≤ S ≤ T ≤ M)

Q개 질의 각각에 대해, 선택 과정의 두 번째 단계에서 만들 수 있는 서로 다른 FG의 개수를 출력한다.