No.3047 Verification of Sorting Network

問題文

「比較器」と呼ばれる単純な装置があります。これは $2$ つの入力の値を比較し、大きい値を後ろに配置するように出力します。こうした比較器を組み合わせた「比較ネットワーク」を適切に構成すると、入力列を並び替えて非減少列を出力する「ソーティングネットワーク」となります。

問題

$T$ 個の比較ネットワークが与えられます。 $i$ 番目 $(1\leq i\leq T)$ の比較ネットワークは、長さ $N_i$ の入出力列を扱い、 $M_i$ 個の比較器 $(A_{i,j},B_{i,j})$ から構成されます。

$i$ 番目の比較ネットワークについては、それぞれ $N_i,M_i,(A_{i,j},B_{i,j})$ を $N,M,(A_j,B_j)$ と略記する場合があります。

与えられた $T$ 個の比較ネットワークがそれぞれ 「ソーティングネットワーク」であるかどうか を判定してください。

比較ネットワークが「ソーティングネットワーク」である場合：長さ $N$ の任意の入力列に対して、比較ネットワークの操作列 $W$ の時刻 $j$ において $W[A_j]\leq W[B_j]$ が常に成立し、 一度も交換が行われない比較器番号 $j\ \ (1\leq j\leq M)$ を、昇順ですべて出力してください。
比較ネットワークが「ソーティングネットワークではない」場合：長さ $N$ の任意の入力列に対して、比較ネットワークの出力列 $Y$ において $Y[k]\gt Y[k+1]$ が起こり得る、 隣接要素が非減少順にならない可能性のある位置 $k\ \ (1\leq k\leq N-1)$ を、昇順ですべて出力してください。

比較器とは

$2$ つの入力と $2$ つの出力を持ちます。
入力 $(\alpha,\beta)$ に対して、 $\alpha\leq\beta$ なら $(\alpha,\beta)$ を出力します。
入力 $(\alpha,\beta)$ に対して、 $\alpha\gt\beta$ なら $(\beta,\alpha)$ を出力します。

比較ネットワークとは

比較器 $1\leq j\leq M$ において $1\leq A_{j}\lt B_{j}\leq N$
比較ネットワークへの入力列 $X$ は整数 $\{1,2,\dots,N\}$ からなる数列（線形順序（全順序）集合の要素からなる列に一般化できます）
入力列 $X$ は長さ $N$ の列で、 $X=[X[1],X[2],\dots,X[N]]$ と表される
操作列 $W$ は長さ $N$ の列で、 $W=[W[1],W[2],\dots,W[N]]$ と表される
出力列 $Y$ は長さ $N$ の列で、 $Y=[Y[1],Y[2],\dots,Y[N]]$ と表される

比較ネットワークは、処理の開始時刻を $0$ とした時、次のように動作します。

時刻 $0$ : 入力列 $X$ を受け取り、操作列 $W$ にコピーします。
時刻 $1$ : $W[A_{1}]$ と $W[B_{1}]$ を比較し、 $W[A_{1}]\gt W[B_{1}]$ ならば、 $W[A_{1}]$ と $W[B_{1}]$ の値を交換します。
時刻 $2$ : $W[A_{2}]$ と $W[B_{2}]$ を比較し、 $W[A_{2}]\gt W[B_{2}]$ ならば、 $W[A_{2}]$ と $W[B_{2}]$ の値を交換します。

$\vdots$
時刻 $M$ : $W[A_{M}]$ と $W[B_{M}]$ を比較し、 $W[A_{M}]\gt W[B_{M}]$ ならば、 $W[A_{M}]$ と $W[B_{M}]$ の値を交換します。
時刻 $(M+1)$ : 操作列 $W$ を出力列 $Y$ にコピーし、出力します。

ソーティングネットワークとは

任意の長さ $N$ の入力列 $X$ に対して、常に非減少列 $Y[1]\leq Y[2]\leq\dots\leq Y[N]$ を出力する「比較ネットワーク」を「ソーティングネットワーク」と呼びます。

逆に、比較ネットワークが非減少列を出力できない入力列が存在する場合、その「比較ネットワーク」は「ソーティングネットワークではない」です。

制約

