D. Зохион байгуулагчдад тулгарсан асуудлууд

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

2214 оны "Russian Code Cup" тэмцээний финал зочид буудлуудад зохион байгуулагдаж байна. Хоёр зочид буудал нь үндсэн зочид буудал гэж үзье, үндсэн зочид буудлууддаа арга хэмжээгээ зохион байгуулж, үлдсэн зочид буудлууддаа оролцогчидоо байрлуулна. Зочид буудлууд нь $n - 1$ замаар хобогдсон ба та аль ч зочид буудлаас өөр нэгрүү очиж болно.

Зохион байгуулагчид бүх оролцогчид үндсэн зочид буудлууд руу очиход зарцуулах хамгийн бага хугацаа хэд байх бол гэж бодсон. Оролцогч бүр өөрт нь ойролцоох үндсэн зочид буудал руу явдаг ба замаар хобогдсон хоёр зочид буудлын хооронд явхад зарцуулах хугацааг нэг нэгж гэж үзнэ.

Зохион байгуулагчид гол зочид буудлын байршилыг янз янзын сонголтоор авч үзнэ. Сонголт бүр нь хамгийн бага хугацаатайг олход зохион байгуулагчдад тусална.

Оролт

Эхний мөрөнд бүхэл $n$ ($2 ≤ n ≤ 100000$) тоо агуулагдана. Энэ нь зочид буудлуудын тоо юмаа. Дараагийн $n - 1$ мөрөнд хоёр бүхэл тоо агуулагдана. Энэ нь зочид буудлуудын хоорондох замын тоо. Зочид буудлууд нь $1$-ээс $n$ хүртэл дугаарлагдсан байхыг анхаараарай.

Дараагийн мөрөнд бүхэл $m$ ($1 ≤ m ≤ 100000$) тоо байна. Энэ нь сонголтуудын тоо. Дараагийн $m$ мөр бүрд давхардаагүй хоёр бүхэл тоо тус бүр агуулагдана. Энэ нь гол зочид буудлуудын тоо гэж бодно.

Гаралт

Зохион байгуулагчдын хүсэлт тус бүрт нэг бүхэл тоог харгалзуулан хэвлэнэ. Уг тоо нь бүх оролцогчдын үндсэн зочид буудлууд руу хүрхэд зарцуулах хугацаа юмаа.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
3
2 3
3 1
3
2 1
2 3
3 1
Гаралт
1
1
1
Оролт
4
1 4
1 2
2 3
3
1 4
1 3
2 3
Гаралт
2
1
2
Сэтгэгдлүүдийг ачааллаж байна...