E. Схем

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

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

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

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

Өөрсдийн таашаадаг үндсэндээ шинэ үйлдлийн системийн талаар хамгийн сүүлийн үеийн мэдээг сонсох боломтой болмогц “Назни”-ийн “БолгонОС” холбооныхон нэгэн схемийг хөгжүүлэхээр шийджээ. Схемийн дагуу тухайн холбооноос хамгийн түрүүнд мэдээллийг сонссон хүн хоёр дахь хүн хүү, энэ нь гуравдагч хүн рүү залгах зэрэг дарааллаар явах юм. Өөрөөр хэлбэл $i$ индекстэй хүн тус мэдээг сонсоод $f_{i}$ индекстэй хүн рүү залгаж тус мэдээг дамжуулах юм.

Ийнхүү хэсэг хугацаа өнгөрсний дараа “БолгонОС” хобооны гишүүд энэ схем зарим тохиолдолд үр дүнгүй байна гэж үзжээ. Учир нь холбооны зарим хүн тус мэдээллийн талаар огтхон ч сонсоогүй байх тохиолдлууд гарчээ. Ингээд тэд тус схемд нэмэлт оруулахаар шийдэв. Ингээд тэд $(x_{i}, y_{i})$-г схемд нэмэв. Энэ нь $x_{i}$ дахь хүн $y_{i}$ хүн рүү мөн залгах ёстой байв. Хэнээс эхлэхээс үл хамааран схемийн хамгийн сүүлд гишүүн бүр мэдээг сонссон байх шаардлагад нийцүүлэхийн тулд тэдний нэмэх ёстой хамгийн бага зааварчилгааны тоо хэд байх вэ?

Оролт

Энхий мөр нь “БолгонОС”-ын гишүүдийн тоог агуулсан $n$ ($2 ≤ n ≤ 10^{5}$) тоог харуулна. Хоёр дахь мөр нь $n$ зайгаар тусгаарлагдсан $f_{i}$ ($1 ≤ f_{i} ≤ n, i ≠ f_{i}$) тоог агуулах ба энэ нь $i$ индекстэй хүн рүү залгах ёстой гишүүний индексийг харуулна.

Гаралт

Эхний мөрөнд нэмэх ёстой зааварчилгааны хамгийн тоог гарга. Дараа нь мөр тус бүрийн схемд нэмж болох боломжит хувилбаруудын нэгийг харуул.

Хэрэв хэд хэдэн зөв хариу гарвал нэгийг сонго.

Орчуулсан: Энхгэрэл

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

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