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