Задача 2. Вирусы и антивирусы

Входной файл:virus.in   Ограничение времени:2 сек
Выходной файл:virus.out   Ограничение памяти:256 Мб
Максимальный балл:100  

Условие

Антивирусная IT-компания имеет официальную иерархическую структуру управления. В ней есть босс – единственный сотрудник, над которым нет начальника. Каждый из остальных сотрудников подчинён ровно одному сотруднику – своему начальнику. Начальник может иметь нескольких подчинённых и отдавать или передавать приказы любому из них. Приказы могут передаваться от одного сотрудника другому только по цепочке, каждый раз от начальника к его подчинённому.

Сотрудник А главнее сотрудника Б в этой иерархии, если А может отдать или передать приказ сотруднику Б непосредственно, или через цепочку подчинённых. Босс главнее любого сотрудника.

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

Будем называть пару сотрудников А и Б устойчивой, если А главнее Б и в основной, и в тайной иерархических структурах.

Требуется написать программу, определяющую количество устойчивых пар в компании.

Формат входного файла

В первой строке задано число N – количество сотрудников компании. Во второй строке – N целых чисел ai, где ai = 0, если в официальной иерархии сотрудник с номером i является боссом, в противном случае ai равно номеру непосредственного начальника сотрудника номер i. В третьей строке – N целых чисел bi, где bi = 0, если в тайной иерархии сотрудник с номером i является боссом, в противном случае bi равно номеру непосредственного начальника сотрудника номер i. Нумерация сотрудников ведется с единицы в том порядке, в каком они упомянуты во входном файле.

Формат выходного файла

Выходной файл должен содержать единственное число – количество устойчивых пар.

Ограничения

2 ≤ N ≤ 100 000.

Примеры тестов

Входной файл (virus.in) Выходной файл (virus.out)
1
3
0 3 1
0 1 1
2
2
5
2 0 1 3 4
3 1 0 2 4
7

0.026s 0.006s 15