AT_xmascon17_f Tree Disassembly

[problemUrl]: https://atcoder.jp/contests/xmascon17/tasks/xmascon17_f *クリスマスツリーを持った青いうさぎと赤いうなぎがぶつかってしまい、二つのツリーがこんがらがってしまいました。* - - - - - - $ N $ 頂点からなるグラフが与えられます。 頂点には $ 1 $ 〜 $ N $ の番号がつけられています。 辺は $ N*2-2 $ 本あり、$ i $ 番目の辺は頂点 $ A_i $ と頂点 $ B_i $ を繋いでいます。 このグラフの辺を赤と青に塗り分ける方法であって、赤い辺のみからなるグラフも青い辺のみからなるグラフも木になるようなものは何通りあるでしょうか？ 答えは非常に大きくなることがあるので、$ 10^9+7 $ で割ったあまりを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ : $ $ A_{N*2-2} $ $ B_{N*2-2} $

答えを $ 10^9+7 $ で割った余りを出力せよ。

### 制約 - $ 4\ \leq\ N\ \leq\ 104 $ - $ 1\ \leq\ A_i,B_i\ \leq\ N $ - 自己ループや多重辺は存在しない - 問題文中の条件を満たす塗り分け方が少なくとも $ 1 $ 通り以上存在する ### 採点 テストケースは `01.txt` 〜 `10.txt` の $ 10 $ 個あり、テストケースに $ 1 $ つ正解するごとに $ 10 $ 点が与えられます。 **この問題ではテストケースが公開されており、[こちら](https://img.atcoder.jp/xmascon17/tree_input.zip)からダウンロードすることができます。** ### Sample Explanation 1 このケースでは以下の $ 12 $ 通りの塗り分け方があります。 !\[\](https://img.atcoder.jp/xmascon17/7740d37671351f1f218f0e3151f5e9ec.png)図：塗り分け方の一覧