연결 유지하기

바이트랜드에 어려운 시기가 찾아왔다. 양자 컴퓨팅이 주류가 되면서 큐비트랜드가 바이트랜드를 점령하려 한다. 문제는 바이트랜드에 전쟁을 치를 돈이 부족하다는 것이다. 그래서 바이트랜드의 왕 바이트맨 0x0B는 지출을 줄이려고 도로망을 개편하기로 했다.

바이트랜드에는 도시가 $n$개 있고, 일방통행 도로 $m$개가 도시를 잇는다. 이 도로만 써서 어느 도시에서든 다른 모든 도시로 갈 수 있다. 도시 밖에서 교차하는 도로는 없고, 그 밖의 도로도 없다. 도로가 일방통행인 이유는 도로마다 중간에 한쪽 방향으로만 통과하는 차단기가 있기 때문이다. 차단기는 적이 길을 잘못 들었을 때 시간을 낭비하게 만들려고 세웠다.

개편의 목표는 도로 몇 개를 폐쇄해서 정확히 $2n$개만 남기는 것이다. 왕의 참모들은 $2n$개면 어느 도시에서든 다른 모든 도시로 갈 수 있는 성질을 지키기에 충분하다고 본다. 더 적어도 되는지는 참모들도 확실히 모른다. 이제 어떤 도로를 폐쇄할지 고르는 일이 남았다.

입력은 여러 개의 테스트 케이스로 이루어진다. 첫 줄에 테스트 케이스의 개수가 주어진다.

각 테스트 케이스의 첫 줄에는 도시의 수 $n$과 도로의 수 $m$이 주어진다($n \ge 4$, $m > 2n$). 다음 $m$개의 줄에는 각각 두 정수 $x_i$와 $y_i$가 주어지고, 도시 $x_i$에서 도시 $y_i$로 가는 도로를 뜻한다($1 \le x_i, y_i \le n$, $x_i \ne y_i$). 주어진 도로만 써서 어느 도시에서든 다른 모든 도시로 갈 수 있음이 보장된다. 두 도시 $x$와 $y$에 대해 $x$에서 $y$로 가는 도로는 많아야 하나이고, $y$에서 $x$로 가는 도로도 많아야 하나이다. 답은 항상 존재한다. 한 입력에 들어 있는 모든 테스트 케이스의 $m$을 더한 값은 100,000을 넘지 않는다.

각 테스트 케이스마다 정확히 $m - 2n$개의 줄을 출력한다. 각 줄에는 폐쇄할 도로의 출발 도시와 도착 도시를 공백 하나로 구분해 출력한다.

폐쇄하는 방법은 여러 가지이므로 다음 규칙으로 정해지는 답만 정답으로 인정한다. 한 테스트 케이스 안에서 도로에 입력에 주어진 순서대로 1번부터 $m$번까지 번호를 붙인다.

1. 도시 1에서 출발해 도로를 주어진 방향으로 따라가는 너비 우선 탐색을 한다. 처음에는 도시 1만 방문 표시를 하고 선입선출 큐에 넣는다. 큐에서 도시 $u$를 꺼내 $u$에서 나가는 도로를 번호가 작은 것부터 살핀다. 그 도로의 도착 도시가 아직 방문 전이면 그 도시에 방문 표시를 하고 큐에 넣은 뒤, 그 도로를 남긴다. 이렇게 남긴 도로의 집합을 $A$라고 하자.
2. 모든 도로의 방향을 뒤집은 그래프에서 도시 1부터 같은 너비 우선 탐색을 한다. 큐에서 꺼낸 도시 $u$로 들어오는 도로를 번호가 작은 것부터 살피고, 그 도로의 출발 도시가 아직 방문 전이면 그 도시에 방문 표시를 하고 큐에 넣은 뒤, 그 도로를 남긴다. 이렇게 남긴 도로의 집합을 $B$라고 하자.
3. $K = A \cup B$로 둔다. $K$의 도로 수는 많아야 $2n - 2$개이므로, $K$에 없는 도로를 번호가 작은 것부터 차례로 $K$에 넣어 $K$의 크기를 정확히 $2n$으로 맞춘다.
4. $K$에 들어가지 않은 도로를 모두 폐쇄하고, 번호가 작은 것부터 차례로 출력한다.