자연공원

JOI섬은 관광지다. 섬 전체가 자연공원으로 지정되어 있다.

JOI섬에는 N개의 장소와 여러 개의 도로가 있다. 장소에는 0부터 N − 1까지 번호가 붙어 있다. 모든 도로는 서로 다른 두 장소를 연결하며, 양방향으로 지날 수 있다. 각 장소에 연결된 도로는 7개 이하다. 서로 다른 두 장소 사이에는 도로가 많아야 하나다. 여러 도로를 지나면 어떤 장소에서든 다른 모든 장소로 갈 수 있다.

당신과 친구 IOI양은 JOI섬을 조사하려고 한다. 효율적으로 조사하려면 JOI섬의 구조를 파악해야 한다. JOI섬에는 야생 동물이 많아 위험하다. IOI양은 운동 능력이 뛰어나므로 IOI양이 JOI섬을 탐험하고, 당신은 IOI양의 보고에 따라 JOI섬의 구조를 알아낸다.

당신은 IOI양에게 두 장소 A, B와 중간 장소로 지날 수 있는 여러 후보를 주고, 주어진 중간 장소 중 일부만 지나면서 장소 A에서 장소 B로 갈 수 있는지 묻는다. 그러면 IOI양이 JOI섬을 탐험하고 결과를 당신에게 보고한다.

조사에 너무 많은 시간을 쓸 수 없으므로 질문의 수는 45 000개 이하여야 한다.

IOI양과 통신하면서 JOI섬의 구조를 알아내는 프로그램을 작성하시오.

샘플 그레이더는 표준 입력에서 다음 데이터를 읽는다.

• 첫째 줄에는 정수 T, 즉 서브태스크 번호가 들어 있다.
• 둘째 줄에는 정수 N, 즉 장소의 수가 들어 있다.
• 셋째 줄에는 정수 M, 즉 도로의 수가 들어 있다.
• 이어지는 M개의 줄 중 i번째 줄(1 ≤ i ≤ M)에는 두 정수 Ai, Bi가 공백으로 구분되어 들어 있다. 이는 장소 Ai와 장소 Bi를 잇는 도로가 있고 양방향으로 지날 수 있음을 뜻한다.

프로그램이 성공적으로 종료되면 샘플 그레이더는 표준 출력에 다음 정보를 쓴다. (따옴표는 실제로 쓰이지 않는다.)

• 프로그램이 올바르다고 판정되면 샘플 그레이더는 “Accepted”를 쓴다.
• 프로그램이 오답으로 판정되면 샘플 그레이더는 그 유형을 “Wrong Answer [1]” 형식으로 쓰고 프로그램을 종료한다.

프로그램이 여러 유형의 오답에 해당하면 샘플 그레이더는 그중 하나만 보고한다.

• 1 ≤ T ≤ 5.
• 2 ≤ N ≤ 1 400.
• 1 ≤ M ≤ 1 500.
• 각 장소에 연결된 도로는 7개 이하다.
• 여러 도로를 지나면 어떤 장소에서든 다른 모든 장소로 갈 수 있다.
• 서로 다른 두 장소 사이에는 도로가 많아야 하나다.