Canmuu và bạn bè có một kho plutonium lớn và đồng ý chôn kho báu mới tại giao lộ sâu trong hoang dã Canada. Chôn kho báu cần bản đồ, nên họ tự tạo.

Mạng có $N$ $(4 \le N \le 100,000)$ giao lộ (số $1..N$) và $N$ đường. Giao lộ đông đúc làm mọi người rối; mỗi giao lộ có ít nhất một và nhiều nhất bốn đường. Bảo trì tốt cho phép nai sừng tấm chạy hai chiều giữa mọi cặp. Canmuu không chôn ở ngã tư vì giao thông giảm bí mật.

Bản đồ chứa mọi đường và giao lộ, nhưng để giấu vị trí chỉ đánh dấu giao lộ có kho báu, dĩ nhiên bằng 'X' đỏ lớn.

Nai sừng tấm cảnh giác Canmuu vẽ bản đồ thử cho các vị trí và thấy hai nơi khác nhau có thể cho bản đồ giống nhau. Tò mò, đàn bắt đầu tìm số bản đồ khác nhau có thể tạo.

Các bản đồ giống nhau nếu có ánh xạ sao cho:

• hai giao lộ mang X tương ứng;

• có thể cho các giao lộ khác tương ứng sao cho

• khi chọn tương ứng giao lộ, các đường nối chúng cũng tương ứng.

Ví dụ dưới có $N = 4$; kho báu có thể ở bất kỳ trong bốn giao lộ.

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

Hai bản đồ cuối giống nhau: cho các đỉnh tương ứng (lật ngược bản đồ), đường cũng khớp hoàn toàn. Vậy chỉ ba bản đồ khác nhau.

Bao nhiêu bản đồ khác nhau cho một tập đường đã cho?

*10 lần nộp đầu có thêm phản hồi.

Dữ liệu vào

Đọc từ dữ liệu vào chuẩn.

• Dòng 1: một số nguyên $N$.

• Các dòng 2..$N + 1$: hai số nguyên $A$, $B$ $(1 \le A \le N; 1 \le B \le N)$ cách nhau bằng dấu cách, đường nối $A$, $B$.

Dữ liệu ra

Ghi ra dữ liệu ra chuẩn.

• Dòng 1: một số nguyên, số bản đồ kho báu khác nhau.

Ví dụ

Dữ liệu vào 1

4
1 2
2 3
3 1
1 4

Dữ liệu ra 1

3

Ghi chú

Hình vẽ đường và giao lộ:

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

Có thể chôn ở mọi giao lộ, nhưng 2 và 3 cho bản đồ giống nhau. Tổng số khác nhau là 3.

Tác giả bài toán: Yang Yi, 2007