گردش


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

شنگدباو در «اینور آب»‌ زندگی می‌کند و خانم کوچولو برای مسافرت به «اونور آب» رفته است!‌

اینور آب و اونور آب خیلی شبیه به هم‌اند. یعنی به ازای هر شهر در اینور آب یک شهر اونور آب مشابه آن وجود دارد و شهر ii در اینور آب مشابه شهر ii در اونور آب است! بین شهرها در هر دو طرف آب، جاده‌هایی وجود دارد، به طور دقیق تر nn شهر وجود دارد و n1n-1 جاده به طوریکه جاده‌ها در هر دو به گونه‌ای هستند که دقیقاً یک مسیر بین هر دو شهر وجود دارد.

مسافرت خانم کوچولو qq روز طول می‌کشد. در روز ii ام او از شهر uiu_i در اونور آب به شهر viv_i از طریق مسیر یکتای بین آن‌ها می‌رود. در این مسیر تعدادی شهر می‌بیند و از این شهرها عکس می‌گیرد. شنگدباو برای اینکه کم نیاورد در همان روز خودش از شهر aia_i در اینور آب به شهر bib_i از طریق مسیر یکتای بین آنها می‌رود.

بعد از هر روز شنگدباو عکس‌هایی که خانم کوچولو در آن روز گرفته را نگاه می‌کند و اگر شهری در این عکس‌ها مشابه شهری بود که خودش در آن روز دیده است می‌گوید:«مام ازینا داریم!»

سوال اینجاست که در آخر هر روز شنگدباو چند بار جمله‌ی «مام ازینا داریم!» را می‌گوید. با گرفتن nn ،‌ نقشه‌ی اینور آب و اونور آب،‌ به ازای هر روز تعداد دفعات گفتن این جمله‌ها را خروجی دهید.

ورودی🔗

در اولین سطر ابتدا nn و سپس qq آمده است. که nn تعداد شهرهای اینور آب و اونور آب است و qq برابر تعداد روزهای گردش است.

در n1n-1 سطر بعدی دو عدد u,vu,v آمده است که به معنای وجود جاده ای بین دو شهر uu و vv در اینور آب است. پس از آن نیز مشابهاً جاده‌های اونور آب در n1n-1 سطر آمده است.

در qq سطر بعدی چهار عدد آمده است که به ترتیب ai,bi,ui,via_i , b_i , u_i , v_i است.

1n,q300 0001 \le n , q \le 300\ 000 1ai,bi,ui,vin1 \le a_i , b_i , u_i , v_i \le n

خروجی🔗

باید qq سطر خروجی دهید که سطر iiام یک عدد به معنای تعداد دفعاتی است که شنگدباو در روز iiام می‌گوید:«مام ازینا داریم!»

زیر مسئله‌ها🔗

زیرمسئله نمره محدودیت
۱ ۱۰ n,q1 000n , 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
Plain text

خروجی نمونه🔗

0
1
1
2
3
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.