| Manthan 2011 |
|---|
| Закончено |
Профессор Фансак Ванду провел некоторые оптические эксперименты на лучах света. Установка для проведения эксперимента для n лучей выглядит следующим образом.
Есть прямоугольная коробка, в которой ровно n отверстий на противоположных гранях. Все лучи проникают сквозь отверстия с первой стороны и выходят из отверстий с другой стороны коробки. Ровно один луч может проникать через каждое отверстие или выходить из него. Отверстия на каждой грани лежат на одной прямой, а сами грани параллельны и симметричны друг другу.
Профессор Ванду продемонстрировал ученикам свои эксперименты. Он показал, что есть случаи, когда все лучи пересекаются всеми остальными лучами. Один любопытный ученик спросил: "Профессор, есть некоторые группы лучей, в которых все лучи в данной группе пересекают все остальные лучи в данной группе. Можем ли мы определить количество лучей в наибольшей из таких групп?".
И вот профессор Ванду в затруднении. Зная ваш интеллект, он просит вас помочь ему.
Первая строка содержит n (1 ≤ n ≤ 106), количество лучей. Вторая строка содержит n различных целых чисел: i-ое целое число xi (1 ≤ xi ≤ n) показывает, что xi-ый луч проходит через i-ое отверстие. Подобным образом, третья строка содержит n различных целых чисел: i-ое целое число yi (1 ≤ yi ≤ n) показывает, что yi-ый луч исходит из i-го отверстия. Все лучи пронумерованы от 1 до n.
Выходные данный содержат единственное целое число — количество лучей в наибольшей группе лучей, в которой все пересекают друг друга.
5
1 4 5 2 3
3 4 2 1 5
3
3
3 1 2
2 3 1
2
Рисунок для первого теста показан выше. В первом тесте следует вывести 3, так как лучи номер 1, 4 и 3 пересекаются друг с другом, то есть 1 пересекает 4 и 3, 3 пересекает 4 и 1, а 4 пересекает 1 и 3. Таким образом, каждый луч в данной группе пересекается другим лучом. Не существует группы, содержащей более трёх лучей, которая удовлетворяла бы вышеприведенному ограничению.
