D. Оптик туршилт

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

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

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

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

Профэссор Пүнсүк Ванду рентген цацраган дээр зарим туршилт хийж байна. $n$ туяаг дараах байлаар тохируулав.

Тэнд эсрэг хoёр талдаа тус бүр яг $n$ нүхтэй тэгш ѳнцѳгт байна. Бүх цацраг нэг талын нүхээр нь ороод нѳгѳѳ талын нүхээр гарна. Орох гарах нүх бүрээр яг нэг цацраг дайрч ѳнгѳрсѳн байна. Нүхнүүд нэг шугаманд байрлана.

http://espresso.codeforces.com/bae0e1ffb03e7f159b8a48ffb47cf3401fd409fc.png

Проффессор Ванду оюутнууддаа туршилтаа үзүүлж байна. Тэр цацраг бүр ѳѳр ямар нэгэн цацрагтай огтлолцсон байх тохиолдлуудыг үзүүллээ. Сониуч оюутан багшаасаа: "Эрхэмээ, зарим бүлэг цацрагийн хувьд цацраг бүр бусадтайгаа огтлолцсон байна. Бид ийм хамгийн том бүлгийн цацрагийн тоог тодорхойлж чадах уу?" гэж асуув.

Профессор Ванду одоо асуудалд орсон бѳгѳѳд таныг туслахыг хүсчээ.

Оролт

Эхний мѳр цацрагуудын тоо $n$ ($1 ≤ n ≤ 10^6$) бүхэл тоог агууна. Хоёрдугаар мѳр $n$ ялгаатай тоог агуулна. $i$-р тоо $x_i$ ($1 ≤ x_i ≤ n$) нь $x_i$-р цацраг $i$-р нүхээр орсныг заана. Үүнтэй адилаар гуравдугаар мѳр $n$ ялгаатай тоог агуулна. $i$-р тоо $y_i$ ($1 ≤ y_i ≤ n$) нь $y_i$-р цацраг $i$-р нүхээр гарсныг заана. Бүх цацраг $1$-ээс $n$ тоогоор дугаарлагдсан байна.

Гаралт

Гаралт бүгд биентэйгээ огтлолцсон байх хамгийн том бүлгийн цацрагуудын тоо болох ганц бүхэл тоог агуулна.

Орчуулсан: Sugardorj

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

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

Тэмдэглэл

For the first test case, the figure is shown above. The output of the first test case is 3, since the rays number 1, 4 and 3 are the ones which are intersected by each other one i.e. 1 is intersected by 4 and 3, 3 is intersected by 4 and 1, and 4 is intersected by 1 and 3. Hence every ray in this group is intersected by each other one. There does not exist any group containing more than 3 rays satisfying the above-mentioned constraint.

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