E. Бонсай
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Василий увлекается бонсай — искусством выращивания декоративных деревьев. У него есть два красивых дерева, но эстетическое чутьё Василия подсказывает ему, что эти деревья нужно сделать как можно более похожими.

Рассмотрим задачу формально. Представим каждое дерево в виде графа со специальной корневой вершиной. Вершины каждого дерева пронумерованы, начиная с единицы, и корнем каждого из деревьев является вершина, имеющая номер 1 среди вершин этого дерева. Графы являются связными и не содержат циклов. Ориентируем рёбра деревьев по направлению от корня. Рёбра, исходящие из каждой вершины, упорядочены (слева направо, если смотреть на дерево спереди) по возрастанию номеров вершин, в которые они исходят.

Василий может совершать два типа операций с любым из деревьев:

  • Удалить из дерева любой лист — вершину, из которой не исходит ни одного ребра. Корень дерева удалять ни в коем случае нельзя.
  • Выбрать два соседних ребра, исходящих из одной вершины, и аккуратно связать их верёвочкой. После этого Василий считает, что два данных ребра становятся одним ребром, а концы этих рёбер становятся одной вершиной, из которой исходят все рёбра, ранее исходившие из начал связанных рёбер. Порядок рёбер, исходящих из новой вершины определяется так: сперва все рёбра, исходившие из конца левого связанного ребра, а затем все рёбра, исходившие из конца правого связанного ребра. Относительный порядок рёбер при этом не меняется. Полученные в результате связывания вершины и рёбра считаются обычными вершинами и рёбрами и могут участвовать в дальнейших связываниях и удалениях.

Василий считает, что деревья стали одинаковыми, если можно построить взаимно-однозначные соответствия между рёбрами и между вершинами двух деревьев таким образом, что:

  • Из соответствующих друг другу вершин исходит одинаковое количество рёбер, и все эти рёбра сопоставлены друг другу согласно их порядку.
  • Для соответствующих друг другу рёбер их концы сопоставлены друг другу.

Из этих правил, в частности, следует, что корни деревьев всегда должны быть сопоставлены друг другу.

Разумеется, Василий хочет как можно меньше испортить исходные деревья. Какое минимальное количество операций ему придется совершить с деревьями, чтобы они стали одинаковыми?

Входные данные

В первой строке записано целое число n — количество вершин первого дерева (1 ≤ n ≤ 5000).

Во второй строке записаны целые числа p2, ..., pn (1 ≤ pi < i). Здесь число pi означает номер родителя некорневой вершины i — начала единственного ребра, входящего в i.

В третьей строке записано целое число m — количество вершин второго дерева (1 ≤ m ≤ 5000).

В четвертой строке записаны номера родителей вершин 2, ..., m второго дерева в том же формате, что описано выше.

Выходные данные

Выведите одно число — минимальное количество операций, необходимое, чтобы сделать деревья одинаковыми.

Примеры
Входные данные
3
1 1
3
1 2
Выходные данные
2
Входные данные
7
1 1 2 2 3 3
7
1 1 2 3 2 3
Выходные данные
0
Входные данные
1
 
5
1 2 1 4
Выходные данные
4
Примечание

В первом примере достичь цели можно за две операции, например, так: отрезать лист 3 в первом дереве, и связать рёбра (1, 2) и (1, 3) во втором дереве.

Во втором примере деревья уже одинаковые несмотря на то, что листья пронумерованы по-разному.

В третьем примере потребуется удалить все вершины второго дерева, кроме корня. Обратите внимание, что если в дереве одна вершина, вторая строка его описания является пустой.