/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 800 点
問題文
整数 N が与えられます。 頂点に 1 から N の番号がついた N 頂点の単純連結無向グラフであって、以下の条件を満たすものが存在するかどうかを判定し、存在するならばその例を 1 つ示してください。
- ある整数 X が存在して、任意の頂点 v について、v から 1 回または 2 回辺を辿ることで到達できる v 以外の頂点の番号の総和は X となる
制約
- 2 \le N \le 200
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
問題文中の条件を満たす N 頂点の単純連結無向グラフが存在しない場合 -1 を出力せよ。 存在する場合、1 行目に辺の本数 M を出力せよ。続く M 行のうち i 行目には 2 つの整数を出力せよ。これらは i 番目の辺の端点の頂点番号を表す。
構成されたグラフが条件を満たすならば正解となる。
入力例 1
12
出力例 1
24 1 2 2 3 3 1 1 4 4 5 5 1 2 6 6 8 8 2 3 7 7 9 9 3 4 6 6 10 10 4 5 7 7 11 11 5 8 9 9 12 12 8 10 11 11 12 12 10
入力例 2
2
出力例 2
-1
条件を満たすグラフが存在しない場合 -1 を出力してください。
Score : 800 points
Problem Statement
You are given an integer N. Determine whether there exists a simple connected undirected graph with N vertices numbered 1 to N that satisfies the following condition, and if it exists, show one such graph.
- There exists an integer X such that for any vertex v, the sum of the numbers of all vertices other than v that can be reached from v by traversing an edge once or twice is X.
Constraints
- 2 \le N \le 200
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
Output
If there does not exist a simple connected undirected graph with N vertices satisfying the condition in the problem statement, print -1. If it exists, print the number of edges M on the first line. On the i-th of the following M lines, print two integers. These represent the vertex numbers of the endpoints of the i-th edge.
Any constructed graph that satisfies the condition will be accepted.
Sample Input 1
12
Sample Output 1
24 1 2 2 3 3 1 1 4 4 5 5 1 2 6 6 8 8 2 3 7 7 9 9 3 4 6 6 10 10 4 5 7 7 11 11 5 8 9 9 12 12 8 10 11 11 12 12 10
Sample Input 2
2
Sample Output 2
-1
If there does not exist a graph satisfying the condition, print -1.