問題一覧 > 通常問題

No.3735 Offbeat Permutation Tree

レベル : / AI推定難易度 : 2400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 26
作問者 : 👑 kencho / テスター : uruzunyaa
お気に入りにしたユーザー ProblemId : 13738 / 自分の提出
問題文最終更新日: 2026-11-02 04:28:14
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
グリッド構築24題 (順位表) の他の問題:

Story

Do you know what a Permutation Tree is? Whether you knew about it or not, everyone is equal in this problem.

Problem Statement

There is a grid graph $G$ whose vertices are arranged in $N$ rows and $N$ columns. For $1 \leq i, j \leq N$, the vertex of $G$ in the $i$-th row from the top and the $j$-th column from the left is numbered $(i - 1) N + j$.

Find one example of a spanning tree $T$ of $G$ that satisfies all of the following conditions. Here, a leaf of $T$ is a vertex whose degree in $T$ is $1$.

  • For $1 \leq i \leq N$, exactly $1$ of the vertices in the $i$-th row from the top is a leaf of $T$.
  • For $1 \leq j \leq N$, exactly $1$ of the vertices in the $j$-th column from the left is a leaf of $T$.

If no $T$ satisfying the conditions exists, print -1.

Constraints

  • All input values are integers.
  • $2 \leq N \leq 500$

Input

The input is given from Standard Input in the following format.

$N$

Output

Print the edges of $T$ in the following format, where $s_i, t_i$ are the numbers of the $2$ vertices connected by the $i$-th edge.

$s_1\ t_1$
$s_2\ t_2$
$\vdots$
$s_{N^2-1}\ t_{N^2-1}$

If no $T$ satisfying the conditions exists, print -1.

Print a newline at the end.

Visualizer

A web-based visualizer for the output is available here.

During the contest, sharing visualization results and mentioning solutions or analysis are prohibited. Please be careful.

In principle, we do not accept questions about the specifications of the visualizer. Please use it only as an auxiliary tool.

Sample

Sample 1
Input
4
Output
1 2
3 4
1 5
2 6
4 8
6 7
7 8
7 11
9 10
11 12
9 13
11 15
12 16
13 14
14 15

The tree is as shown in the figure below, and vertices $3, 5, 10, 16$ are the leaves.

Sample 2
Input
2
Output
-1

There are $4$ possible spanning trees of $G$, but none of them satisfies the conditions.

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