入力はすべて整数
$1\leq T\leq 1000$
$2\leq N_i\leq 27\quad(1\leq i\leq T)$
$1\leq M_i\leq\cfrac{N_i(N_i-1)}{2}\quad(1\leq i\leq T)$
$1\leq A_{i,j}\lt B_{i,j}\leq N_i\quad(1\leq i\leq T,\ 1\leq j\leq M_i)$
$\sum_{i=1}^{T}(M_i\times\varphi^{N_i})\leq 10^{8}$
$\varphi=\dfrac{1+\sqrt{5}}{2}\simeq 1.6180339887$

入力

入力は以下の形式で標準入力から与えられる。ここで $\mathrm{case}_i$ は $i$ 番目のテストケースを意味する。

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

各テストケースは以下の形式で与えられる。

$N\ M$
$A_1\ A_2\ A_3 \dots A_M$
$B_1\ B_2\ B_3 \dots B_M$

出力

$1$ テストケースごとに $3$ 行、全体で $3T$ 行出力せよ。

$i$ 番目 $(1\leq i\leq T)$ のテストケースで与えられた比較ネットワークが「ソーティングネットワーク」と判定した場合は次のように $3$ 行出力せよ。
- $1$ 行目に、 Yes
- $2$ 行目に、該当する比較器番号 $j$ の個数
- $3$ 行目に、該当する比較器番号 $j$ を昇順で空白区切りに出力（個数が $0$ 個の場合は空行）
$i$ 番目 $(1\leq i\leq T)$ のテストケースで与えられた比較ネットワークが「ソーティングネットワークではない」と判定した場合は次のように $3$ 行出力せよ。
- $1$ 行目に、 No
- $2$ 行目に、該当する位置 $k$ の個数
- $3$ 行目に、該当する位置 $k$ を昇順で空白区切りに出力

サンプル

サンプル1

入力

4
2 1
1
2
4 5
1 3 1 2 2
2 4 3 4 3
4 6
1 3 1 2 2 3
2 4 3 4 3 4
4 5
1 3 2 1 3
2 4 3 2 4

出力

Yes
0

Yes
0

Yes
1
6
No
1
2

以下の図は比較ネットワークの模式図で、横線の左端が入力、右端が出力を表しています。縦線は比較器を表しています。

比較ネットワークにおいてはどの比較器の出力も、ネットワークの出力か、他の比較器の入力に接続されます。比較ネットワークは有向非巡回グラフ構造を取るため、出力から入力へと辿っていって同じ比較器に戻るような閉路は存在しません。このため、図のように左から右へ値が流れていく形で描くことができます。

$1$ 番目のテストケースは、 $2$ 入力の最も単純な「ソーティングネットワーク」です。
```
2 1
1
2
```
$i=1,\ (N_1,M_1)=(2,1),\ [(A_{1,j},B_{1,j})]=[(1,2)]$

この比較ネットワークに例えば $[1,1],\ [2,2],\ [1,2],\ [2,1]$ の整数列をそれぞれ入力した場合、このようになります。
- $X=[1,1]$ が入力された場合、この比較ネットワークは非減少列 $Y=[1,1]$ を出力します。
- $X=[2,2]$ が入力された場合、この比較ネットワークは非減少列 $Y=[2,2]$ を出力します。
- $X=[1,2]$ が入力された場合、この比較ネットワークは非減少列 $Y=[1,2]$ を出力します。
- $X=[2,1]$ が入力された場合、この比較ネットワークは非減少列 $Y=[1,2]$ を出力します。
長さ $2$ のすべての入力列に対し、この比較ネットワークは非減少列を出力します。この比較ネットワークは 「ソーティングネットワーク」です。

$1$ 番目の出力:
```
Yes
0
```
$2$ 番目のテストケースは、 $4$ 入力の「ソーティングネットワーク」の例です。
```
4 5
1 3 1 2 2
2 4 3 4 3
```
$i=2,\ (N_2,M_2)=(4,5),\ [(A_{2,j},B_{2,j})]=[(1,2),(3,4),(1,3),(2,4),(2,3)]$

