No.3341 Making Beautiful Graphs
タグ : / 解いたユーザー数 58
作問者 :
noya2
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もしくは右上の雲マークをクリックしてアカウントを作成してください。