라우터 3

헨리와 헤티는 네트워크 장비 회사에 입사해 새 라우터를 설계한다. 라우터의 구성은 다음과 같다.

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

노드 $X$가 노드 $Y$로 데이터를 보낼 수 있다는 말은 ($Y$가 $X$에게서 데이터를 받을 수 있다는 말과 같다) 다음 중 하나가 성립한다는 뜻이다.

• $X = Y$이다.
• $X$가 데이터를 보낼 수 있는 노드 $Z$가 있고, $Z$에서 $Y$로 가는 직접 연결이 있다.

$X \ne Y$이고 $X$가 $Y$로 데이터를 보낼 수 있으면, $X$에서 $Y$로 가는 데이터 경로는 $A_1 = X$이고 $A_L = Y$인 직접 연결의 집합 $\{(A_1, A_2), (A_2, A_3), \dots, (A_{L-1}, A_L)\}$이다. 여기서 $L \ge 2$이다.

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

• 모든 입력 노드는 모든 출력 노드로 데이터를 보낼 수 있다.
• 입력 노드는 자기 자신에게서만 데이터를 받는다.
• 출력 노드는 자기 자신에게만 데이터를 보낸다.
• $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_{tot} = 2N + K \le 500\,000$인 라우터를 만들어라.

조건을 만족하는 라우터는 여러 가지이므로, 출력 형식에서 정한 3층 구성 규칙으로 만든 라우터 하나만 정답으로 인정한다.

첫째 줄에 정수 세 개 $N$, $M_{lim}$, $P_{lim}$이 공백으로 구분되어 주어진다. $N$은 입력 노드의 수이자 출력 노드의 수, $M_{lim}$은 쓸 수 있는 직접 연결의 최대 개수, $P_{lim}$은 라우터가 쓸 수 있는 최대 전력이다.

$1 \le N \le 100\,000$, $1 \le M_{lim} \le 500\,000$, $N \le P_{lim} \le 10^{10}$이다.

$\lceil N/g \rceil^2 \le P_{lim}$을 만족하는 가장 작은 양의 정수를 $g$라고 할 때, $2Ng \le M_{lim}$이고 $2N + g^2 \le 500\,000$임이 보장된다.

이 라우터의 설계 사양은 $N = 1250$, $M_{lim} = 500\,000$, $P_{lim} = 500\,000$이고, 더 작은 사양도 입력으로 주어진다.

라우터를 다음 규칙대로 만든다.

1. $\lceil N/g \rceil^2 \le P_{lim}$을 만족하는 가장 작은 양의 정수를 $g$라고 하자.
2. $1 \le i, j \le N$일 때 입력 노드 $i$는 입력 그룹 $a_i = ((i-1) \bmod g) + 1$에 속하고, 출력 노드 $N+j$는 출력 그룹 $b_j = ((j-1) \bmod g) + 1$에 속한다.
3. $1 \le a, b \le g$인 순서쌍 $(a, b)$마다 내부 노드를 하나씩 만들고 번호 $2N + (a-1)g + b$를 붙인다. 따라서 $K = g^2$이고 $N_{tot} = 2N + g^2$이다.
4. 모든 입력 노드 $i$에서 모든 $b$에 대해 내부 노드 $(a_i, b)$로 직접 연결을 놓고, 모든 내부 노드 $(a, b)$에서 그룹 $b$에 속한 모든 출력 노드로 직접 연결을 놓는다. 따라서 $M = 2Ng$이다.

첫째 줄에 $N_{tot}$과 $M$을 공백으로 구분해 출력한다. 이어지는 $M$개의 줄에는 직접 연결을 한 줄에 하나씩, $X$에서 $Y$로 가는 연결을 정수 $X$와 $Y$로 출력한다. 연결을 출력하는 순서는 다음과 같다.

• 먼저 입력 노드에서 나가는 연결을 $i$가 증가하는 순서로 출력하고, $i$가 같으면 $b$가 증가하는 순서로 출력한다.
• 그다음 내부 노드에서 나가는 연결을 내부 노드 번호가 증가하는 순서로 출력하고, 같은 내부 노드 안에서는 출력 노드 번호가 증가하는 순서로 출력한다.

이렇게 만든 라우터는 제대로 동작하고, 최대 전력은 $\max(N, \lceil N/g \rceil^2)$이다.