라우터 1

헨리와 헤티는 네트워크 장비 회사에 입사했다. 첫 프로젝트는 새 라우터 Connect Ethernet Operating Interface를 만드는 일이다. 라우터는 다음으로 이루어진다.

• 입력 노드 $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), \ldots, (A_{L-1}, A_L)\}$이다.

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

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

노드 $X$를 작동시키는 데 드는 전력은 $P_X = IN_X \times OUT_X$다. $IN_X$는 $X$로 데이터를 보낼 수 있는 입력 노드의 개수, $OUT_X$는 $X$에서 데이터를 받을 수 있는 출력 노드의 개수다. 전체 노드 수를 $N_{tot} = 2N + K$라고 하면 라우터의 최대 전력은 $P_{max} = \max(P_1, P_2, \ldots, P_{N_{tot}})$다.

$N$, $M_{lim}$, $P_{lim}$이 주어진다. 제대로 동작하고, 입력 노드와 출력 노드가 각각 $N$개이며, 직접 연결을 $M_{lim}$개 이하로 쓰고, $P_{max} \le P_{lim}$이며, 노드를 모두 합쳐 $500\,000$개 이하로 쓰는 라우터를 만들어라. 조건을 만족하는 라우터는 여러 가지라서 출력해야 하는 라우터 하나를 출력 항목에서 정한다.

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

$N \le P_{lim}$이고, 출력 항목에서 정한 라우터가 직접 연결을 $M_{lim}$개 이하로 쓰는 입력만 주어진다.

아래 규칙으로 정해지는 라우터를 출력한다.

$N \times N \le P_{lim}$이면 내부 노드가 하나인 라우터를 출력한다. 이 라우터는 노드가 $N_{tot} = 2N + 1$개, 직접 연결이 $M = 2N$개다. 먼저 $i = 1, 2, \ldots, N$ 순서로 연결 $i \to 2N+1$을 출력하고, 이어서 $j = 1, 2, \ldots, N$ 순서로 연결 $2N+1 \to N+j$를 출력한다.

그렇지 않으면 내부 노드가 없는 라우터를 출력한다. 이 라우터는 노드가 $N_{tot} = 2N$개, 직접 연결이 $M = N \times N$개다. 모든 $(i, j)$ 쌍의 연결 $i \to N+j$를 $i$가 커지는 순서로, $i$가 같으면 $j$가 커지는 순서로 출력한다.

첫째 줄에 $N_{tot}$과 $M$을 공백으로 구분해 출력한다. 이어지는 $M$개의 줄에는 각각 두 정수 $X$와 $Y$를 출력한다. 노드 $X$에서 노드 $Y$로 가는 직접 연결을 만들었다는 뜻이다.