D. Вант улс ба улсын хотууд

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

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

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

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

К-ийн вант улс хааны гүнжийн хуримд бэлдэж байна. Хаан хамаатан садангийнхаа өмнө нүүр улайхгүйн тулд эхлээд вант улсдаа сайжруулалт хийх ёстой. Хаан охиныхоо хуримыг хүлээж тэсэхгүй байгаа учир сайжруулалт аль болох хурдан дуусах ёстой.

Вант улс $n$ хоттой. Хотууд $n - 1$ хос чиглэлтэй замуудаар дурын хотоос дурын өөр хотруу очиж болохоор холбогдсон. Хаан маш их хэмнэлттэй учир дурын хоёр хотын хооронд нэг л зам байна.

Сайжруулалтын цэг юу вэ? Улсын түлхүүр яамдууд ялгаатай хотуудруу хуваарилагдах ёстой (бид ийм хотуудыг чухал хот гэнэ). Гэхдээ зэрлэг хүмүүс дайрах магадлал өндөр учир үүнийг болгоомжтой хийх ёстой. Хаанд хэд хэдэн төлөвлөгдсөн төлөвлөгөөнүүд байгаа ба төлөвлөгөө бүр чухал хотуудын бүрдлээр тодорхойлогдох ба одоо тэр аль нь хамгийн сайн төлөвлөгөө вэ гэж бодож байна.

Зэрлэг хүмүүс чухал биш хотуудын заримыг эзэлж чадна (чухал хотууд нь хангалттай хамгаалалттай байх болно). Үүний дараа эзлэгдсэн хотууд нэвтэршгүй болно. Мөн төлөвлөгөөний сонирхолтой нэг хэсэг бол зэрлэг хүмүүс бүх чухал хотоос өөр дурын чухал хотруу очих боломжгүй байхаар бүх чухал хотыг тусгаарлахын тулд эзлэх шаардлагатай хотуудын тоог хамгийн бага байлгах юм.

Хаанд төлөвлөгөө бүрийнхээ хувьд энэ үзүүлэлтийг тооцоолоход туслана уу.

Оролт

Оролтын эхний мөрөнд бүхэл тоон утга $n$ ($1 ≤ n ≤ 100 000$) байх буюу вант улсын хотуудын тоо байна.

Дараагийн $n - 1$ мөр бүрт хоёр ялгаатай бүхэл тоо $u_{i}$, $v_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$) байх ба $i$-р замаар холбогдсон хотуудын дугаарууд байна. Та замуудаар дамжин дурын хотоос дурын өөр хотруу очих боломжтой байна.

Дараагийн мөрөнд бүхэл тоон утга $q$ ($1 ≤ q ≤ 100 000$) байх ба хааны төлөвлөгөөнүүдийн тоо юм.

Дараагийн $q$ мөр бүрт: эхлээд $k_{i}$ тоо буюу хааны төлөвлөгөөн дахь чухал хотуудын тоо, ($1 ≤ k_{i} ≤ n$) тэгээд дараа нь 1-с $n$ хоорондох ялгаатай зайгаар тусгаарлагдсан яг $k_{i}$ тоо байх буюу уг төлөвлөгөөн дахь чухал хотуудын дугаар юм.

Бүх $k_{i}$-уудын нийлбэр $100 000$-с хэтрэхгүй.

Гаралт

Төлөвлөгөө бүрийн хувьд зэрлэг хүмүүс эзлэх шаардлагатай хотуудын хамгийн бага тоо болох бүхэл тоог хэвлэ эсвэл зэрлэг хүмүүсийн чухал хотуудыг тусгаарлах бүх оролдлогууд үр ашиггүй байх бол $ - 1$-г хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
4
1 3
2 3
4 3
4
2 1 2
3 2 3 4
3 1 2 4
4 1 2 3 4
Гаралт
1
-1
1
-1
Оролт
7
1 2
2 3
3 4
1 5
5 6
5 7
1
4 2 4 6 7
Гаралт
2

Тэмдэглэл

Эхний жишээн дээр хааны эхний болон гуравдугаар төлөвлөгөөнд зэрлэг хүмүүс $3$ дугаартай хотыг л эзлэхэд хангалттай. Хоёрдугаар болон дөрөвдүгээр төлөвлөгөөнд тэдний бүх оролдлого үр ашиггүй байна.

Хоёр дахь жишээн дээр эзлэх хотууд нь $3$ ба $5$ байна.

Сэтгэгдлүүдийг ачааллаж байна...