問題一覧 > 通常問題

No.3341 Making Beautiful Graphs

レベル : / AI推定難易度 : 1450 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 58
作問者 : toka0428 / テスター : ponjuice jupiter_68 りすりす/TwoSquirrels noya2
お気に入りにしたユーザー ProblemId : 12802 / 自分の提出
問題文最終更新日: 2025-11-13 13:58:27
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 作問ハッカソンコンテスト 003 Day1 (順位表) の他の問題:

Problem Statement

You are given an integer $N$. A simple connected undirected graph with $N^{2}$ vertices numbered from $1$ to $N^{2}$ is called a beautiful graph if it satisfies all of the following conditions.

  • For every pair of integers ($i,j$) satisfying ($1 \leq i < j \leq N^2$), the length of the shortest path between vertex $i$ and vertex $j$ is at most $N$.
  • The degree of every vertex is 4.
  • For every integer $i$ satisfying ($1 \leq i \leq N^2$), letting $A_i$ be the sum of the numbers of the 4 vertices adjacent to $i$, it holds that $4i \equiv A_i \pmod{N^2}$.

Here, a graph is simple and connected if it has no self-loops (edges whose $2$ endpoints are the same vertex) or multiple edges (several edges between the same $2$ vertices), and any $2$ vertices can be reached from each other by following edges.

Determine whether a beautiful graph exists, and if it exists, show $1$ example of one.

Constraints

  • $1 \leq N \leq 50$
  • All input values are integers.

Input

The input is given from standard input in the following format.

$N$

Output

If no beautiful graph exists, print $-1$. If one exists, print the number of edges $M$ on line $1$. On the $i$-th of the following $M$ lines, print $2$ integers separated by a space. These represent the vertex numbers of the endpoints of the $i$-th edge. Your answer is judged as correct if the constructed graph is a beautiful graph.

Sample

Sample 1
Input
3
Output
18
1 3
1 5
1 6
1 8
2 4
2 6
2 7
2 9
3 5
3 7
3 8
4 6
4 8
4 9
5 7
5 9
6 8
7 9
Sample 2
Input
2
Output
-1
  • There is no simple undirected graph with $2^2$ vertices in which the degree of every vertex is $4$. Therefore it is impossible to construct a good graph, so print $-1$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。