알고리스트 동아리

알고리스트 동아리는 회원끼리 서로 잘 안다는 점을 자랑으로 여긴다. 해마다 5월 신입 회원이 들어오면 치킨과 맥주를 놓고 친목회를 연다. 이 자리에서 신입 회원은 기존 회원과 인사하고 신입 회원끼리도 인사한다. 규칙은 이렇다. 서로 모르는 두 회원 A와 B는 15분 동안 대화를 한 번 나눈다. A가 B와 C를 둘 다 모른다면 A는 대화를 두 번 따로 한다.

친목회 시간은 15분짜리 슬롯으로 나눈다. 한 슬롯에서는 대화가 몇 개든 동시에 진행되지만, 한 사람은 한 슬롯에 대화를 하나만 한다. 동아리에서 모르는 사람이 가장 많은 회원을 A라 하고, A가 모르는 사람 수를 $k$라고 하자. 슬롯은 적어도 $k$개가 필요하다. $k$개로 충분한지는 알 수 없으므로 운영진은 슬롯을 $k+1$개까지 쓰기로 했다.

운영진은 다음 규칙으로 일정을 짠다. 서로 모르는 쌍을 입력에 주어진 순서대로 하나씩 보면서, 두 사람 모두 아직 대화를 배정받지 않은 슬롯 가운데 번호가 가장 작은 슬롯을 그 쌍에 배정한다. 쓸 수 있는 슬롯은 1번부터 $k+1$번까지다. 두 사람 모두 비어 있는 슬롯이 하나도 없는 쌍을 만나면 일정 짜기는 그 자리에서 실패한다.

서로 모르는 쌍이 주어지면 이 규칙으로 만든 일정을 구하는 프로그램을 작성하시오.

입력은 여러 테스트 케이스로 이루어진다. 첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 회원 수 $n$과 서로 모르는 쌍의 수 $m$이 주어진다 ($2 \le n \le 444$, $1 \le m \le n(n-1)/2$). 회원의 번호는 1번부터 $n$번까지다. 다음 $m$개 줄에는 서로 모르는 두 회원의 번호 $a$와 $b$가 주어진다. 쌍은 사전순으로 주어진다. 즉 항상 $a < b$이고, $a$가 작은 쌍이 먼저 나오며, $a$가 같은 쌍끼리는 $b$가 작은 쌍이 먼저 나온다.

각 테스트 케이스마다 입력에 주어진 쌍을 같은 순서로 한 줄에 하나씩 출력한다. 각 줄에는 두 회원의 번호와 그 쌍에 배정된 슬롯 번호를 공백으로 구분해 출력한다. 일정 짜기가 실패한 테스트 케이스는 모든 쌍의 슬롯 번호를 0으로 출력한다.