D. Замын зураг

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

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

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

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

$n$ бол Берландын хотууд юм. Хот тус бүр $1$-ээс $n$ хүртэл бүхэл тоогоор индекслэгдсэн ба нийслэл нь $r_{1}$ индекстэй. Берландын бүх зам нь хоёр урсгалтай. Авто замын систем нь нийслэлээс хот болгон луу яг нэг замаар л явдаг, өөрөөр хэлбэл замын зураг нь мод шиг харагддаг. Берландын сударт замын зураг нь дараах аргаар хадгалагдаж байдаг: Нийслэлээс ялгаатай дурын $i$ хотын хувьд $p_{i}$ -- ($i$ нь нийслэлээс дайрж өнгөрсөн хотын индекс) гэсэн дугаартай хадгалагдаж байгаа.

Нэг удаа Берландын хаан XXXIV Берл хотын нийслэлийг $r_{1}$-ээс $r_{2}$ луу нүүлгэхээр шийджээ. Мэдээж хэрэг үүний дараа Берландын судар дахь замын зураг буруу болно. Дээр дурьдсан аргаар авто замын шинэ зургийг гаргахад хаанд туслана уу.

Оролт

Эхний мөр нь зайгаар тусгаарлагдсан гурван бүхэл тоо $n$, $r_{1}$, $r_{2}$ ($2$ ≤ $n$ ≤ $5*10^{4}$, $1$ ≤ $r_{1}$ ≠ $r_{2}$ ≤ $n$) байна. $n$ бол Берландын хотууд, $r_{1}$ хуучин нийслэл, $r_{2}$ нь шинэ нийслэл юм.

Дараагийн мөрөнд $n - 1$ ширхэг бүхэл тоо (авто замын хуучин зураг) агуулагдана. Энд өгөгдсөн $p_{i}$- ($i$ нь нийслэлээс дайрж өнгөрсөн хотын индекс) тоонууд нь $r_{1}$ - ээс гадагш хот болгон руу гарсан. Бүх хотуудыг индексийн өсөх дарааллаар тэмдэглэсэн.

Гаралт

$n-1$ ширхэг тоо гарна.Авто замын шинэ зургийг хуучинтайгаа ижил загвараар гаргана.

Орчуулсан: Даариймаа

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

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