問題一覧 > 通常問題

No.1647 Travel in Mitaru city 2

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 64
作問者 : 蜜蜂蜜蜂 / テスター : MitarushiMitarushi 👑 ygussanyygussany
0 ProblemId : 6788 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-13 23:56:30

問題文

ミタル市は $H \times W$ のマス目で表すことのできる町です。上から $i$ 番目の行、左から $j$ 番目の列にあるマスを $(i,j)$ と表記します。
ミタル市には $N$ 個の観光名所があり、 $i$ 番目の観光名所は $(x_i,y_i)$ にあります。

ここで、長さ $X$ の正整数列 $T$ が以下を満たすとき いい旅路 とします。ただし、 $T_i$ を $T$ の第 $i$ 項とし、 $T_{X+1}$ を $T_1$ とみなします。

  • $X \geq 4$
  • $1 \leq T_i \leq N$ $(\ 1 \leq i \leq X\ )$
  • $T_i \neq T_j$ $(\ i \neq j\ )$
  • 整数 $i$ が $1 \leq i \leq X$ を満たすとき、以下が成り立つ。
    • $i$ が偶数の時、 $T_i$ 番目の観光名所と $T_{i+1}$ 番目の観光名所は同じ行にある。すなわち、 $x_{T_i}=x_{T_{i+1}}$ が成立する。
    • $i$ が奇数の時、 $T_i$ 番目の観光名所と $T_{i+1}$ 番目の観光名所は同じ列にある。すなわち、 $y_{T_i}=y_{T_{i+1}}$ が成立する。

いい旅路 が存在するか判定し、存在する場合はそのうちの $1$ つを示してください。

入力

$H\ \ W\ \ N$
$x_1\ \ y_1$
$x_2\ \ y_2$
$\vdots$
$x_N\ \ y_N$

  • $2 \leq H,W \leq 10^5$
  • $4 \leq N \leq \mathrm{min}(H \times W,10^5)$
  • $1 \leq x_i \leq H$ ( $1 \leq i \leq N$ )
  • $1 \leq y_i \leq W$ ( $1 \leq i \leq N$ )
  • $(x_i,y_i)$ は相異なる
  • 入力は全て整数

出力

いい旅路 が存在しない時は -1 を出力し、改行してください。
存在するときはそのうちの $1$ つを以下の形式で出力してください。解が複数ある場合、どれを出力しても構いません。

$X$
$T_1\ \ T_2\ \ \cdots T_X$

サンプル

サンプル1
入力
2 2 4
1 1
1 2
2 1
2 2
出力
4
1 3 4 2

この他に、以下のような出力も正解となります。

4
4 2 1 3

サンプル2
入力
3 3 4
1 1
2 2
3 3
1 3
出力
-1

サンプル3
入力
4 4 8
1 1
3 1
3 3
2 3
2 2
4 2
4 4
1 4
出力
8
1 2 3 4 5 6 7 8

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