라우터 7

Henry와 Hetty는 최근 Piatra Neamț의 한 네트워킹 회사에 채용되었다. 그들의 첫 프로젝트는 Connect Ethernet Operating Interface 2016이라는 새로운 라우터를 만드는 것이다. 이 라우터는 다음으로 구성된다.

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

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

$X$가 $Y$에 데이터를 보낼 수 있고 $X \neq 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$, $Y$에 대해 $X$가 $Y$에 데이터를 보낼 수 있으면, $Y$는 $X$에 데이터를 보낼 수 없다.
• 서로 다른 두 노드 $X$, $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, \ldots, P_{2 \times N+K})$이다.

이 사양에 맞는 라우터는 다음 조건을 만족해야 한다.

• 입력 노드와 출력 노드가 정확히 $N$개이다.
• 직접 연결을 $M_{lim}$개 이하로 사용한다.
• 최대 전력이 $P_{lim}$ 이하이다.
• 전체 노드 수는 500000 이하이다($N_{tot} = 2 \times N + K \le 500000$).

첫 줄에 세 정수 $N$, $M_{lim}$, $P_{lim}$이 주어진다. 각각 입력 노드와 출력 노드의 수, 직접 연결의 최대 개수, 라우터가 사용하는 최대 전력이다.

이 테스트에서는 $N = 9978$, $M_{lim} = 100000$, $P_{lim} = 100000$이다.

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