E. Балдмэн ба Цэргийнхэн

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

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

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

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

Балдмэн бол мөлхөлтийн мастер юм. Тэрээр өтний нүх үүсгэх онцгой авьяастай ажээ. Огторгуйд 2 цэг өгөгдсөн байхад Балдмэн эдгээр цэгүүдийн хооронд 2 чиглэлд 2-ууланд нь явах боломжтой байх нэгэн өтний нүх үүсгэж чаддаг байв. Харамсалтай нь уг үйлдэл нь Балдмэнд тодорхой хэмжээний хохиролтой бөгөөд тодруулбал түүний үүсгэсэн өтний нүх болгонд түүний толгойноос ихээхэн хэмжээний үс унадаг байжээ.

Маш онцгой чадвартай учраас цэргийнхэн түүнийг анхааралдаа авчээ. Тэрээр нэгэн онцгой даалгаварт томилогдсон байв. Уг даалгавар нь маш чухал учраас тэрээр ямар ч чухал ажилтай байсан уг даалгаврыг эхлээд биелүүлэхээр болжээ.

Цэргийн бааз нь хэд хэдэн газар доорх объектуудаас тогтох бөгөөд эдгээрийн зарим нь хооронд 2 урсгалтай хонгилуудаар холбогдсон байв. Мөн хос объект болгоны хооронд эдгээр хоолойнуудаас тогтох системээр дамжин явж болдог зам заавал оршин байна. Түүнчлэн яг 2 ширхэг объект нь гадаргуугаараа холбогдсон байх ажээ. Аюулгүй байдлын үүднээс харуул өдөр болгон хоолойн системийг шалгах юм: Тэрээр гадаргуугаараа холбогдсон объектуудын аль нэг уруу нь эхэлж орох бөгөөд баазаар алхан явсаар хоолой болгоноор дор хаяж нэг удаа дайран өнгөрч гадаргуугаараа холбогдсон объектуудын аль нэгээр нь гарч ирэх юм. Тэрээр ингэх явцдаа ижилхэн эсвэл ялгаатай объектууд уруу эхэлж орж мөн гарч ирсэн байж болно. Цэргийн удирдлага харуул зарим хоолойнуудаар олон тооны удаа дайран гарч байгааг анзаарсан бөгөөд уг үйл явдлыг оновчтой байдлаар шийдэхээр болжээ. Одоо тэд дараах асуудалтай тулгарсан байв: Харуулыг хоолой болгоноор яг нэг удаа дайрч явсан байхаар хоолойнуудын системд шалгалт хийх боломжтой болгох өтний нүхнүүдийн системийг бүтээх хэрэгтэй болжээ. Мөн үүний зэрэгцээ харуул нь өтний нүх болгоноор хэдэн ч тооны удаа дайран өнгөрсөн байж болох юм.

Балдман ийм учраас хэрэг болсон бөгөөд тэрээр уг өтний нүхийг төлөвлөж бүтээн байгуулах нэгэн ажээ. Түүний хувьд нэгэн хүндрэлтэй зүйл нь цэргийн хатуу нууцлалаас болоод түүнд эдгээр хоолойнуудын зохион байгуулалтыг хэлж болохгүй байв. Үүний оронд тэд түүний өтний нүхнүүдийн систем нь дараах өгөгдсөн нөхцөлүүдийг хангах ямар ч хоолойнуудын зохион байгуулалтын хувьд уг асуудлыг шийдэж байхыг шаарджээ. Гэхдээ Балдмэн дараах зүйлсийг мэдэж байв: тэрээр аль хос объектуудыг холбож чадахаа түүнчлэн эдгээрийг холбоход хэр их хохиролтой(үсний тоо) болохыг мэдэж байлаа. Түүнчлэн маргааш түүнд ямар объектууд нь (яг 2 ширхэг объект байна) гадаргуугаараа холбогдсон болохыг хэлж өгөх юм. Мэдээж хэрэг манай баатар маань цаг заваа дэмий үрэхийг хүсэхгүй байгаа бөгөөд хэсэг хос объектуудын хувьд(тэрээр аль 2 объект нь гадаргуугаараа холбогдсон болохыг маргааш мэдэх бөгөөд цаг алдахгүйн тулд ямар нэгэн хос объектуудыг гадаргуугаараа холбогдсон гэж үзэн хохирлын хэмжээгээ тооцож байгаа юм) уг даалгаврыг хийж дуусгахад шаардагдах хамгийн бага хохирлын хэмжээг тооцоолохыг хүсжээ. Балдмэн-д тусална уу!

Оролт

Оролтын эхний мөрөнд ганц натурал тоо $n$ ($2 ≤ n ≤ 100000$) өгөгдөх ба энэ нь цэргийн бааз дээр байх объектын тоог илэрхийлнэ. 2-дахь мөрөнд Балдмэн-ий хийж чадах өтний нүхний тоог илэрхийлэх $m$ ($1 ≤ m ≤ 200000$) гэсэн ганц тоо өгөгдөнө. Дараагийн $m$ мөрөнд эдгээр өтний нүхнүүдийг дүрсэлнэ: мөр болгонд 3-н бүхэл тоо $a, b, c$ ($1 ≤ a, b ≤ n, 1 ≤ c ≤ 100000$)-ууд өгөгдөх ба эдгээр нь уг өтний нүхээр холбогдох объектуудын дугаарууд болон Балдмэн уг өтний нүхийг хийхийн тулд алдах ёстой үсний тоог илэрхийлнэ.

Дараагийн мөрөнд ганц натурал тоо $q$ ($1 ≤ q ≤ 100000$) өгөгдөх ба энэ нь асуултуудын тоог илэрхийлнэ. Эцэст нь $q$ ширхэг мөрөнд асуултуудын тайлбар өгөгдөх бөгөөд мөр болгонд ялгаатай $a_{i}, b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$, $a_{i} ≠ b_{i}$) гэсэн объектуудын хос дугаарууд өгөгдөнө. Мөн хос объектуудын хооронд нэгээс олон тооны өтний нүх байж болох юм.

Гаралт

Таны программ $q$ ширхэг мөр хэвлэх ёстой бөгөөд асуулт болгоны хувьд нэг мөр хэвлэнэ. $i$-р мөрөнд нэг ширхэг бүхэл тоог хэвлэх бөгөөд энэ нь $i$-р асуултын хариултыг илэрхийлнэ. Хариулт нь дараах байдалтай байна: Хэрэв $a_{i}$ болон $b_{i}$-ууд нь гадаргуугаараа холбогдсон 2 объектууд бол ямар ч хоолойнуудын системийн хувьд(өгөгдсөн нөхцөлийг хангасан систем байна) харуул оновчтой байдлаар шалгалт явуулж болдог байх өтний нүхний системийн хамгийн бага хохирлын(үсний тоо) хэмжээ эсвэл ийм байх өтний нүхний системийг байгуулах боломжгүй байвал "-1" байх юм.

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

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

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