حصل 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