K - Cycle Flip
問題文
$N$ 個の頂点 $1,2,\dots ,N$ と $M$ 本の有向辺から成る有向グラフ $S, G$ が与えられます。 以下の操作を好きな回数 ($1$ 回も行わなくても良い) 繰り返して $S$ と $G$ を一致させられるか判定し、出来るならばその操作列の一例を出力してください。
- $S$ 上の単純な有向閉路を一つ選び、その上のすべての有向辺の向きを反転する
ただし一致させられる場合、出力の操作列に含まれる閉路の長さの総和が $20000$ 以下になるようにしてください (この問題の制約下でそのような操作列が必ず存在することが証明できます)。
※有向閉路が単純であるとは、同じ頂点を二度通らないことを指します。
※入力は多重辺や自己ループを含む場合があります。
※頂点には番号が振ってあるものとします。そのため $S$ と $G$ が一致するとは、全ての頂点組 $(u,v)$ について、 $S$ 上での有向辺 $(u,v)$ と $G$ 上での有向辺 $(u,v)$ が同じ本数だけ張られていることを指します。
制約
- $1 \leq N \leq 1000$
- $1 \leq M \leq 1000$
- $1 \leq a_i, b_i, c_i, d_i \leq N$
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
$S,G$ はどちらも $N$ 個の頂点と $M$ 本の有向辺から成り、 $S$ 上には $a_i$ から $b_i$ への有向辺 ($1\leq i\leq M$) が、 $G$ 上には $c_i$ から $d_i$ への有向辺 ($1\leq i\leq M$) が張られている。
$N$ $M$
$a_1$ $b_1$
$\vdots$
$a_M$ $b_M$
$c_1$ $d_1$
$\vdots$
$c_M$ $d_M$
出力
$S$ と $G$ を一致させられないなら No を出力せよ。
$S$ と $G$ を一致させられるなら Yes を出力したのち、次の形式で操作列の一例を出力せよ。
一行目に操作の回数 $C$ を出力し、続く二行目からは操作を行う有向閉路の長さ $L_i$ と有向閉路に含まれる頂点 $u_{i1} \dots u_{iL_i}$ を有向閉路の向きに従って出力せよ。
$C$
$L_1$
$u_{11}$ $u_{12}$ $\dots$ $u_{1L_1}$
$L_2$
$u_{21}$ $u_{22}$ $\dots$ $u_{2L_2}$
$\vdots$
$L_C$
$u_{C1}$ $u_{C2}$ $\dots$ $u_{CL_C}$
4 5
1 2
2 4
3 1
3 2
4 3
1 3
2 1
3 2
3 4
4 2
Yes
2
3
2 4 3
3
1 2 3
操作 $1$ $\rightarrow$ 操作 $2$ の順番に行うと
$1\rightarrow 2\hspace{30pt}1\rightarrow 2\hspace{30pt}1\leftarrow 2$
$\uparrow\ \nearrow\ \downarrow\hspace{10pt}\Rightarrow\hspace{10pt}\uparrow\ \swarrow\ \uparrow\hspace{10pt}\Rightarrow\hspace{10pt}\downarrow\ \nearrow\ \uparrow$
$3\leftarrow 4\hspace{30pt}3\rightarrow 4\hspace{30pt}3\rightarrow 4$
となり $S$ と $G$ が一致します。
4 5
1 2
2 4
3 1
3 2
4 3
1 3
2 1
2 3
3 4
4 2
No
どのように操作を行っても $S$ と $G$ を一致させることはできません。
3 7
1 2
2 3
3 1
1 2
2 3
3 1
1 1
1 3
3 2
2 1
1 3
3 2
2 1
1 1
Yes
2
3
1 2 3
3
1 2 3
入力は多重辺や自己ループを含む場合があります。