امین برای تعطیلات به پوستون رفته است. یکی از جاذبه‌های گردشگری‌ پوستون میدان‌های بزرگ و زیبای آن هستند. میدان‌های شهر با تعدادی خیابان به یک‌دیگر متصل شده‌اند.

امین برای جابه‌جایی بین میدان‌ها در شهر می‌تواند از اوبر یا اسنپ تاکسی بگیرد! هر کدام از این دو شرکت مجموعه‌ای از خیابان‌های شهر را تحت پوشش قرار داده است، به طوری که با خیابان‌های تحت پوشش هر کدام از شرکت‌ها به تنهایی، می‌توان با یک مسیر یکتا از هر میدانی به هر میدان دیگر رفت. هم‌چنین، هیچ خیابانی وجود ندارد که تحت پوشش هر دو شرکت اوبر و اسنپ باشد.

امین می‌خواهد بین میدان‌های شهر دور دور کند. او عملیات دور دور را به این شکل انجام می‌دهد که از یک میدان دلخواه شروع می‌کند، از هیچ خیابانی بیش از یک بار عبور نمی‌کند و در نهایت به میدان نخست بر می‌گردد. او در هر حرکت یک بار از یکی از دو شرکت تاکسی می‌گیرد و با این کار از یک سر یک خیابان که تحت پوشش آن شرکت است به سر دیگر آن خیابان می‌رود.

به دلیل این که هزینه‌ی استفاده از تاکسی‌های اوبر بسیار زیاد است، امین حداکثر دوبار می‌تواند از آن‌ها استفاده کند، اما به هر تعداد دلخواهی می‌تواند از تاکسی‌های اسنپ استفاده کند. از طرفی تاکسی‌های اوبر به مراتب لوکس‌تر از تاکسی‌های اسنپ هستند و در نتیجه در نظر دارد که حتماً از دو مرتبه‌ای که می‌تواند هزینه‌ی تاکسی‌های اوبر را پرداخت کند استفاده کند. پس یک دور دور از نظر امین به صرفه است اگر و تنها اگر در طول آن دقیقاً دوبار از تاکسی‌های اوبر استفاده شود.

امین دو دور دور را در صورتی متفاوت در نظر می‌گیرد که در یکی از آن‌ها از خیابانی عبور کنیم که در دور دور دیگر از آن عبور نخواهیم کرد. آیا می‌توانید با گرفتن مسیرهای تحت پوشش اوبر و مسیرهای تحت پوشش اسنپ، تعداد دور دورهای مختلف که امین می‌تواند انجام دهد را بشمارید؟

در خط اول ورودی عدد $n$، تعداد میدان‌های پوستون، آمده است.

در $n-1$ خط بعدی، در هر خط دو عدد طبیعی $v_{s,i}$ و $u_{s,i}$ آمده است که نشان‌ می‌دهد خیابان متصل کننده‌ی آن دو میدان تحت پوشش اسنپ است.

در $n-1$ خط بعدی، در هر خط دو عدد طبیعی $v_{u,i}$ و $u_{u,i}$ آمده است که نشان‌ می‌دهد خیابان متصل کننده‌ی آن دو میدان تحت پوشش اوبر است.

در تنها خط خروجی، تعداد ‌دور دورهای به صرفه در پوستون را چاپ کنید.

• زیرمسئله اول (۲۰ نمره): $n \le 100$
• زیرمسئله دوم (۲۲ نمره): $n \le 3000$
• زیرمسئله سوم (۵۸ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $4 \le n \le 10^5$
• $1 \le v_{s,i}, u_{s,i} \le n$
• $1 \le v_{u,i}, u_{u,i} \le n$
• بین هر دو میدان حداکثر یک خیابان وجود دارد.
• با تاکسی‌های تحت پوشش هر شرکت می‌توان از هر میدان به هر میدان دیگر رسید.

• سوال قبل