في عشب حديقة KOI جحر يعيش فيه عدد من النمل. يتكون الجحر من $N$ غرفة و$N-1$ ممرًا تربط غرفًا مختلفة مباشرة، ويمكن الانتقال بين أي غرفتين مختلفتين عبر الممرات. أي إن الجحر شجرة ذات $N$ رأسًا. تُرقّم الغرف من $1$ إلى $N$.

يمكن أن تسكن كل غرفة نملة واحدة على الأكثر. إذا كانت غرفتا نملتين متصلتين مباشرة بممر، فإنهما تشعران بالانزعاج من بعضهما. لذا حاليًا، تسكن نملة في غرفة واحدة على الأكثر من الغرفتين اللتين يربطهما كل ممر.

النمل ذكي، لذا يسكن الجحر حاليًا أكبر عدد ممكن من النمل مع تحقق هذا الشرط. بعبارة أخرى، إذا دخلت نملة أخرى، فلن يحقق أي توزيع للنمل على الغرف الشرط المذكور.

في يوم صيفي مشمس، يذهب كثير من الناس للتنزه في حديقة KOI. وأثناء استمتاعهم بالعشب، تتفتت تربة الجحر فيظهر ممر جديد واحد بالضبط يربط غرفتين مختلفتين. قد تكون الغرفتان متصلتين مباشرة أصلًا. أي إنه لأي عددين صحيحين $1 \le i < j \le N$، قد يظهر ممر جديد بين الغرفتين $i$ و$j$، سواء وُجد ممر بينهما سابقًا أم لا.

قد يربط الممر الجديد مباشرة غرفتي نملتين، فيصبح هذا الزوج منزعجًا. لذلك قد يضطر النمل المقيم حاليًا إلى إعادة توزيع نفسه لتحقيق الشرط. بحسب اختيار $(i,j)$، قد يكون ذلك ممكنًا، لكن في بعض الحالات لا يحقق أي توزيع جديد لجميع النمل الحالي الشرط. عندئذ قد يلزم طرد بعض المقيمين.

لعددين صحيحين $1 \le i < j \le N$، نسمي $(i,j)$ زوجًا مسالمًا إذا أمكن، بعد إضافة ممر بين الغرفتين $i$ و$j$، تحقيق الشرط بإعادة توزيع مناسبة لجميع النمل دون طرد أي نملة. عند إعطائك بنية الجحر، احسب عدد الأزواج المسالمة.

القيود

• $2 \le N \le 250\,000$
• $u \ne v$, $1 \le u,v \le N$
• الجحر المعطى له بنية شجرة.

المهام الفرعية

1. (8 نقطة) $N \le 16$.
2. (6 نقطة) $N \le 80$.
3. (18 نقطة) $N \le 400$.
4. (18 نقطة) $N \le 2000$.
5. (6 نقطة) $N \le 10000$.
6. (8 نقطة) $N \le 50000$.
7. (36 نقطة) لا توجد قيود إضافية.

الإدخال

يحتوي السطر الأول على $N$.

يحتوي كل من الأسطر $N-1$ التالية على رقمي الغرفتين $u$ و$v$ اللتين يربطهما ممر.

الإخراج

اطبع عدد الأزواج المسالمة في السطر الأول.

أمثلة

الإدخال 1

4
1 2
1 3
1 4

الإخراج 1

3

ملاحظة

في البداية يمكن أن يسكن الجحر 3 نملات على الأكثر، والتوزيع الوحيد بهذا العدد هو $\{2,3,4\}$. إضافة ممر بين غرفتين متصلتين مباشرة أصلًا لا تتطلب إعادة توزيع. توجد 3 حالات كهذه. في جميع الحالات الأخرى، لا يوجد توزيع يستوعب 3 نملات بعد إضافة الممر.

الإدخال 2

6
1 2
2 3
3 4
4 5
5 6

الإخراج 2

15

ملاحظة

في البداية يمكن أن يسكن الجحر 3 نملات على الأكثر، ومن التوزيعات الممكنة $\{1,3,6\}$. أيًا كان الممر المضاف، يوجد توزيع يستوعب 3 نملات.

الإدخال 3

7
1 2
1 3
2 4
2 5
3 6
3 7

الإخراج 3

11