E. Хавтгайн граф

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

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

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

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

Граф нь түүний ирмэгүүд зөвхөн түүний оройнууд дээр огтлолцож байхаар зурж болдог бол $хавтгайн$ граф гэдэг.

Чиглэлгүй графын хувьд тухайн оройг хасахад графын холбоост хэсгүүдийн тоог өсдөг бол энэ оройг $нугасан цэг$ гэнэ.

Чиглэлгүй рафаас тухайн ирмэгийг хасахад графын холбоост хэсгүүдийн тоо өсдөг бол энэ ирмэгийг $гүүр$ гэнэ.

Танд $1$-ээс $n$ хүртэл дугаарлагдсан $n$ оройтой хавтгайн граф өгөгдсөн. Энэ графд гүүр, нугасан цэг, гогцоо, давхар ирмэг байхгүй. Мөн $q$ ширхэг хүсэлт өгөгдсөн. Хүсэлт бүр нь графийн цикл байна. Уг хүсэлтийн хариу нь уг цикл (хэрвээ энэ цифлийг хавтгайд зурсан гэвэл) доторх болон уг граф дээр байрлах цэгүүдийн тоо юм. Граф болон хүсэлтүүд өгөгдсөнөөр хүсэлт бүрт хариулах програм бичнэ үү.

Оролт

Эхний мөрөнд графийн орой болон ирмэгийн тоог илэрхийлэх зайгаар тусгаарлагдсан хоёр бүхэл тоо $n$ and $m$ ($3 ≤ n, m ≤ 10^{5}$) байрлана. Дараагийн $m$ мөр графийн ирмэгүүдийг агуулна: $i$-р мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоо $u_{i}$, $v_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$) байрлана, энэ нь $i$-р ирмэгийг холбох хоёр оройн дугаар байна. Дараагийн $n$ мөр хавтгайн графийн цэгүүдийн байрлал болох коордийнатыг агуулна: $i$-р мөр зайгаар тусгаарлагдсан $x_{i}$, $y_{i}$ ($|x_{i}|, |y_{i}| ≤ 10^{9})$ тоонуудыг агуулна, энэ нь $i$-р оройн координат юм.

Дараагийн мөр хүсэлтийн тоо болох $q$ ($1 ≤ q ≤ 10^{5}$) бүхэл тоог агуулна. Үүний араас $q$ мөр хүсэлтүүдийг илэрхийлнэ: $i$-р мөрөнд $k_{i}$, $a_{1}$, $a_{2}$, ..., $a_{k_{i}}$ ($1 ≤ a_{j} ≤ n; k_{i} > 2$) тоонууд байрлана, энд $k_{i}$ $i$-р хүсэлтийн циклийн урт, $a_{j}$ нь цикл дэх оройнуудын дугаар. Эдгээр цэгүүд нь энэ дарааллаараа цагийн зүүний дагуу юмуу эсрэг чиглэлээр тойрно. Энэ цикл нь орой бүрээр нэгээс илүү дайрч өнгөрөхгүй энгийн цикл байна. Циклүүдийн нийт урт $10^{5}$ тооноос хэтрэхгүй.

Уг граф гүүр, нугасан цэг, гогцоо, давхар ирмэггүйгээр өгөгднө. Мөн графийн ирмэгүүд цэгүүд дээр л огтлолцно.

Гаралт

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

Орчуулсан: Sugardorj

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

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