링 보존 네트워크 timer 30s memory 2048MB

한 연구 컨소시엄이 새로운 데이터센터를 짓고 있다. 데이터센터에는 여러 컴퓨터가 함께 작업하고 네트워크를 통해 통신하도록 설치된다. 이 네트워크는 컴퓨터들 사이의 직접적인 양방향 링크만으로 동작한다. 그들이 이름 보존 네트워크(name-preserving networks)에서 성공한 뒤, 보장된 성질을 갖는 다른 설계들도 해 보기로 했다.

컨소시엄은 당신에게 링 보존 네트워크(ring-preserving network) 설계를 제출해 달라고 요청했다. 네트워크의 링(ring)이란, 네트워크의 모든 컴퓨터를 한 줄로 나열한 순서로서, 그 순서에서 이웃한 두 컴퓨터가 직접 링크로 연결되어 있고, 또한 순서의 첫 컴퓨터와 마지막 컴퓨터도 직접 링크로 연결되어 있는 것을 말한다.

링 보존 네트워크란, 원래의 컴퓨터 식별(ID)을 잃어버린 뒤에도 자기 자신의 링을 효율적으로 찾아낼 수 있는 네트워크 설계를 말한다. 당신은 링 보존 네트워크가 되도록 여러 개의 네트워크 설계를 제출해야 한다.

네트워크 설계를 평가하기 위해 컨소시엄은 자동화된 프로그램을 준비해 두었다. 당신은 컴퓨터의 정확한 개수 \mathbf{C}와, 포함해야 하는 양방향 링크의 정확한 개수 \mathbf{L}를 지정하는 네트워크 설계를 요청받게 된다. 당신은 각 컴퓨터에 1부터 \mathbf{C}까지의 서로 다른 ID를 하나씩 부여하고, ID를 사용해 링크의 두 끝점을 나타내어 \mathbf{L}개의 링크 목록을 제출해야 한다. 평가 프로그램은 그 설계를 받은 다음, 다음과 같은 변경을 가한 네트워크 설계의 사본을 되돌려준다.

• ID들이 균등한 확률로 무작위 순열(permutation)로 바뀐다. (즉, 각 ID는 어떤 컴퓨터에든 동일한 확률로 부여될 수 있다.)
• 각 링크는 (새 ID를 기준으로) 더 작은 ID가 먼저 오도록 정렬되어 제시된다.
• 링크들의 집합은 (새 ID를 기준으로) 첫 번째 끝점이 증가하는 순서로 정렬되어 제시되며, 첫 번째 끝점이 같으면 두 번째 끝점이 작은 순서로 정렬된다(사전식 순서).

당신은 이렇게 변경된 네트워크에서 링을 찾아낼 수 있어야 한다. 찾아낸 링은 원래의 링일 필요는 없다.