이름을 보존하는 네트워크

제한 시간: 10000 ms. 메모리 제한: 1024 MB.

한 연구 컨소시엄이 새 데이터센터를 짓고 있다. 데이터센터에서는 컴퓨터들이 함께 일하고 네트워크로 통신하도록 구성된다. 네트워크는 컴퓨터 사이의 양방향 직접 링크만으로 동작한다. 직접 링크로 연결되지 않은 두 컴퓨터 $c_1$과 $c_2$도, 연속한 링크 $l_1, l_2, \ldots, l_k$의 경로가 있으면 서로 통신할 수 있다. 이때 $l_i$와 $l_{i+1}$은 끝점을 공유하고, $c_1$은 $l_1$의 끝점이며, $c_2$는 $l_k$의 끝점이다. 두 컴퓨터 사이에는 직접 링크가 최대 하나만 있을 수 있다.

컨소시엄은 네트워크에 컴퓨터가 몇 대 있고 어떻게 연결되는지를 보여 주는 설계를 제출하라고 요청한다. 제출하는 설계는 다음 제한을 모두 지켜야 한다.

1. 컴퓨터 수는 L대 이상 U대 이하여야 한다.
2. 각 컴퓨터는 정확히 4개의 링크의 끝점이며, 이 링크들은 서로 다른 4대의 컴퓨터와 연결된다.
3. 모든 컴퓨터 쌍은 위에서 설명한 방식으로 서로 통신할 수 있어야 한다.
4. 시스템이 꺼져 있는 동안 ID가 무작위로 바뀌어도, 컴퓨터는 자신을 고유하게 식별할 수 있어야 한다.

마지막 조건을 자세히 말하면 이렇다. 설계의 $N$대 컴퓨터에는 처음에 1부터 $N$까지의 서로 다른 정수 ID가 하나씩 주어진다. 하지만 일정 시간 꺼졌다가 다시 켜지면 ID가 순열로 뒤섞일 수 있다. 각 컴퓨터는 여전히 1부터 $N$까지의 정수를 하나씩 갖지만, 그 정수가 원래 값과 같다고 보장할 수 없다. 네트워크는 기존 직접 링크 정보만으로 원래 ID를 복원해야 한다.

자동 프로그램은 설계의 조건 1부터 3까지를 검증한 뒤, 다음과 같이 바뀐 사본을 돌려준다.

• 고유 ID가 무작위로 뒤섞인다. 각 ID는 어느 컴퓨터에든 같은 확률로 놓인다.
• 각 링크는 새 ID를 사용해 작은 ID를 먼저 적는다.
• 링크 목록은 첫 번째 끝점의 오름차순으로 정렬하고, 같으면 두 번째 끝점의 오름차순으로 정렬한다.

ID가 어떻게 바뀌었는지 정확히 알아내야 한다. 프로그램은 1부터 $N$까지 정수의 비밀 무작위 순열 $f$를 만들고, 링크를 모두 제거한 빈 사본의 컴퓨터에 그 수들을 배정한다. 설계의 컴퓨터 $i$와 $j$ 사이 링크마다, 사본에는 $f(i)$와 $f(j)$ 사이 링크를 추가한다. 프로그램이 사용한 $f$를 정확히 복원해야 한다. 같은 결과를 내는 다른 순열 $f'$을 반환하면, 복원한 ID가 원래 ID라고 보장할 수 없으므로 컨소시엄은 그 설계를 받아들이지 않는다.

10 이상 100 이하의 모든 $N$에 대해, 위의 제한을 모두 지키고 서로 다른 두 순열 $f$와 $f'$를 적용하면 서로 다른 링크 집합이 나오는 네트워크가 적어도 하나 존재한다.

• $1 \le T \le 30$.