Good Order#11314
The office network consists of several nodes and bidirectional cables connecting them according to the following rules:
Each cable connects exactly two distinct nodes.
No cable may connect a node to itself.
Any two nodes may be connected directly by at most one cable.
Information between any two nodes can be transmitted through one or more cables via intermediate nodes, that is, the network is connected.
The general director wants the network to be in good order. This means that the following condition must be satisfied:
there is exactly one node connected to exactly one cable, exactly two nodes connected to exactly two cables, exactly three nodes connected to exactly three cables, and so on up to .
In other words, for any 1 \le i \le n, the network must contain exactly nodes of degree . No other nodes or cables are allowed in the network.
Your task is to construct a network of good order for the given integer , or determine that it is impossible to do so.
Contains a single integer n~(1 \le n \le 239) — the network parameter.
If it is impossible to construct a network of good order for the given , print .
Otherwise, list all the cables in the network. Each cable should be written on a separate line and described by two integers — the -indexed indices of the nodes it connects.
Example 1