시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 3 2 2 66.667%

문제

Henry and Hetty were recently hired by a networking company from Piatra Neamț. Their first project is to create a new type of router, the revolutionary Connect Ethernet Operating Interface 2016, comprised of:

  • N input nodes, numbered from 1 to N;
  • N output nodes, numbered from N+1 to 2×N;
  • K internal nodes, numbered from 2×N+1 to 2×N+K;
  • M unidirectional direct connections between pairs of distinct nodes.

A node X can send data to a node Y (and hence Y can receive data from X) if:

  • X = Y, or
  • there exists a node Z such that X can send data to Z and there is a direct connection from node Z to node Y.

If a node X can send data to a node Y, and X ≠ Y, then we define a data path from X to Y as a set of direct connections {(A1, A2), (A2, A3), … (AL-1, AL)} for some L ≥ 2, such that A1 = X and AL = Y.

A router works properly if:

  • Each input node can send data to each output node;
  • Each input node can receive data only from itself;
  • Each output node can send data only to itself;
  • For any two nodes X and Y, if X ≠ Y and X can send data to Y, then Y cannot send data to X;
  • For any two nodes X and Y, if X ≠ Y and X can send data to Y, then the data path from X to Y is unique. In particular, any two nodes X and Y should be connected by at most 1 direct connection.

Like any other electronic device, a router needs electricity to work. Let's define the power needed to operate a node X as PX = INX × OUTX, where INX is the number of input nodes that can send data to X, and OUTX is the number of output nodes that can receive data from X. Let's define the maximum power used by the router as Pmax = max(P1, P2, … P2×N+K).

The project manager has given Henry and Hetty the technical specifications for building a few test routers, listed in the table below. For each of these specifications, the manager wants a router which:

  • has exactly N input nodes and N output nodes;
  • uses at most Mlim direct connections;
  • uses a maximum power which is at most Plim;
  • uses at most 500 000 nodes overall (Total nodes = Ntot = 2×N + K ≤ 500 000).

입력

On the first and only line, three integers: N, the number of input and output nodes; Mlim, the maximum number of direct connections allowed; and Plim, the maximum power the router uses.

N = 9934, Mlim = 500 000, Plim = 500 000 

출력

You will output two integer numbers separated by a space: Ntot = 2×N + K, representing the total number of nodes used to build the router; and M, representing the total number of direct connections used. On each of the following M lines you should output a pair of integers X and Y, meaning a direct connection from node X to node Y was built.

예제 입력 1

3 100 200

예제 출력 1

9 8
1 7
2 7
3 8
7 8
8 4
8 9
9 5
9 6

Henry and Hetty must build a router with 3 input nodes and 3 output nodes, which uses at most 100 direct connections and uses a maximum power of 200.

They use 9 nodes overall (input nodes 1, 2 and 3, output nodes 4, 5 and 6, and internal nodes 7, 8 and 9), and 8 direct connections.

The maximum power the router uses is 9 and is given by the power of vertex 8, which can receive data from IN8=3 input nodes and can send data to OUT8=3 output nodes.

예제 입력 2

3 100 200

예제 출력 2

6 9
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6

Another valid router for the same specifications uses 6 nodes overall (the three input nodes and the three output nodes).

The maximum power this router uses is 3: each input node can receive data only from itself and can send data to all three output nodes. Similarly, each output node can receive data from all 3 input nodes and can send data only to itself.

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 소스 코드의 크기는 800000B을 넘을 수 없다.
  • 이 문제는 하루에 3번 제출할 수 있다.