E. Язгууртан баатрын зам

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

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

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

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

Берландад феодал бүр $1$ шилтгээнтэй ба шилтгээн бүр яг $1$ феодалд харьяалагддаг. Хаанаас бусад феодлууд өөр нэг феодалд захирагдана. Харин $1$ феодал нь хэдэн ч феодал захирч болно. Зарим шилтгээнүүд $2$ чиглэлт замаар холбогдсон. Нэг шилтгээний эзэмшигч нь нөгөө шилтгээний эзэмшигчийг шууд захирдаг бол энэ $2$ шилтгээнийг холбодог зам байна.

Жил бүр доорх $2$ үйл явдлын аль нэг нь Берландад болдог.

  1. Харь улсууд $c$ шилтгээн рүү довтолно. Сонирхолтой нь Берландын түүхэнд харь улсууд $1$ шилтгээн рүү $2$ удаа довтолж байсан тохиолдол байдаггүй.
  2. Язгууртан баатар $a$ шилтгээнээс $b$ шилтгээн рүү очих аялал хийнэ (Замдаа тэр нэг таарсан шилтгээнтэйгээ дахиж таарахгүй).

$2$ дахь үйл явдлыг илүү дэлгэрэнгүй авч үзье. $a$-аас $b$ рүү очих аялал богино биш, тиймээс тэр замдаа амрахаар ямар нэгэн шилтгээнээр дайрч болох юм. Гэхдээ тэр бүх шилтгээнээр дайрахгүй, учир нь түүний хувьд дайсны муухай үнэр арилаагүй байгаа шилтгээнд орно гэдэг байж боломгүй зүйл юм. $y$ оноос хойш шилтгээн рүү довтолсон бол шилтгээнийг бохирдсон гэнэ. Тиймээс баатар $y+1$ оноос энэ жил хүртэл дайсан довтлоогүй, өөртэй нь тааралдсан $k$-р шилтгээнийг сонгоно. Шилтгээн нь $a$-аас эхлэн (энд, $a$ ба $b$ шилтгээнийг оролцуулахгүй) дугаарлагдана.

Баатар аль шилтгээн рүү хэдэн онд довтолсон гэдгийг мэдэхгүй тул шүүхийн шинжээч танаас тусламж хүсч байна. Танд Берландын түүхэнд болсон үйл явдлуудын дараалал өгөгдөнө. Баатар бүрт аль хотоор дайрах вэ гэдгийг хэлж өгөөрэй. Эсвэл $a$ хотоос $b$ хот хүрэх замд түүний шаардлагад нийцэх хот хамгийн багадаа $k$ байвал баатар амрахгүй тул түүнд муу мэдээ дуулгах хэрэгтэй.

Оролт

Оролтын эхний мөр нь феодалын тоог харуулах $n$ $(2≤n≤10^{5})$ бүхэл тоог агуулна.

Дараагийн мөр нь хоосон зайгаар тусгаарлагдсан $n$ тооны бүхэл тоог агуулна. $i$-р бүхэл тоо нь $i$-р феодалын тоог агуулах ба хэрэв $i$-р феодал нь хаан бол $0$-ийг агуулна.

Гурав дахь мөр нь хүсэлтийн тоог харуулах $m$ $(1≤m≤10^{5})$ бүхэл тоог агуулна.

Дараагийн $m$ мөрүүд нь үйл явдлуудыг тайлбарлана. $i$-р мөр нь ($1$-ээс эхлэн дугаарласан) $i$-р онд болсон үйл явдлын тайлбарыг агуулна. Үйл явдал бүр нь төрөл $t_{i}$ $(1≤t_{i}≤2)$-ээр тодорхойлогдоно. Эхний төрлийн үйл явдлын тайлбар нь хоосон зайгаар тусгаарлагдсан $t_{i}$ $c_{i}$ $(t_{i}=1; 1≤c_{i}≤n)$ 2 бүхэл тоогоор илэрхийлэгдэнэ. Энд, $c_{i}$ нь $i$ дахь жилд харийнхны довтолсон шилтгээний тоо байна. $2$-р төрлийн үйл явдлын тайлбар нь хоосон зайгаар тусгаарлагдсан $t_{i}$ $a_{i}$ $b_{i}$ $k_{i}$ $y_{i}$ $(t_{i}=2; 1≤a_{i}, b_{i}, k_{i}≤n; a_{i}≠b_{i}; 0≤y_{i}

Феодалуудыг $1-n$ хүртэл дугаарлагдсан гэж үзээрэй. Феодалуудын дунд ганц л хаан байна. $1$-р төрлийн үйл явдалд бүх $c_{i}$ ялгаатай байна.

Гаралт

2 дахь төрлийн үйл явдал бүрд баатрын амарч болох шилтгээний тоо, эсвэл $a_{i}$-аас $b_{i}$ хүрэх зайг амралтгүйгээр туулах бол $-1$ бүхэл тоог хэвлээрэй. Хариултуудыг хоосон зайгаар тусгаарлана уу.

Оролтод өгсөн $2$-р төрлийн үйл явдлуудын дарааллаар хэвлээрэй.

Орчуулсан: Солонго

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

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

Тэмдэглэл

Эхний жишээнд, $1$-р шилтгээнээс $3$-р шилтгээн орох замд зөвхөн $2$ дугаартай шилтгээн байна. Баатар анх удаагаа $1-3$ хүрэх замаар явахад $2$ нь дайсны довтолгоонд өртөөгүй тул баатар тэндээ байж болно. $2$ дахь жилдээ $2$ дугаартай шилтгээн бохирдоно. Тиймээс баатар дараагийн $2$ жил байрлах газаргүй болно ($1$-ээс $2$ дахь жилд бохирлогдоогүй шилтгээн олно гэдэг түүнд их чухал). $5$ дахь жилдээ $2$ дугаартай шилтгээнийг бохир гэж баатар үзэхгүй тул тэр ахин тэндээ үлдэж амарч болно.

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