기차 여행

어떤 사람들이 기차를 타려고 하며, 각자 어느 자리에 앉을지 정하려고 한다. 사람들 중 $M$ 쌍은 친구 사이이며, 이들은 서로 최대한 가까이 앉기를 원한다. 기차 객실은 $N$개의 행으로 이루어져 있고, 각 행에 자리가 4개씩 있는 $N \times 4$ 격자 모양이다. 그룹에는 총 $4N$명이 있으며, 사람들은 $1$번부터 $4N$번까지 번호가 붙어 있다.

유클리드 거리가 $L = \sqrt{dx^2 + dy^2}$인 자리에 앉은 친구 한 쌍은 그룹의 총 행복도에 $1/L^2$을 더한다. 여러분의 과제는 총 행복도가 최대가 되도록 사람들을 배치하는 것이다.

입력은 $10$개의 테스트 케이스로 이루어진다.

첫째 줄에 테스트 케이스 번호 $T$ ($0 \le T \le 10$)가 주어진다. ($0$은 예시 케이스이다.) 둘째 줄에는 객실의 행 수 $N$과 친구 쌍의 수 $M$ ($1 \le N \le 25\,000$, $1 \le M \le 100\,000$)이 주어진다. 이어지는 $M$개의 줄에는 친구 두 명의 번호 $a$와 $b$ ($1 \le a,b \le 4N$, $a \ne b$)가 각각 주어진다.

$N$개의 줄을 출력한다. 각 줄에는 정수 4개를 출력하며, 그 행에 앉은 네 사람의 번호를 적는다. 모든 사람은 어딘가의 자리에 배치되어야 한다.

예시 케이스에서는 $2 \times 4$ 격자에 8명을 배치한다. 예시 해답은 1번과 4번을 제외한 모든 친구 쌍의 거리를 최적화하며, 1번과 4번은 서로 $\sqrt 3$만큼 떨어져 앉는다. 이때 총 행복도는 $4 \cdot 1/1 + 1/3 \approx 4.33$이다.

모든 친구 쌍이 거리 1에 앉도록 배치하면 더 나은 해를 얻을 수 있다. 만약 이것이 실제 테스트 케이스였고 다른 참가자가 이 해(총 행복도 $5$)를 냈다면, 이 테스트 케이스는 $10 \cdot (4.33 / 5)^2 \approx 7.51$점을 받았을 것이다.