E. Хоёр ширхэг үндэстэй мод

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

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

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

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

Танд тус бүр $n$ оройтой чиглэлгүй хоёр мод байна. Мод бүрийн оройнуудыг $1$-c $n$ хүртэл бүхэл тоонуудаар дугаарлая. Мод бүрийн үндэс нь $1$ дугаартай орой байна. Эхний модны ирмэгүүд хөх өнгөөр харин хоёрдугаар модны ирмэгүүд улаан өнгөөр будагдсан. Хялбарчлахын тулд эхний модыг хөх мод, хоёрдугаар модыг улаан мод гэж нэрлэе.

Хэрвээ дараах хоёр нөхцөл биелэж байвал ${p, q}$ ирмэгийн хувьд ${x, y}$ ирмэгийг муу гэж нэрлэе:

  1. ${x, y}$ ирмэгийн өнгө ${p, q}$ ирмэгийн өнгөнөөс ялгаатай.
  2. ${p, q}$ ирмэгтэй ижил өнгөтэй модыг авч үзье. $x$, $y$ оройнуудын яг нэг нь $p$ болон $q$ оройн дэд модуудад хоёуланд нь байх.

Энэ бодлогоны хувьд таны ажил бол доор тодорхойлогдсон үйл явцыг дуурайлгах явдал юм.

  1. Үе бүрт яг нэг өнгийн ирмэгүүд устана.
  2. Эхний үед яг нэг хөх ирмэг устана.
  3. Бид $i$-р үед ${u_{1}, v_{1}}$, ${u_{2}, v_{2}}$, $...$, ${u_{k}, v_{k}}$ ирмэгүүдийг устгана. Харин $i + 1$-р үед бид ${u_{1}, v_{1}}$ ирмэгийн хувьд устаагүй байгаа бүх муу ирмэгүүдийг устгана тэгээд бид ${u_{2}, v_{2}}$ ирмэгийн хувьд устаагүй байгаа бүх муу ирмэгүүдийг устгана тэгээд бид ${u_{k}, v_{k}}$ ирмэгт хүрэх хүртлээ үргэлжлүүлнэ.

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

Оролт

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

Дараагийн мөрөнд $n - 1$ эерэг бүхэл тоон утгууд $a_{2}, a_{3}, ..., a_{n}$ ($1 ≤ a_{i} ≤ n; a_{i} ≠ i$) байх ба эхний модны ирмэгүүдийн тайлбар байна. $a_{i}$ тоо нь эхний модонд $a_{i}$ орой болон $i$ оройг холбосон ирмэг байгааг илэрхийлнэ.

Дараагийн мөрөнд $n - 1$ эерэг бүхэл тоон утгууд $b_{2}, b_{3}, ..., b_{n}$ ($1 ≤ b_{i} ≤ n; b_{i} ≠ i$) байх ба хоёрдугаар модны ирмэгүүдийн тайлбар байна. $b_{i}$ тоо нь хоёрдугаар модонд $b_{i}$ орой болон $i$ оройг холбосон ирмэг байгааг илэрхийлнэ.

Дараагийн мөрөнд бүхэл тоон утга $idx$ ($1 ≤ idx < n$) байх ба эхний үед устгагдсан хөх ирмэгийн индекс байна. Мод бүрийн ирмэгүүд оролтонд өгөгдсөн дарааллаараа $1$-с $n - 1$ хүртэлх тоонуудаар дугаарлагдсан. The next line contains integer $idx$ ($1 ≤ idx < n$) -- the index of the blue edge that was removed on the first stage. Assume that the edges of each tree are numbered with numbers from $1$ to $n - 1$ in the order in which they are given in the input.

Гаралт

Ирмэгүүдийг устгаж байгаа үе бүрийн хувьд үеийн тайлбарыг хэвлэ. Тайлбар бүр яг хоёр мөрөөс тогтох ёстой. Хэрвээ уг үед хөх ирмэгүүд устгагдсан бол эхний мөрөнд $Blue$ гэсэн үг байх ба эсрэг тохиолдолд $Red$ гэсэн үг байна. Хоёр дахь мөрөнд уг үед устгагдсан ирмэгүүдийн индексүүдийг өсөх дарааллаар хэвлэнэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
5
1 1 1 1
4 2 1 1
3
Гаралт
Blue
3
Red
1 3
Blue
1 2
Red
2

Тэмдэглэл

Хялбарчлахын тулд үндэстэй модны бүх ирмэг нэг чиглэл хүлээн авна ингээд бүх ирмэгүүдрүү $1$ оройгоос хүрэх боломжтой. Тэгээд $v$ оройн дэд мод нь үүссэн чиглэлтэй графын $v$ оройгоос хүрэх боломжтой ирмэгүүдийн бүрдэл болно ($v$ орой энэ бүрдэлд багтана).

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