- محدودیت زمان: ۱۰ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
شنگدباو در «اینور آب» زندگی می‌کند و خانم کوچولو برای مسافرت به «اونور آب» رفته است!
اینور آب و اونور آب خیلی شبیه به هم‌اند. یعنی به ازای هر شهر در اینور آب یک شهر اونور آب مشابه آن وجود دارد و شهر $i$ در اینور آب مشابه شهر $i$ در اونور آب است! بین شهرها در هر دو طرف آب، جاده‌هایی وجود دارد، به طور دقیق تر $n$ شهر وجود دارد و $n-1$ جاده به طوریکه جاده‌ها در هر دو به گونه‌ای هستند که دقیقاً یک مسیر بین هر دو شهر وجود دارد.
مسافرت خانم کوچولو $q$ روز طول می‌کشد. در روز $i$ ام او از شهر $u_i$ در اونور آب به شهر $v_i$ از طریق مسیر یکتای بین آنها می‌رود. در این مسیر تعدادی شهر می‌بیند و از این شهرها عکس می‌گیرد. شنگدباو برای اینکه کم نیاورد در همان روز خودش از شهر $a_i$ در اینور آب به شهر $b_i$ از طریق مسیر یکتای بین آنها می‌رود.
بعد از هر روز شنگدباو عکس‌هایی که خانم کوچولو در آن روز گرفته را نگاه می‌کند و اگر شهری در این عکس‌ها مشابه شهری بود که خودش در آن روز دیده است می‌گوید:«مام ازینا داریم!»
سوال اینجاست که در آخر هر روز شنگدباو چند بار جمله‌ی «مام ازینا داریم!» را می‌گوید. با گرفتن $n$ ، نقشه‌ی اینور آب و اونور آب، به ازای هر روز تعداد دفعات گفتن این جمله‌ها را خروجی دهید.
ورودی
در اولین سطر ابتدا $n$ و سپس $q$ آمده است. که $n$ تعداد شهرهای اینور آب و اونور آب است و $q$ برابر تعداد روزهای گردش است.
در $n-1$ سطر بعدی دو عدد $u,v$ آمده است که به معنای وجود جاده ای بین دو شهر $u$ و $v$ در اینور آب است. پس از آن نیز مشابهاً جاده‌های اونور آب در $n-1$ سطر آمده است.
در $q$ سطر بعدی چهار عدد آمده است که به ترتیب $a_i , b_i , u_i , v_i$ است.
$$1 \le n , q \le 300\ 000$$ $$1 \le a_i , b_i , u_i , v_i \le n$$
خروجی
باید $q$ سطر خروجی دهید که سطر $i$ام یک عدد به معنای تعداد دفعاتی است که شنگدباو در روز $i$ام می‌گوید:«مام ازینا داریم!»
زیر مسئله‌ها
| زیرمسئله | نمره | محدودیت |
|---|---|---|
| ۱ | ۱۰ | $n , q \le 1\ 000$ |
| ۲ | ۴۰ | تضمین می‌شود به هر شهری در اینور آب و اونور آب حداکثر دو تا جاده متصل است. |
| ۳ | ۵۰ | بدون محدودیت اضافی |
مثال
ورودی نمونه
5 5
3 4
5 1
4 1
3 2
1 2
4 1
5 1
2 3
4 1 5 5
3 4 2 4
4 3 1 3
1 5 5 3
5 2 1 3
خروجی نمونه
0
1
1
2
3
ارسال پاسخ برای این سؤال