F. Хүчирхэг болон Шидэт Гномууд

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

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

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

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

Вася Хүчирхэг болон Шидэт Гномууд гэх нэгэн алдартай тоглоомыг тоглож байв.

Уг тоглоомд Вася Гномуудын эзэнт улсыг удирдах бөгөөд уг улс хоорондоо 2 чиглэлтэй замуудаар холбогдсон хэд хэдэн цайзуудаас тогтож байв. Эзэнт улсын замын сүлжээ нь онцгой хэлбэртэй байв. Эзэнт улс $a_{1}, a_{2}, ..., a_{m}$ гэсэн үндсэн $m$ ширхэг цайзтай бөгөөд эдгээр нь нийлэн Сайн Маршрутыг үүсгэх юм. Уг маршрут нь $a_{i}, a_{i + 1}$ $(1 ≤ i < m)$ гэсэн цайзуудын хоорондох замууд болон $a_{m}$ болон $a_{1}$-ын хоорондох замаас тогтож байв. Уг Сайн Маршрутын цайзуудын хооронд эдгээрээс өөр ямар ч зам байхгүй байх ажээ.

Түүнчлэн Сайн Маршрут-ын хос цайз $u$ болон $v$ бүрийн хувьд яг нэг ширхэг Чөтгөрийн Богино Маршрут оршин байх бөгөөд энэ нь эхний цайз $(u)$-аас 2-дахь цайз $(v)$ хүртэл явах, $u$ болон $v$ оройнуудыг тооцохгүйгээр Сайн Маршруттай ямар нэгэн ерөнхий оройгүй байх замын маршрут юм. Бид эзэнт улсанд эдгээрээс өөр ямар нэгэн зам болон цайз оршин байхгүй болохыг мэдэж байгаа бөгөөд өөрөөр хэлбэл зам болгон нь мөн цайз болгон нь Сайн Маршрут дээр эсвэл Чөтгөрийн Богино Маршрутууд дээр оршин (цайзууд нь эдгээрийн 2-уулан дээр нь оршиж болно) байх юм. Мөн ямар ч 2 Чөтгөрийн Богино Маршрутууд нь Сайн Маршрут дээрх цайзуудаас өөр ямар ч ерөнхий цайзгүй байна.

7 хоног бүрийн эхэнд эзэнт улсад нэг маш муу Гном гарч ирэх бөгөөд тэрээр эзэнт улсын замуудын аль нэг дээр нь зогсож байх юм. Тэрээр уг замын дагуу явах бөгөөд тааралдсан корован-уудаа дээрэмдэх ажээ. Нэг зам дээр олон тооны маш муу Гномууд гарч ирж болно. Вася өөрийн корован-ууддаа анхаарал тавьдаг учраас заримдаа тэрээр нэг цайзаас өөр нэг цайз хүртэл үхлийн даалгаврыг илгээдэг байв.

Үхлийн даалгавар нь $s$ цайзаас $t$ цайзад очих ёстой гэж үзье. Тэгвэл энэ нь $s$ цайзаас $t$ цайз уруу хөдлөх бөгөөд уг даалгаврын явах маршрутын замууд дээр байрлаж буй бүх маш муу Гномуудыг устгах юм. Вася маш хүчирхэг учраас түүний илгээх үхлийн даалгавар нь өөрийн зам дээр байрлах хэдэн ч тооны Гномуудыг устгаж чадах байв. Гэвч Вася маш сайхан сэтгэлтэй нэгэн учраас тэрээр үргэлж хамгийн цөөхөн тооны Гномуудыг устгах $s$ болон $t$ цайзуудын хоорондох маршрутыг сонгох юм. Хэрэв ийм байх олон тооны маршрутууд оршин байвал Вася тэдгээрийн дундаас хамгийн цөөн тооны зам агуулах маршрутыг сонгох юм. Хэрэв дахин ийм байх олон тооны маршрутууд оршин байвал Вася тэдгээрийн дундаас хэл зүйн хувьд хамгийн багийг нь сонгох ажээ.

Вася-д туслан Хүчирхэг болон Шидэт Гномууд тоглоомын эзэнт улсын амьдралын үзэгдлүүдийг хэрэгжүүлж өгнө үү.

Маршрут гэдэг нь цайзуудын дараалал бөгөөд ингэхдээ уг маршрутад байх зэргэлдээ цайз болгон нь замаар холбогдсон байх юм. Түүнчлэн хэрэв $p < q$ ба $x_{1} = y_{1}, x_{2} = y_{2}, ... , x_{p} = y_{p}$ байх юм уу $x_{1} = y_{1}, x_{2} = y_{2}, ... , x_{r} = y_{r}$ бөгөөд $x_{r + 1} < y_{r + 1}$ байх $r$ $(r < p, r < q)$ тоо оршин байвал $x_{1}, x_{2}, ... , x_{p}$ гэсэн маршрутыг $y_{1}, y_{2}, ... , y_{q}$ гэсэн маршрутаас хэл зүйн хувьд бага байна гэж үзнэ.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ $(3 ≤ m ≤ n ≤ 100000)$ өгөгдөх ба эдгээр нь харгалзан эзэнт улс дахь цайзуудын тоо болон Сайн Маршрут дээрх цайзуудын тоог тус тус илэрхийлнэ.

