2단 라우터

라우터는 노드와, 서로 다른 두 노드를 잇는 단방향 연결로 이루어진다.

• 입력 노드 $N$개, 번호는 $1$부터 $N$까지
• 출력 노드 $N$개, 번호는 $N+1$부터 $2N$까지
• 내부 노드 $K$개, 번호는 $2N+1$부터 $2N+K$까지
• 단방향 연결 $M$개

노드 $X$가 노드 $Y$로 데이터를 보낼 수 있다는 것은, $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 = \mathrm{IN}_X \times \mathrm{OUT}_X$로 정의한다. $\mathrm{IN}_X$는 $X$로 데이터를 보낼 수 있는 입력 노드의 수, $\mathrm{OUT}_X$는 $X$에게서 데이터를 받을 수 있는 출력 노드의 수다. 라우터의 최대 전력은 $P_{max} = \max(P_1, P_2, \dots, P_{2N+K})$이다.

$N$, $M_{lim}$, $P_{lim}$이 주어진다. 출력 항목이 설명하는 방법으로 라우터를 만들어라. 이 라우터는 제대로 동작하고, 연결을 $M_{lim}$개 이하로 쓰며, 최대 전력이 $P_{lim}$ 이하이고, 노드를 모두 합쳐 500000개 이하로 쓴다.

첫째 줄에 정수 $N$, $M_{lim}$, $P_{lim}$이 공백으로 구분되어 주어진다. ($1 \le N \le 5000$, $N \le P_{lim} \le 10^9$, $1 \le M_{lim} \le 500000$)

출력 항목의 라우터가 쓰는 연결의 수는 $M_{lim}$ 이하다.

$s = \min(N, \lfloor P_{lim} / N \rfloor)$, $g = \lceil N / s \rceil$이라고 하자. 라우터는 다음과 같이 만든다.

• 입력 노드를 번호 순으로 $s$개씩 묶어 $g$개의 그룹으로 나눈다. 입력 노드 $i$는 그룹 $\lceil i / s \rceil$에 속한다. 마지막 그룹은 $s$개보다 적을 수 있다.
• 출력 노드도 같은 방법으로 나눈다. 출력 노드 $N + j$는 그룹 $\lceil j / s \rceil$에 속한다.
• 수집 노드를 $g$개 둔다. 그룹 $c$의 수집 노드는 $2N + c$번이다.
• 분배 노드를 $g$개 둔다. 그룹 $d$의 분배 노드는 $2N + g + d$번이다.
• 입력 노드마다 자기 그룹의 수집 노드로 가는 연결을 만든다.
• 모든 수집 노드에서 모든 분배 노드로 가는 연결을 만든다.
• 그룹마다 그 그룹의 분배 노드에서 그 그룹의 출력 노드로 가는 연결을 만든다.

첫째 줄에 노드의 총 개수 $N_{tot} = 2N + 2g$와 연결의 수 $M = 2N + g^2$를 공백으로 구분해 출력한다. 다음 $M$개의 줄에는 노드 $X$에서 노드 $Y$로 가는 연결을 한 줄에 하나씩 두 정수 $X$, $Y$로 출력한다. 연결은 $X$가 증가하는 순서로, $X$가 같으면 $Y$가 증가하는 순서로 출력한다.