問題一覧 > 通常問題

No.261 ぐるぐるぐるぐる!あみだくじ!

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 35
作問者 : koyumeishikoyumeishi
3 ProblemId : 655 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-12-09 03:12:24

この問題は No.101 ぐるぐる!あみだくじ! の続編です。 まだ解いていない方は先にNo.101を解いた方が良いかもしれません。

問題文

太郎君はまた数列 $1, 2, ... , N$ を あみだくじ でシャッフルして遊んでいます。
以前は「同じあみだくじを使って最低何回シャッフルすると、元の列に戻るか」気になっていた太郎君ですが、 それが解決した今は「同じあみだくじを使って最低何回シャッフルすると、ある数列にすることができるか」気になっています。

例えば次のあみだくじは数列 $1, 2, 3$ を $3, 1, 2$ へとシャッフルします。

このあみだくじを何回か使って $2, 3, 1$ という数列にすることを考えます。
実際に何回か繰り返しシャッフルしてみましょう。
$1, 2, 3$ → $3, 1, 2$ → $2, 3, 1$


2回シャッフルすることで元の列を $2, 3, 1$ にすることができました。

1つのあみだくじと、シャッフルして得たい$Q$個の数列が入力に与えられるので、 それぞれ最低何回シャッフルを繰り返せば得られるのか出力してください。 何度シャッフルを繰り返しても得ることのできない数列だった場合、$-1$を出力してください。
また、最低1回はシャッフルする必要があります。

入力

あみだくじは$N$本の縦線と、それに垂直な$K$本の横棒で構成されています。
$K$本の横棒はいずれも異なる高さにあり、上から$k$番目の横棒は、左から$X_k$番目の縦線と 左から$Y_k$番目の縦線を繋いでいます。
数列の$i$番目の数はあみだくじの左から$i$番目の縦線を上から下へと辿っていき、 途中で横棒と接触すると、その横棒と繋がっている縦線へ移動し、また下へとその縦線を辿っていきます。 縦線の一番下へたどり着いたとき、あみだくじの左から$j$番目の縦線にいた場合、 その数は新しくシャッフルされた数列の$j$番目の数になります。

入力は以下の形で与えられます。

$N$
$K$
$X_1$ $Y_1$
$\vdots$
$X_K$ $Y_K$
$Q$
$A_{11}$ $\dots$ $A_{1N}$
$\vdots$
$A_{Q1}$ $\dots$ $A_{QN}$

1行目に縦棒の数$N$、2行目に横棒の数$K$が与えられます。
以下$K$行に横棒の情報が与えられます。
3+$K$行目に、シャッフルして得たい数列の数$Q$が与えられます。
以下$Q$行の各行に、シャッフルして得たい数列$A_i$の$j$番目の数$A_{ij}$が空白区切りで与えられます。

入力は全て整数で、以下の制約を満たします。
$ 2 \leq N \leq 100 $
$ 0 \leq K \leq 1000 $
$ 1 \leq X_i < Y_i \leq N $
$ X_i + 1 = Y_i $
$ 1 \leq Q \leq 10$
$A_i$ は 列 $1,2, \dots , N$ を並べ替えたもの

出力

$S_1$
$\vdots$
$S_Q$

i行目には $1, 2, ... , N$ を $A_i$ にするために必要な最小のシャッフル回数 $S_i$ を出力してください。 何回シャッフルしても $A_i$ に出来ない場合は $-1$ を出力してください。

サンプル

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

$1, 3, 2$ は何度シャッフルしても得ることはできません。
また、最低1回はシャッフルしなければならないので、 $1, 2, 3$ を得るには 3回シャッフルする必要があります。

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

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

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