2-дахь мөрөнд $m$ ширхэг бүхэл тоонууд өгөгдөх ба эдгээр нь Сайн Маршрут дээр орсон дарааллынх нь дагуу аль нэг цайзаас нь эхлэн өгсөн эдгээр цайзуудын дугаарууд (бүх цайзууд нь $1$-ээс $n$ хүртэл дугаарлагдсан байна) байх юм. Сайн Маршрут дахь бүх цайзууд нь ялгаатай байна.

Дараагийн $m$ ширхэг мөрийн мөр болгонд Чөтгөрийн Богино Маршрутуудыг дүрсэлнэ. Мөр болгон нь эхлээд $k_{i}$ $(3 ≤ k_{i} ≤ 100000)$ гэсэн бүхэл тоог агуулах ба энэ нь уг Чөтгөрийн Богино Маршрутад харгалзах цайзуудын тоог илэрхийлнэ(эдгээр цайзуудын 2 нь Сайн Маршрут дээр байрлана). Дараа нь $k_{i}$ ширхэг бүхэл тоонууд өгөгдөх ба эдгээр нь өгөгдсөн Богино Маршрут дээр орсон дарааллынх нь дагуу өгсөн эдгээр цайзуудын дугаарууд байх юм. Нэг Чөтгөрийн Богино Маршрут дээрх бүх цайзууд нь ялгаатай байна. Богино Маршрутын эхний болон сүүлийн цайзууд нь Сайн Маршрут дээр байх бөгөөд бүх Чөтгөрийн Богино Маршрутуудын эхний цайзууд нь Сайн Маршрутыг үүсгэх ба эдгээр цайзууд нь 2-дахь мөрөнд Сайн Маршрутын өгөгдсөн дараалалтай ижил дарааллын дагуу бичигдсэн байна.

Дараагийн мөрөнд бүхэл тоо $q$ $(1 ≤ q ≤ 100000)$ өгөгдөх ба энэ нь эзэнт улсын амьдралын үзэгдлийн тоог илэрхийлнэ. Дараагийн $q$ ширхэг мөрийн мөр болгонд нэг үзэгдлийг дүрсэлнэ. Үзэгдэл болгон нь $c_{j}$ тэмдэгт, $s_{j}$ болон $t_{j}$ гэсэн 2 тоогоор дүрслэгдэнэ. Энд өгөгдөх тэмдэгт болон тоонууд нь хоорондоо зайгаар тусгаарлагдсан байна. Хэрэв $c_{j}$ тэмдэгт нь "+" (нэмэх) байвал энэ нь маш муу Гном (магадгүй эхнийх нь биш) $s_{j}$ болон $t_{j}$ гэсэн цайзуудын хооронд байх зам дээр гарч ирсэн гэсэн үг юм. Хэрэв $c_{j}$ тэмдэгт нь "?" (асуулт) байвал энэ нь Вася $s_{j}$ цайзаас $t_{j}$ цайз хүртэл үхлийн даалгавар илгээсэн гэсэн үг юм. Мөн "+" хэлбэртэй үзэгдэл бүрийн хувьд $s_{j}$ болон $t_{j}$ гэсэн цайзуудын хооронд зам оршин байх юм. Үзэгдлүүд нь цаг хугацааны дарааллаар өгөгдсөн байх бөгөөд хамгийн эхэнд болсон үзэгдлээс эхэлж өгөгдөнө. Түүнчлэн анхандаа замууд дээр ямар ч маш муу Гномууд байхгүй байна.

Бүх мөрүүдэд өгөгдөх бүх тоонууд нь хоорондоо нэг хоосон зайгаар тусгаарлагдсан байна. Мөн бүх өгөгдсөн Чөтгөрийн Богино Маршрутууд болон Сайн Маршрут нь бодлогын нөхцөлд өгөгдсөн хязгаарлалтыг хангаж байх юм.

Гаралт

"?" хэлбэртэй үзэгдэл бүрийн хувьд дан мөрөнд нэг тоог хэвлэх бөгөөд уг тоо нь харгалзах үхлийн даалгаврын туршид устах маш муу Гномуудын тоог илэрхийлнэ. Үзэгдлүүдийн хариултуудыг цаг хугацааны дарааллын дагуу хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
6 3
1 2 3
3 1 4 2
3 2 5 3
3 3 6 1
10
+ 1 2
+ 4 2
+ 1 3
+ 2 3
? 1 2
+ 2 5
? 1 2
? 1 2
+ 1 2
? 1 2
Гаралт
0
1
0
1

Тэмдэглэл

Бодлогын жишээнд эхний 4-н үзэгдлийн дараа зөвхөн 1-р цайзаас 2-р цайз хүртэлх ганц маршрут нь маш муу Гномуудтай замууд агуулаагүй байна: 1 6 3 5 2.

Гном (2, 5) гэсэн зам дээр гарч ирмэгц дараагийн үхлийн даалгавар нь 1 2 гэсэн маршрутын дагуу хөдлөх бөгөөд (1, 2) гэсэн зам дээр зогсож байсан Гномыг устгах юм. Дараагийн үхлийн даалгавар нь ижил маршрутын дагуу явах боловч уг маршрут дээр ямар ч Гном байхгүй байна.

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

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