import sys
sys.setrecursionlimit(250000)

# 이 문제는 이전에 학습한 스킬이 얼마나 많이 필요한지를 파악해야 하는 그래프 이론 문제
# T: 해당 인덱스의 스킬을 배우기 위해 우선적으로 배워야 하는 스킬
# A: 배워야 하는 스킬 모음
# 스킬 트리 T의 배열 A에서 모든 스킬을 습득하기 위해 배워야 하는 최소 스킬 수 반환

# 1
# 역순으로 배워야 하는 곳까지 DFS
def solution(T, A):
    N = len(T)
    learned = [False] * N   # 각 스킬을 배웠는지 여부 (방문 처리)
    answer = 0
    for target in A:
        skill = target
        # 해당 스킬 및 필요 선수 스킬을 모두 배웠다면 다음 스킬 검사
        while not learned[skill]:
            answer += 1
            learned[skill] = True
            skill = T[skill]    # 부모 스킬을 배웠는지 check
    return answer

# 2
# 집합 사용
# def solution(T, A):
#     skills = set()
#     for skill in A:
#         while skill not in skills:
#             skills.add(skill)
#             skill = T[skill]
#     return len(skills)

T1 = [0, 0, 1, 1]
A1 = [2]
T2 = [0, 0, 0, 0, 2, 3, 3]
A2 = [2, 5, 6]
T3 = [0, 0, 1, 2]
A3 = [1, 2]
T4 = [0, 3, 0, 0, 5, 0, 5]
A4 = [4, 2, 6, 1, 0]

print(solution(T1, A1)) # 3
print(solution(T2, A2)) # 5
print(solution(T3, A3)) # 3
print(solution(T4, A4)) # 7
