ストーリー

Permutation Tree を知っていますか？知っている方も知らなかった方も、この問題においては平等です。

問題文

頂点が $N$ 行 $N$ 列に並んだグリッドグラフ $G$ があります。$1 \leq i, j \leq N$ について $G$ の上から $i$ 行目、左から $j$ 列目の頂点の番号は $(i - 1) N + j$ です。

以下の条件を全て満たす $G$ の全域木 $T$ の一例を求めてください。ここで、$T$ の葉とは、$T$ における次数が $1$ である頂点のことです。

• $1 \leq i \leq N$ について、上から $i$ 行目に属する頂点のうちちょうど $1$ つが $T$ の葉である
• $1 \leq j \leq N$ について、左から $j$ 列目に属する頂点のうちちょうど $1$ つが $T$ の葉である

条件を満たす $T$ が存在しない場合は -1 を出力してください。

制約

• 入力は全て整数
• $2 \leq N \leq 500$

入力

入力は以下の形式で標準入力から与えられる。

$N$

出力

$T$ に含まれる辺を以下の形式で出力してください。ただし、$s_i, t_i$ は $i$ 番目の辺が結ぶ $2$ 頂点の番号です。

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

条件を満たす $T$ が存在しない場合は -1 を出力してください。

最後に改行してください。

ビジュアライザ

出力結果のWeb版ビジュアライザがこちらで提供されています。

コンテスト中における、ビジュアライズ結果の共有や解法・考察に関する言及は禁止されています。ご注意下さい。

また、ビジュアライザの仕様に関する質問は原則受け付けません。あくまで補助ツールとしてご利用ください。

サンプル

サンプル1

入力

4

出力

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

木は下図のようになり、頂点 $3, 5, 10, 16$ が葉です。

2

-1