- محدودیت زمان: ۱۰ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
شنگدباو در «اینور آب» زندگی میکند و خانم کوچولو برای مسافرت به «اونور آب» رفته است!
اینور آب و اونور آب خیلی شبیه به هماند. یعنی به ازای هر شهر در اینور آب یک شهر اونور آب مشابه آن وجود دارد و شهر \(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