라우터 6

헨리와 헤티는 네트워크 회사에 입사했고, 첫 프로젝트로 라우터 Connect Ethernet Operating Interface 2016을 만든다. 라우터는 다음으로 구성된다.

• 입력 노드 $N$개, 번호는 $1$번부터 $N$번까지
• 출력 노드 $N$개, 번호는 $N+1$번부터 $2N$번까지
• 내부 노드 $K$개, 번호는 $2N+1$번부터 $2N+K$번까지
• 서로 다른 두 노드를 잇는 단방향 직접 연결 $M$개

노드 $X$가 노드 $Y$로 데이터를 보낼 수 있다는 말은 $Y$가 $X$에서 데이터를 받을 수 있다는 말과 같고, 다음 중 하나가 성립한다는 뜻이다. $X = Y$이거나, $X$가 데이터를 보낼 수 있는 노드 $Z$가 있고 $Z$에서 $Y$로 가는 직접 연결이 있다.

$X$가 $Y$로 데이터를 보낼 수 있고 $X \neq Y$일 때, $X$에서 $Y$로 가는 데이터 경로는 $L \geq 2$, $A_1 = X$, $A_L = Y$를 만족하는 직접 연결의 집합 $\{(A_1, A_2), (A_2, A_3), \ldots, (A_{L-1}, A_L)\}$이다.

라우터는 다음 다섯 조건을 모두 만족할 때 제대로 동작한다.

• 모든 입력 노드가 모든 출력 노드로 데이터를 보낼 수 있다
• 모든 입력 노드는 자기 자신에서만 데이터를 받을 수 있다
• 모든 출력 노드는 자기 자신으로만 데이터를 보낼 수 있다
• $X \neq Y$인 두 노드에서 $X$가 $Y$로 데이터를 보낼 수 있으면 $Y$는 $X$로 데이터를 보낼 수 없다
• $X \neq Y$인 두 노드에서 $X$가 $Y$로 데이터를 보낼 수 있으면 $X$에서 $Y$로 가는 데이터 경로가 유일하다. 특히 두 노드를 잇는 직접 연결은 최대 한 개다

노드 $X$를 돌리는 데 드는 전력은 $P_X = IN_X \times OUT_X$이다. $IN_X$는 $X$로 데이터를 보낼 수 있는 입력 노드의 개수, $OUT_X$는 $X$에서 데이터를 받을 수 있는 출력 노드의 개수다. 라우터가 쓰는 최대 전력은 $P_{max} = \max(P_1, P_2, \ldots, P_{2N+K})$다.

제대로 동작하는 라우터를 만들어라. 입력 노드와 출력 노드가 각각 정확히 $N$개여야 하고, 직접 연결은 $M_{lim}$개 이하여야 하며, $P_{max} \le P_{lim}$이어야 하고, 전체 노드 수는 $N_{tot} = 2N + K \le 500\,000$이어야 한다.

이 조건을 만족하는 라우터는 여러 개여서 출력 항목에서 그중 하나를 정해 두었다. 그 라우터를 출력하면 된다.

한 줄에 정수 $N$, $M_{lim}$, $P_{lim}$이 주어진다. 차례대로 입력 노드의 개수, 허용되는 직접 연결의 최대 개수, 허용되는 최대 전력이다. 출력 노드의 개수도 $N$과 같다.

$1 \le N \le 10\,000$, $1 \le M_{lim} \le 500\,000$, $N \le P_{lim} \le 1\,000\,000$이다. 모든 입력 노드 $X$는 $IN_X = 1$, $OUT_X = N$이므로 답이 존재하려면 $P_{lim} \ge N$이어야 한다.

모든 테스트 데이터에서 출력 항목이 정한 라우터의 직접 연결 개수는 $M_{lim}$개 이하다.

아래 규칙으로 만든 라우터를 출력한다. 이 라우터는 제대로 동작하고 최대 전력이 $P_{lim}$ 이하다.

먼저

$g = \min\left(N, \left\lfloor \frac{P_{lim}}{N} \right\rfloor\right), \qquad c = \left\lfloor \sqrt{P_{lim}} \right\rfloor, \qquad b = \left\lfloor \frac{c}{g} \right\rfloor$

로 둔다.

입력 노드를 연속한 $g$개씩 묶어 $S = \lceil N / g \rceil$개의 그룹으로 자른다. 입력 그룹 $j$는 입력 노드 $(j-1)g+1$번부터 $\min(jg, N)$번까지를 담으므로 마지막 그룹은 다른 그룹보다 작을 수 있다. 출력 노드도 같은 방식으로 자른다. 출력 그룹 $j$는 출력 노드 $N + (j-1)g + 1$번부터 $N + \min(jg, N)$번까지를 담는다.

그룹 번호 $1$부터 $S$까지를 연속한 $b$개씩 묶어 $B = \lceil S / b \rceil$개의 블록으로 자른다. 블록 $k$는 그룹 번호 $(k-1)b+1$부터 $\min(kb, S)$까지를 담고, 그룹 $j$는 블록 $\lfloor (j-1)/b \rfloor + 1$에 속한다. 입력 쪽과 출력 쪽은 같은 블록 구분을 쓴다.

내부 노드는 $K = 2S + B^2$개이고 다음 순서로 번호를 붙인다.

• 입력 그룹마다 모으는 노드 하나. $2N + j$번 노드가 입력 그룹 $j$의 모으는 노드다
• 블록 쌍마다 중계 노드 하나. $2N + S + (k-1)B + l$번 노드가 (입력 블록 $k$, 출력 블록 $l$) 쌍의 중계 노드다
• 출력 그룹마다 나누는 노드 하나. $2N + S + B^2 + j$번 노드가 출력 그룹 $j$의 나누는 노드다

직접 연결은 다음 순서로 출력한다.

1. 입력 그룹 $j$를 번호가 커지는 순서로, 그 그룹에 속한 입력 노드 $x$를 번호가 커지는 순서로 보면서, $x$에서 그룹 $j$의 모으는 노드로 가는 연결
2. 입력 그룹 $j$를 번호가 커지는 순서로, 출력 블록 $l$을 번호가 커지는 순서로 보면서, 그룹 $j$의 모으는 노드에서 (그룹 $j$가 속한 블록, 블록 $l$) 쌍의 중계 노드로 가는 연결
3. 출력 그룹 $j$를 번호가 커지는 순서로, 입력 블록 $k$를 번호가 커지는 순서로 보면서, (블록 $k$, 그룹 $j$가 속한 블록) 쌍의 중계 노드에서 그룹 $j$의 나누는 노드로 가는 연결
4. 출력 그룹 $j$를 번호가 커지는 순서로, 그 그룹에 속한 출력 노드 $y$를 번호가 커지는 순서로 보면서, 그룹 $j$의 나누는 노드에서 $y$로 가는 연결

이 라우터는 $N_{tot} = 2N + 2S + B^2$, $M = 2N + 2SB$다.

첫째 줄에 $N_{tot}$과 $M$을 공백으로 구분해 출력한다. 다음 $M$개의 줄에는 직접 연결 하나마다 두 정수 $X$와 $Y$를 공백으로 구분해 출력한다. 노드 $X$에서 노드 $Y$로 가는 직접 연결을 뜻하고, 순서는 위에서 정한 대로다.