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

حل سؤال در بانک سؤالات