Canmuu と友達は大量のプルトニウムを手に入れ、カナダの荒野の奥の交差点に新しい宝を埋めることにしました。埋めるなら地図が必要なので自分で作ります。

道路網は $N$ $(4 \le N \le 100,000)$ 交差点（番号 $1..N$）と $N$ 道路です。混雑した交差点は混乱を招くため、各点に1本以上4本以下の道があります。良い整備によりヘラジカは任意の2交差点間を両方向に走れます。Canmuu は交通量が秘密性を下げるので四差路には埋めません。

地図は全道路と交差点を含みますが、宝の位置を隠すため埋めた交差点だけを当然大きな赤い 'X' で示します。

注意深いヘラジカ Canmuu は埋める場所ごとの試作地図を描き、2か所が違っても似た地図ができると気付きました。好奇心から群れは異なる地図が何枚できるか考え始めました。

次の対応を作れる地図は同じです。

• 両地図の X の交差点が対応する。

• ほかの交差点にも対応を作れ、

• 交差点の対応を選ぶと、それらを結ぶ道路も対応する。

例えば下図は $N = 4$ で、4交差点のどこにも埋められます。

        +             +             X           +
       /|            /|            /|          /|
  X---+ |       +---X |       +---+ |     +---+ |
       \|            \|            \|          \|
        +             +             +           X

最後の2地図は同じです。頂点の対応を作ると（図を逆さに見る）、道も完全に対応します。異なる地図は3枚だけです。

与えられた道路で何枚の異なる地図が可能ですか？

*本問の最初の10回の提出には追加フィードバックがあります。

入力

標準入力から読みます。

• 1行目：整数 $N$。

• 2..$N + 1$ 行目：空白区切り2整数 $A$、$B$ $(1 \le A \le N; 1 \le B \le N)$、交差点 $A$、$B$ を結ぶ道を表します。

出力

標準出力に書きます。

• 1行目：異なる宝の地図の枚数を整数1個で出力します。

入出力例

入力 1

4
1 2
2 3
3 1
1 4

出力 1

3

注記

道路と交差点の図です。

                   4---1---2
                        \ /
                         3

どの交差点にも埋められますが、2と3は同じ地図になります。したがって異なる宝の地図は3枚です。

問題作成：Yang Yi、2007