소셜 네트워킹 어플리케이션

어릴 때부터 컴퓨터 프로그래밍에 뛰어난 재능을 보인 상근이는 늘 소셜 네트워킹 웹사이트를 만들고 싶어 했다. 지난 3년 동안 여러 서비스를 열심히 분석한 상근이는 이제 자신만의 새로운 소셜 네트워킹 어플리케이션을 만들려고 한다.

사용자는 어플리케이션에 가입한 뒤, 현실에서 아는 사람을 친구로 추가한다. 이렇게 쌓인 친구 관계 정보로 친구 관계 그래프를 만들 수 있다.

이 어플리케이션에서 가장 중요한 기능은, 한 사용자가 다른 사용자의 페이지를 방문했을 때 친구 관계 그래프에서 두 사람을 잇는 경로를 보여 주는 것이다. 경로가 없으면 아무것도 보여 주지 않는다.

서비스가 인기를 끌면서 사용자가 늘어나자 이 기능의 응답이 점점 느려졌다. 두 사람 사이에 경로가 없을 때, 경로를 찾으려고 그래프 전체를 너무 오래 탐색하기 때문이다. 그래서 상근이는 두 사람 사이에 경로가 존재하는지 여부를 미리 계산해 두려고 한다.

사용자의 수와 친구 관계가 주어진다. 이때 주어진 두 사람이 친구 관계 그래프에서 서로 연결되어 있는지(경로가 존재하는지) 판별하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 입력의 첫째 줄에는 테스트 케이스의 개수 $T$ ($T \ge 1$)가 주어진다.

각 테스트 케이스의 첫째 줄에는 사용자의 수 $n$ ($1 \le n \le 10^6$)이 주어진다. 둘째 줄에는 친구 관계의 수 $k$ ($1 \le k \le 10^5$)가 주어진다. 이어지는 $k$개의 줄에는 두 정수 $a$, $b$ ($0 \le a, b < n$)가 주어지며, 이는 사용자 $a$와 $b$가 친구라는 뜻이다. 그다음 줄에는 미리 확인할 쌍의 수 $m$ ($1 \le m \le 10^5$)이 주어진다. 이어지는 $m$개의 줄에는 확인할 쌍을 나타내는 두 정수 $u$, $v$가 주어진다.

각 테스트 케이스마다 먼저 Scenario i:를 출력한다. 여기서 $i$는 테스트 케이스 번호로, $1$부터 시작한다. 그다음, 주어진 각 쌍에 대해 두 사람을 잇는 경로가 있으면 $1$을, 없으면 $0$을 한 줄에 하나씩 출력한다.

각 테스트 케이스의 출력 사이에는 빈 줄을 하나 출력한다.