라우터 4

헨리와 헤티는 네트워크 장비 회사에 막 입사했고, 첫 프로젝트로 새 라우터 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 \ne Y$일 때, $X$에서 $Y$로 가는 데이터 경로는 $L \ge 2$, $A_1 = X$, $A_L = Y$를 만족하는 직접 연결의 집합 $\{(A_1, A_2), (A_2, A_3), \dots, (A_{L-1}, A_L)\}$이다.

다음을 모두 만족하면 라우터가 제대로 동작한다.

• 모든 입력 노드는 모든 출력 노드로 데이터를 보낼 수 있다.
• 입력 노드는 자기 자신에서만 데이터를 받는다.
• 출력 노드는 자기 자신으로만 데이터를 보낸다.
• $X \ne Y$이고 $X$가 $Y$로 데이터를 보낼 수 있으면, $Y$는 $X$로 데이터를 보낼 수 없다.
• $X \ne 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, \dots, P_{2N+K})$다.

프로젝트 관리자는 명세 $N$, $M_{lim}$, $P_{lim}$을 건네면서 입력 노드와 출력 노드가 정확히 $N$개씩이고, 직접 연결을 많아야 $M_{lim}$개 쓰고, $P_{max}$가 $P_{lim}$ 이하이며, 전체 노드가 $500000$개 이하($N_{tot} = 2N + K \le 500000$)인 라우터를 요구한다. 관리자가 실제로 건넨 명세는 $N = 5101$, $M_{lim} = 500000$, $P_{lim} = 500000$이다.

명세 하나를 만족하는 라우터는 여러 가지다. 그래서 이 문제에서는 출력에 적힌 라우터 하나만 만든다.

첫째 줄에 정수 $N$, $M_{lim}$, $P_{lim}$이 주어진다. $N$은 입력 노드의 개수이자 출력 노드의 개수, $M_{lim}$은 쓸 수 있는 직접 연결의 최대 개수, $P_{lim}$은 허용되는 최대 전력이다.

• $1 \le N \le 100000$
• $N \le P_{lim} \le 10^9$
• $1 \le M_{lim} \le 500000$

출력에서 정의한 $g = \min(N, \lfloor P_{lim} / N \rfloor)$과 $r = \lceil N / g \rceil$에 대해 $2N + r^2 \le M_{lim}$과 $2N + 2r \le 500000$이 항상 성립한다.

아래에 적힌 라우터를 그대로 만든다. $g = \min(N, \lfloor P_{lim} / N \rfloor)$, $r = \lceil N / g \rceil$이라고 하자.

내부 노드는 $K = 2r$개이므로 $N_{tot} = 2N + 2r$이다. $2N+1$번부터 $2N+r$번까지는 모음 노드, $2N+r+1$번부터 $2N+2r$번까지는 분배 노드다. 입력 노드 $i$는 입력 그룹 $\lceil i / g \rceil$에 속하고, 출력 노드 $N+t$는 출력 그룹 $\lceil t / g \rceil$에 속한다. 한 그룹의 크기는 많아야 $g$다.

직접 연결은 $M = 2N + r^2$개다.

• $1$부터 $N$까지의 모든 $i$에 대해, 입력 노드 $i$에서 모음 노드 $2N + \lceil i / g \rceil$로 가는 연결
• $1$부터 $r$까지의 모든 $j$와 $1$부터 $r$까지의 모든 $k$에 대해, 모음 노드 $2N + j$에서 분배 노드 $2N + r + k$로 가는 연결
• $1$부터 $N$까지의 모든 $t$에 대해, 분배 노드 $2N + r + \lceil t / g \rceil$에서 출력 노드 $N + t$로 가는 연결

첫째 줄에 $N_{tot}$과 $M$을 공백 하나로 구분해 출력한다. 다음 $M$개의 줄에는 연결을 한 줄에 하나씩 출력하는데, 노드 $X$에서 노드 $Y$로 가는 직접 연결이 있다는 뜻으로 정수 $X$와 $Y$를 출력한다. 순서는 $i$가 커지는 순의 입력 연결, 그다음 $j$가 커지는 순이고 $j$가 같으면 $k$가 커지는 순의 내부 연결, 마지막으로 $t$가 커지는 순의 출력 연결이다.