라우터 2

헨리와 헤티는 네트워크 장비 회사에 입사했다. 두 사람의 첫 과제는 새 라우터 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$로 가는 직접 연결이 있는 노드 $Z$가 있다.

$X \neq Y$이고 $X$가 $Y$로 데이터를 보낼 수 있으면, $X$에서 $Y$로 가는 데이터 경로는 $A_1 = X$, $A_L = Y$인 $L \ge 2$에 대해 직접 연결의 집합 $\{(A_1, A_2), (A_2, A_3), \dots, (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, \dots, P_{2N+K})$이다.

다음 조건을 모두 만족하는 라우터를 만들어라.

• 입력 노드가 정확히 $N$개, 출력 노드가 정확히 $N$개다.
• 직접 연결을 $M_{lim}$개 이하로 쓴다.
• 최대 전력이 $P_{lim}$ 이하다.
• 전체 노드 수 $N_{tot} = 2N + K$가 $500\,000$ 이하다.

조건을 만족하는 라우터는 여럿이므로, 그중 출력 형식에서 정의한 사전순으로 가장 작은 하나만 정답으로 인정한다.

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

$1 \le N \le 250$, $1 \le M_{lim} \le 1\,000\,000$, $1 \le P_{lim} \le 1\,000\,000$이다. 입력은 항상 $N^2 \le M_{lim}$과 $N \le P_{lim}$을 만족한다.

첫째 줄에 전체 노드 수 $N_{tot} = 2N + K$와 직접 연결의 개수 $M$을 공백으로 구분해 출력한다. 이어지는 $M$개의 줄에는 직접 연결을 한 줄에 하나씩 $X$ $Y$ 형식으로 출력한다. 이는 노드 $X$에서 노드 $Y$로 가는 직접 연결이 있다는 뜻이다. 직접 연결은 $X$가 커지는 순서로, $X$가 같으면 $Y$가 커지는 순서로 정렬해서 출력한다.

출력 전체를 정수 수열 $N_{tot}, M, X_1, Y_1, \dots, X_M, Y_M$으로 볼 때, 조건을 만족하는 모든 라우터의 출력 중 사전순으로 가장 작은 것을 출력한다.