Задано два корневых дерева, состоящих из \(n\) вершин каждое. Вершины в деревьях пронумерованы от \(1\) до \(n\), корень дерева — вершина \(1\).
Вы можете выполнять следующую операцию: выбрать дерево и вершину \(v\) (кроме корня дерева) в нем; соединить дочерние узлы \(v\) с родителем \(v\) и удалить \(v\) из дерева.
Давайте скажем, что два дерева равны, если выполняются оба следующих условия:
- множества оставшихся вершин в обоих деревьях одинаковы;
- для каждой вершины \(v\), которая не удалена, ее родитель в первом дереве такой же, как и ее родитель во втором дереве.
Ваша задача — вычислить минимальное количество вышеупомянутых операций, чтобы сделать деревья равными.
Выходные данные
Выведите одно целое число — минимальное количество вышеупомянутых операций, чтобы сделать деревья равными.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 5 5 1
1 4 1 2
|
4
|
|
2
|
2
1
1
|
0
|
|
3
|
10
4 7 10 6 2 9 7 1 1
1 2 10 3 4 6 6 5 5
|
10
|