この比較ネットワークに例えば $X=[4,3,2,1]$ の整数列を入力した場合、このようになります。
- 時刻 $0:$ 初期状態では、入力列 $X$ をコピーして $W=[4,3,2,1]$ です。
- 時刻 $1:$ $1,2$ 番目の要素を比較し、 $W=[3,4,2,1]$ となります。
- 時刻 $2:$ $3,4$ 番目の要素を比較し、 $W=[3,4,1,2]$ となります。
- 時刻 $3:$ $1,3$ 番目の要素を比較し、 $W=[1,4,3,2]$ となります。
- 時刻 $4:$ $2,4$ 番目の要素を比較し、 $W=[1,2,3,4]$ となります。
- 時刻 $5:$ $2,3$ 番目の要素を比較し、 $W=[1,2,3,4]$ となります。
- 時刻 $6:$ $W=[1,2,3,4]$ を出力列 $Y$ として出力します。
この比較ネットワークに例えば $X=[4,2,3,1]$ の整数列を入力した場合、このようになります。
- 時刻 $0:$ 初期状態では、入力列 $X$ をコピーして $W=[4,2,3,1]$ です。
- 時刻 $1:$ $1,2$ 番目の要素を比較し、 $W=[2,4,3,1]$ となります。
- 時刻 $2:$ $3,4$ 番目の要素を比較し、 $W=[2,4,1,3]$ となります。
- 時刻 $3:$ $1,3$ 番目の要素を比較し、 $W=[1,4,2,3]$ となります。
- 時刻 $4:$ $2,4$ 番目の要素を比較し、 $W=[1,3,2,4]$ となります。
- 時刻 $5:$ $2,3$ 番目の要素を比較し、 $W=[1,2,3,4]$ となります。
- 時刻 $6:$ $W=[1,2,3,4]$ を出力列 $Y$ として出力します。
この比較ネットワークは、他の長さ $4$ の入力列についても常に非減少列を出力する「ソーティングネットワーク」です。

$2$ 番目の出力:
```
Yes
0
```
$3$ 番目のテストケースもまた「ソーティングネットワーク」ですが、赤線で描いた $6$ 番目の比較器はどのような入力に対しても交換の操作が行われる事がありません。
```
4 6
1 3 1 2 2 3
2 4 3 4 3 4
```
$i=3,\ (N_3,M_3)=(4,6),\ [(A_{3,j},B_{3,j})]=[(1,2),(3,4),(1,3),(2,4),(2,3),(3,4)]$

$3$ 番目の出力:
```
Yes
1
6
```
$4$ 番目のテストケースは $4$ 入力の比較ネットワークですが、これは「ソーティングネットワークではない」です。
```
4 5
1 3 2 1 3
2 4 3 2 4
```
$i=4,\ (N_4,M_4)=(4,5),\ [(A_{4,j},B_{4,j})]=[(1,2),(3,4),(2,3),(1,2),(3,4)]$

この比較ネットワークに例えば $X=[4,3,2,1]$ の整数列を入力した場合、このようになります。
- 時刻 $0:$ 初期状態では、入力列 $X$ をコピーして $W=[4,3,2,1]$ です。
- 時刻 $1:$ $1,2$ 番目の要素を比較し、 $W=[3,4,2,1]$ となります。
- 時刻 $2:$ $3,4$ 番目の要素を比較し、 $W=[3,4,1,2]$ となります。
- 時刻 $3:$ $2,3$ 番目の要素を比較し、 $W=[3,1,4,2]$ となります。
- 時刻 $4:$ $1,2$ 番目の要素を比較し、 $W=[1,3,4,2]$ となります。
- 時刻 $5:$ $3,4$ 番目の要素を比較し、 $W=[1,3,2,4]$ となります。
- 時刻 $6:$ $W=[1,3,2,4]$ を出力列 $Y$ として出力します。
$[1,3,2,4]$ は非減少順に並び替えられていないため、 $4$ 個目のテストケースで与えられた比較ネットワークは「ソーティングネットワーク」ではありません。

$Y[2]\gt Y[3]$ となっているため、この入力列の場合は $k=2$ の時に $Y[k]\gt Y[k+1]$ となります。また、長さ $N_i$ のどのような入力列においても $k\neq 2$ の場合は $Y[k]\gt Y[k+1]$ とならないため、 赤点を付けた位置の $k=2$ の時のみ $Y[k]\gt Y[k+1]$ となる可能性がある として出力します。

$4$ 番目の出力:
```
No
1
2
```

サンプル2

入力

