E - ネットワークの構築
解説
/
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 1400 点
問題文
すぬけ君は 1 から N の番号がついた N 頂点の有向グラフを持っています。はじめ、このグラフには辺はありません。 すぬけ君の仕事はこのグラフに M 本の辺を追加して、任意の頂点のペア (u,v) について u から v へと辺を辿って到達できるようにすることです。
辺の追加には長さ M の数列 a,b を用います。 すぬけ君は a,b をそれぞれ自由に並び替えたあと (a,b 間で要素の交換をすることはできません)、これらの数列を使ってこのグラフに M 本の有向辺を追加します。
すぬけ君は i 番目の辺として、以下のどちらかの辺を追加することができます。
- 頂点 a_i から b_i へ向かう有向辺
- 頂点 b_i から a_i へ向かう有向辺
すぬけ君の仕事は達成可能ですか?可能ならばそのような辺の追加仕方の一例を示してください。
制約
- 1 \leq N , M \leq 2 \times 10^{5}
- 1 \leq a_i, b_i \leq N
- 与えられる入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M a_1 a_2 ... a_{M} b_1 b_2 ... b_{M}
出力
すぬけ君の仕事が達成可能ならば Yes
を、そうでなければ No
を出力せよ。
達成可能な場合、続く M 行に以下のフォーマットで辺の追加の仕方を出力せよ。
x_1 c_1 y_1 : x_{M} c_{M} y_{M}
ここで、c_i が >
ならば x_i から y_i に向かう有向辺を、c_i が <
ならば y_i から x_i に向かう有向辺を追加したことを表す。
x,y がそれぞれ a,b を並び替えた数列であり、任意の頂点のペア u,v について u から v へと辺を辿って到達可能ならば正解となる。
入力例 1
3 6 1 2 3 1 1 1 3 2 1 1 1 2
出力例 1
Yes 1 > 2 1 < 2 1 > 3 3 > 1 1 < 1 2 > 1
- 以下の図のようなグラフを構成することで、すぬけ君は仕事を達成することが可能です。
- 最終的なグラフに多重辺や自己ループが含まれていても構わないことに注意してください。
入力例 2
3 1 1 2
出力例 2
No
- どのように辺を追加してもすぬけ君は仕事を達成することができません。
入力例 3
13 29 2 8 4 5 5 8 2 9 2 5 9 4 3 8 4 2 12 4 4 12 8 8 3 12 3 9 4 8 9 6 1 1 11 12 6 9 12 6 13 10 11 13 6 10 10 11 3 10 13 10 13 7 7 11 7 11 10 12
出力例 3
Yes 2 > 6 12 < 1 5 > 1 4 > 11 2 < 12 12 < 6 4 < 9 3 > 12 8 < 6 9 > 13 4 < 10 3 < 11 4 < 13 2 < 6 8 > 10 5 > 10 4 < 11 12 < 3 8 < 10 9 < 13 4 > 10 9 < 13 8 > 7 8 < 7 5 < 11 2 < 7 9 < 11 8 < 10 3 > 12