Canmuu 和朋友最近得到大量鈽，同意把新寶藏埋在加拿大荒野深處某個路口。埋寶藏總要有藏寶圖，於是決定自己畫一張。

路網有 $N$ $(4 \le N \le 100,000)$ 個路口（編號 $1..N$），由 $N$ 條路連接。繁忙路口令人困惑，每個路口至少一條路、至多四條路。維護良好，駝鹿總能在任意兩個路口之間來回奔跑。Canmuu 決定不埋在四岔路口，因為繁忙交通會降低秘密性。

地圖包含所有路和路口。但為了隱藏寶藏位置，只標記埋寶藏的那個路口，當然用大紅 'X'。

警覺的駝鹿 Canmuu 試畫了地圖，看看埋在不同地點會怎樣。他發現埋在兩個不同地點也可能畫出相似地圖。好奇的鹿群開始研究能畫多少張不同地圖。

若能建立如下映射，兩圖視為相同：

• 兩圖標 X 的路口對應；

• 其他路口可以建立對應，使得

• 選好路口對應後，連接路口的道路也對應。

例如下圖 $N = 4$，寶藏可以埋在四個路口中的任意一個：

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

最後兩圖相同，因為可建立頂點對應（把圖倒過來看），道路便完全對應。因此只有三張不同地圖。

給定一組道路，可能有多少張不同地圖？

*本題前 10 次提交會獲得額外回饋。

輸入格式

從標準輸入讀入。

• 第 1 行：一個整數 $N$。

• 第 2..$N + 1$ 行：兩個以空格分隔的整數 $A$、$B$ $(1 \le A \le N; 1 \le B \le N)$，表示路口 $A$、$B$ 之間有路。

輸出格式

向標準輸出寫入。

• 第 1 行：一個整數，不同藏寶圖數量。

範例

輸入格式 1

4
1 2
2 3
3 1
1 4

輸出格式 1

3

說明

下面畫出道路和路口。

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

任意路口都可埋寶藏，但埋在路口 2、3 得到相同地圖，因此不同藏寶圖總數為 3。

題目作者：Yang Yi，2007