F. Аралтай оньсого

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

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

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

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

Холын арлуудын сүлжээ нь $n$ арал агуулах ба тэдгээрийн хооронд хэсэг 2 чиглэлтэй гүүрүүд байдаг ажээ. Одоогийн гүүрийн сүлжээ нь мод хэлбэртэй юм. Өөрөөр хэлбэл, нийт $n - 1$ гүүрүүд нь арлуудыг хос хосоор нь замаар холбох ба ингэснээр ямар ч арлаас ямар ч бусад арал уруу гүүрийн сүлжээг ашиглан хүрэх боломжтой.

Арал бүрийн төвд нь ижилхэн тавцан байх ба бүгд тийм боловч арлуудын нэг нь одоогоор тавцан дээрээ хэврэг, ер бусын будагдсан хөшөө байрлуулсан байх юм. Үлдсэн арлууд нь зөвхөн хоосон тавцантай байна.

Арлын оршин суугчид хөшөөнүүдийг шинэ дарааллаар шинээр байрлуулахыг хүсжээ. Ингэхийн тулд, тэд дараах аргыг давтах юм: эхлээд, тэд хоосон тавцантай аралтай шууд зэргэлдээ байх арал сонгоно. Дараа нь, тэд болгоомжтойгоор зэргэлдээ гүүрэн дээгүүр уг арал уруу хөшөөг зөөх ба хоосон тавцан дээр байрлуулна.

Зөвхөн дээр дүрслэгдсэн аргыг хэрэглэн хүссэн дарааллаараа хөшөөнүүдийг шинээр байрлуулна гэдэг нь ихэнхдээ боломжгүй байдаг. Оршин суугчид үүнийг боломжит хамгийн цөөн тооны үйлдлээр хийж болохоор нэмэлт нэг гүүр барихыг хүсэж байгаа юм. Баригдах гүүрийг олоод хүссэн байрлалд хөшөөнүүдийг байрлуулахад шаардагдах хөшөөний шилжилтийн хамгийн бага тоог олно уу.

Оролт

Эхний мөрөнд арлуудын тоо болох ганц бүхэл тоо $n$ ($2 ≤ n ≤ 200 000$) өгөгдөнө.

2-дахь мөрөнд зайгаар тусгаарлагдсан $n$ ширхэг бүхэл тоо $a_{i}$ ($0 ≤ a_{i} ≤ n - 1$) өгөгдөнө -- хөшөө нь одоогоор $i$-дахь аралд байрлаж байгаа. Хэрэв $a_{i} = 0$ бол, уг арал нь хөшөөгүй байна. Мөн $a_{i}$-ууд нь ялгаатай байна.

3-дахь мөрөнд зайгаар тусгаарлагдсан $n$ ширхэг бүхэл тоо $b_{i}$ ($0 ≤ b_{i} ≤ n - 1$) өгөгдөнө -- $i$-дахь аралд байлгахыг хүссэн хөшөөг илэрхийлнэ. Дахин хэлэхэд $b_{i} = 0$ байвал энэ нь уг арал хөшөөгүй байхыг хүсэж байгаа гэсэн үг юм. Мөн $b_{i}$-ууд нь ялгаатай байна.

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

Гаралт

Бүхэл тоонуудын ганц мөр хэвлэнэ:

Хэрэв оршин байгаа сүлжээнд шинээр байрлуулж болж байвал, $0 t$ гэж хэвлэнэ, энд $t$-ээр шинээр байрлуулахын тулд шаардлагатай шилжилтийн тоог илэрхийлнэ.

Бусад тохиолдолд, $u$, $v$, болон $t$ ($1 ≤ u < v ≤ n$)-г хэвлэнэ -- эдгээр нь шинэ гүүрийн 2 захын цэгүүд болон шинээр байрлуулахын тулд шаардагдах хөшөөний шилжилтийн хамгийн бага тоог илэрхийлнэ

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

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

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

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

Тэмдэглэл

Эхний жишээнд, арлын оршин суугчид $1$ болон $3$-дахь арлуудыг холбосон гүүр барих ба дараах шилжилтүүдийг хийнэ: эхлээд $1$ хөшөөг $1$ арлаас $2$ арал уруу шилжүүлнэ, дараа нь $2$ хөшөөг $3$ арлаас $1$ арал уруу шилжүүлэх ба эцэст нь $1$ хөшөөг $2$ арлаас $3$ арал уруу шилжүүлж нийт $3$-н шилжилт хийх юм.

2-дахь жишээнд, арлын оршин суугчид $1$ хөшөөг $1$ арлаас $2$ арал уруу шилжүүлнэ. Ямар ч шинэ гүүр баригдах хэрэггүй ба үүнийг хийхэд зөвхөн $1$ үйлдэл хийх юм.

3-дахь жишээнд, ямар ч нэмэлт гүүр болон дараагийн шилжилтүүд нь хүссэн байрлалд хүргэж чадахгүй.

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