B - Balanced Neighbors 2 Editorial /

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.