4
8 28
1 3 5 7 2 4 6 1 3 5 7 2 4 6 1 3 5 7 2 4 6 1 3 5 7 2 4 6
2 4 6 8 3 5 7 2 4 6 8 3 5 7 2 4 6 8 3 5 7 2 4 6 8 3 5 7
8 24
1 3 5 7 1 2 5 6 1 3 5 7 1 2 3 4 1 2 5 6 1 3 5 7
2 4 6 8 4 3 8 7 2 4 6 8 8 7 6 5 3 4 7 8 2 4 6 8
8 19
1 3 5 7 1 2 5 6 2 6 1 2 3 4 3 4 2 4 6
2 4 6 8 3 4 7 8 3 7 5 6 7 8 5 6 3 5 7
8 19
1 3 5 7 1 5 2 6 1 2 3 4 3 4 2 4 2 4 6
2 4 6 8 3 7 4 8 5 6 7 8 5 6 5 7 3 5 7

出力

Yes
0

Yes
0

Yes
0

Yes
0

これらの比較ネットワークはいずれも、入力列を常に非減少順に並び替えて出力する「ソーティングネットワーク」です。

奇偶転置ソート

バイトニックソート

バッチャー奇偶マージソート

ペアワイズソート

サンプル3

入力

2
26 142
1 3 5 7 9 11 13 15 17 19 21 23 25 1 2 5 6 9 10 15 16 19 20 23 24 1 2 3 4 9 10 11 12 13 19 20 21 22 1 2 3 4 5 6 7 8 9 11 12 14 2 3 4 5 6 7 8 10 12 14 16 18 1 2 4 6 7 8 9 11 13 15 17 22 3 4 6 9 11 14 15 17 22 2 4 7 8 10 13 15 16 18 22 2 4 5 8 9 10 12 14 16 20 21 24 3 5 6 8 12 13 16 17 20 23 4 6 8 10 12 14 16 18 20 22 6 7 10 11 14 15 18 19 5 7 9 11 13 15 17 19 21
2 4 6 8 10 12 14 16 18 20 22 24 26 3 4 7 8 11 12 17 18 21 22 25 26 5 6 7 8 15 17 14 18 16 23 24 25 26 19 20 21 22 23 24 25 26 13 15 16 18 19 11 21 9 23 15 25 13 20 17 24 22 5 10 14 16 19 20 12 21 23 18 25 26 5 12 10 18 13 16 23 21 24 5 9 11 14 12 19 17 20 23 25 3 7 6 13 11 15 17 19 18 23 22 25 4 7 11 10 14 15 21 19 22 24 5 7 9 11 13 15 17 19 21 23 8 9 12 13 16 17 20 21 6 8 10 12 14 16 18 20 22
26 177
1 3 5 7 9 11 15 17 19 21 23 25 1 2 5 6 9 10 15 16 19 20 23 24 13 22 6 4 8 12 17 2 14 3 10 18 1 9 8 5 11 16 15 7 6 2 18 19 1 25 15 19 3 13 23 10 5 14 4 9 20 1 7 16 13 17 22 8 21 6 3 12 2 1 24 15 19 10 12 14 18 4 7 23 2 3 20 9 13 11 16 18 8 21 5 4 23 2 25 10 15 12 17 8 20 6 11 22 4 24 1 15 13 17 10 19 7 21 5 3 23 16 13 9 18 11 7 20 4 22 2 24 14 11 12 8 19 10 6 21 4 2 23 14 12 17 10 7 20 15 5 22 3 14 11 18 16 9 6 21 4 23 15 13 19 17 8 10 5 12 16 14 20 18 7 9 4
2 4 6 8 10 12 16 18 20 22 24 26 3 4 7 8 11 12 17 18 21 22 25 26 15 23 16 9 25 19 21 11 24 5 20 26 7 22 10 17 13 24 21 14 12 3 20 23 4 26 18 21 7 17 24 12 6 16 8 11 22 2 15 19 14 18 23 10 25 9 4 20 11 5 26 17 21 11 13 16 22 9 8 25 5 6 24 10 15 12 17 20 14 22 6 7 24 3 26 13 18 14 19 9 21 7 16 23 5 25 2 16 14 18 11 20 9 22 6 4 24 17 15 10 19 12 8 21 6 23 5 25 17 13 15 9 20 16 7 22 5 3 24 16 13 18 11 8 21 19 6 23 4 15 12 19 17 10 7 22 5 24 16 14 20 18 9 11 6 13 17 15 21 19 8 10 5

出力

Yes
1
78
No
7
3 6 11 13 15 19 21

yukicoder