+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بعد از یک کلاس ریاضیات سخت، حنا برای تفریح به همراه بنا به جنگل رفته است. حنا و بنا هر کدام یک درخت (گراف بدون دور و همبند) ریشه‌دار $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 ``` <details class="blue"> <summary> راهنمایی ۱ </summary> یک $dp$ تعریف کنید که در آن $dp_v$ برابر طول بلند‌ترین دنباله است که پایین‌ترین راس ان در درخت اول، $v$ است و این$dp$ را به دست آورید. </details>