AT_abc251_f [ABC251F] Two Spanning Trees

[problemUrl]: https://atcoder.jp/contests/abc251/tasks/abc251_f $ N $ 頂点 $ M $ 辺の無向グラフ $ G $ が与えられます。 $ G $ は**単純**（自己ループおよび多重辺を持たない）かつ**連結**です。 $ i\ =\ 1,\ 2,\ \ldots,\ M $ について、$ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結ぶ無向辺 $ \lbrace\ u_i,\ v_i\ \rbrace $ です。 下記の $ 2 $ つの条件をともに満たすような $ G $ の $ 2 $ つの全域木 $ T_1,T_2 $ を $ 1 $ 組構成してください。（ $ T_1 $ と $ T_2 $ は異なる全域木である必要はありません。） - $ T_1 $ は下記を満たす。 > $ T_1 $ を頂点 $ 1 $ を根とする根付き木とみなしたとき、$ G $ の辺のうち $ T_1 $ に含まれないすべての辺 $ \lbrace\ u,\ v\ \rbrace $ について、$ u $ と $ v $ は $ T_1 $ において祖先と子孫の関係にある。 - $ T_2 $ は下記を満たす。 > $ T_2 $ を頂点 $ 1 $ を根とする根付き木とみなしたとき、$ G $ の辺のうち $ T_2 $ に含まれない辺 $ \lbrace\ u,\ v\ \rbrace $ であって、$ u $ と $ v $ が $ T_2 $ において祖先と子孫の関係にあるようなものは存在しない。 ここで、「根付き木 $ T $ において頂点 $ u $ と頂点 $ v $ が祖先と子孫の関係にある」とは、「 $ T $ において $ u $ が $ v $ の祖先である」と「 $ T $ において $ v $ が $ u $ の祖先である」のうちどちらかが成り立つことをいいます。 本問題の制約下において上記の条件を満たす $ T_1 $ と $ T_2 $ は必ず存在することが示せます。

N/A

N/A

### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ N-1\ \leq\ M\ \leq\ \min\lbrace\ 2\ \times\ 10^5,\ N(N-1)/2\ \rbrace $ - $ 1\ \leq\ u_i,\ v_i\ \leq\ N $ - 入力はすべて整数 - 与えられるグラフは単純かつ連結 ### Sample Explanation 1 上記の出力例において、$ T_1 $ は $ 5 $ 本の辺 $ \lbrace\ 1,\ 4\ \rbrace,\ \lbrace\ 4,\ 3\ \rbrace,\ \lbrace\ 5,\ 3\ \rbrace,\ \lbrace\ 4,\ 2\ \rbrace,\ \lbrace\ 6,\ 2\ \rbrace $ を持つ $ G $ の全域木です。この $ T_1 $ は問題文中の条件を満たします。実際、$ G $ の辺のうち $ T_1 $ に含まれない各辺に関して、 - 辺 $ \lbrace\ 5,\ 1\ \rbrace $ について、頂点 $ 1 $ は頂点 $ 5 $ の祖先であり、 - 辺 $ \lbrace\ 1,\ 2\ \rbrace $ について、頂点 $ 1 $ は頂点 $ 2 $ の祖先であり、 - 辺 $ \lbrace\ 1,\ 6\ \rbrace $ について、頂点 $ 1 $ は頂点 $ 6 $ の祖先です。 また、$ T_2 $ は $ 5 $ 本の辺 $ \lbrace\ 1,\ 5\ \rbrace,\ \lbrace\ 5,\ 3\ \rbrace,\ \lbrace\ 1,\ 4\ \rbrace,\ \lbrace\ 2,\ 1\ \rbrace,\ \lbrace\ 1,\ 6\ \rbrace $ を持つ $ G $ の全域木です。この $ T_2 $ は問題文中の条件を満たします。実際、$ G $ の辺のうち $ T_2 $ に含まれない各辺に関して、 - 辺 $ \lbrace\ 4,\ 3\ \rbrace $ について、頂点 $ 4 $ と頂点 $ 3 $ は祖先と子孫の関係になく、 - 辺 $ \lbrace\ 2,\ 6\ \rbrace $ について、頂点 $ 2 $ と頂点 $ 6 $ は祖先と子孫の関係になく、 - 辺 $ \lbrace\ 4,\ 2\ \rbrace $ について、頂点 $ 4 $ と頂点 $ 2 $ は祖先と子孫の関係にありません。 ### Sample Explanation 2 $ 3 $ 本の辺 $ \lbrace\ 1,\ 2\rbrace,\ \lbrace\ 1,\ 3\ \rbrace,\ \lbrace\ 1,\ 4\ \rbrace $ を持つ木 $ T $ が $ G $ の唯一の全域木です。 $ G $ の辺のうちこの木 $ T $ に含まれない辺は存在しないので、明らかに、$ T $ は $ T_1 $ の条件と $ T_2 $ の条件をともに満たします。