- محدودیت زمان: ۳ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
بعد از یک کلاس ریاضیات سخت، حنا برای تفریح به همراه بنا به جنگل رفته است. حنا و بنا هر کدام یک درخت (گراف بدون دور و همبند) ریشهدار \(n\) راسی انتخاب کردهاند. آنها به یک دنباله از اعداد مانند \(V_1, V_2, ..., V_K\) علاقه دارند اگر هر دو شرط زیر برقرار باشد:
- در درخت حنا، به ازای هر \(1 \leq i < K\) راس \(V_i\) جد راس \(V_{i+1}\) است.
- در درخت بنا، به ازای هر \(1 \leq i < K\) راس \(V_{i+1}\) جد راس \(V_i\) است.
آنها عاشق یک دنباله هستند اگر هر دو شرط زیر برقرار باشد:
- به این دنباله علاقه داشته باشند.
- هیچ دنبالهای با طول بیشتر از این دنباله وجود نداشته باشد که به آن علاقه داشته باشند.
در یک درخت ریشهدار، به راس \(v\) جد راس \(u\) میگوییم اگر یکی از دو شرط زیر برقرار باشد:
- راس \(v\) پدر راس \(u\) باشد.
- راس \(v\) جد پدر راس \(u\) باشد.
طول بزرگترین دنبالهای که حنا و بنا به آن علاقه دارند، و تعداد دنبالههایی که آنها عاشق آن هستند، چقدر است؟
ورودی
در سطر اول ورودی، عدد \(n\) آمدهاست.
در \(n - 1\) سطر بعدی یالهای درخت حنا آمدهاست. در \(i\) امین سطر \(v_i\) و \(u_i\) دو سر یال \(i\) ام در درخت حنا آمدهاست. ریشه درخت حنا راس شماره \(1\) است.
در \(n - 1\) سطر بعدی یالهای درخت بنا آمدهاست. در \(i\) امین سطر \(v_i\) و \(u_i\) دو سر یال \(i\) ام در درخت بنا آمدهاست. ریشه درخت بنا راس شماره \(n\) است.
\[ 1 \leq n \leq 200 \, 000 \] \[ 1 \leq v_i, u_i \leq n \]
خروجی
در تنها سطر خروجی، طول بزرگترین دنبالهای که حنا و بنا به آن علاقه دارند و باقیمانده تعداد دنبالههایی که آنها عاشق آن هستند را بر \(10^9 + 7\) چاپ کنید.
مثال
ورودی نمونه ۱
5
4 2
3 1
5 4
2 1
4 5
1 5
3 4
2 5
خروجی نمونه ۱
2 3