B. Мод засах

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

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

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

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

Чиглэлгүй циклгүй холбогдсон графыг мод гэнэ.

$1$-c $n$ хүртэл дугаарлагдсан $n$ оройтой үндэстэй чиглэлгүй модыг авч үзье. Ийм модыг дүрслэх маш олон зам бий. Үүнийг дүрслэх нэг зам нь $p_{i}$ нь $i$ оройн эцэг оройг заах $n$ ширхэг $p_{1}, p_{2}, ..., p_{n}$ бүхэл тоонуудтай массив үүсгэх юм (энд хялбар байх үүднээс үндэс нь өөрийнхөө эцэг байна).

Энэ үндэст модны хувьд $p$ массив нь $[2, 3, 3, 2]$.

Өгөгдсөн $p_{1}, p_{2}, ..., p_{n}$ дарааллаас модыг сэргээх боломжтой:

  1. $p_{r} = r$ байх яг нэг индекс байна. $r$ орой нь модны үндэс байна.
  2. Бусад бүх $n - 1$ орой $i$-н хувьд $i$ болон $p_{i}$ оройнууд ирмэгээр холбогдоно.

Хэрвээ дээрх тодорхойлсон үйл явцын дагуу $p_{1}, p_{2}, ..., p_{n}$ дарааллаас дурын үндэст мод үүсч байвал энэ дарааллыг хүчинтэй гэнэ. Жишээлбэл $n = 3$ тохиолдолд $(1,2,2)$, $(2,3,1)$ ба $(2,1,3)$ дарааллууд нь хүчингүй байна.

Танд хүчинтэй байх албагүй $a_{1}, a_{2}, ..., a_{n}$ дараалал өгөгдсөн. Таны ажил бол хүчинтэй дараалал үүсгэхийн тулд хамгийн цөөн тооны элемент өөрчлөх юм. Өөрчлөлтүүдийн тоог уг тооны өөрчлөлтийн дараах хүчинтэй дарааллын хамт хэвлэ. Хэрвээ уг тооны өөрчлөлтийн дараа хэд хэдэн хүчинтэй дараалал байвал алийг нь ч хэвлэж болно.

Оролт

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

Хоёр дахь мөрөнд $n$ бүхэл тоо $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{i} ≤ n$) байна.

Гаралт

Эхний мөрөнд дарааллыг хүчинтэй болгоход шаардлагатай үйлдлүүдийн хамгийн бага тоог хэвлэ.

Хоёр дахь мөрөнд $(a_{1}, a_{2}, ..., a_{n})$ дарааллын хамгийн цөөн тооны өөрчлөлтийн дараах дурын хүчинтэй дарааллыг хэвлэ.

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

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

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

Тэмдэглэл

Эхний жишээн дээр нэг элементийг өөрчлөхөд л хангалттай. Гаралтын дараалал нь $4$ (учир нь $p_{4} = 4$) орой дээр үндэстэй модыг илэрхийлэх ба та доорх зурагны зүүн хэсгээс харж болно. Бусад зөв шийдлүүдийн нэг нь $2 3 3 2$ дараалал байж болох ба энэ нь $3$ орой дээр үндэстэй модыг дүрслэнэ (доорх зурагны баруун хэсэгт). Доорх зурганд үндсүүдийг улаан өнгөөр тэмдэглэсэн.

Хоёр дахь жишээн дээр өгөгдсөн дараалал нь аль хэдийн хүчинтэй дараалал байна.

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