AT_arc111_d [ARC111D] Orientation

[problemUrl]: https://atcoder.jp/contests/arc111/tasks/arc111_d $ N $ 頂点 $ M $ 辺の単純な無向グラフが与えられます。頂点には $ 1,\ \cdots,\ N $ の番号がついています。$ i $ 番目の辺は頂点 $ a_i $, $ b_i $ を繋いでいます。 また、正整数列 $ c_1,\ c_2,\ \cdots,\ c_N $ も与えられます。 このグラフを、次の条件を満たすように有向グラフに変換してください。つまり、各 $ i $ について無向辺 $ (a_i,\ b_i) $ を削除し、有向辺 $ a_i\ \to\ b_i $、$ b_i\ \to\ a_i $ のどちらか $ 1 $ つを張ってください。 - 全ての $ i\ =\ 1,\ 2,\ \cdots,\ N $ について、頂点 $ i $ から(有向辺を好きな回数使うことで)到達可能な頂点数がちょうど $ c_i $ 個。なお、頂点 $ i $ 自身も $ 1 $ 個と数える。 なお、この問題では、**解が存在する**ような入力のみが与えられます。

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 100 $ - $ 0\ \leq\ M\ \leq\ \frac{N(N\ -\ 1)}{2} $ - $ 1\ \leq\ a_i,\ b_i\ \leq\ N $ - 与えられるグラフに自己ループや多重辺は存在しない - $ 1\ \leq\ c_i\ \leq\ N $ - **必ず題意を満たす解が存在する** ### Sample Explanation 1 長さ $ 3 $ のサイクルでは、どの頂点からも全ての頂点に到達できます。 ### Sample Explanation 3 グラフは非連結のこともあります。