John's Party

John is throwing an at-home party and he wants to invite his friends. John’s friends are very shy so they will only come if their best friend comes to the party. The best friend of that person will come to the party if his best friend comes to the party considering that his best friend is different. In this case a person can have only one best friend.

A person can also have no best friend. In this case his best friend will be himself. John wants to know the total number of people attending the party so that he can buy things needed ahead of time. Total number of people will be limited to the people studying in John's college.

If A considers B as his best friend and B considers C as his best friend. So, in order to invite A John has to invite B and C along with A. If A considers B as his best friend, it is not necessary that B also considers A as his best friend.

Input Format

• The first line of the input contains a single integer N, the total number of people in John's college.
• The next N lines contains two space-separated integers u and v where u considers v as his best friend.
• The next line contains integer M, number of friends that John wants to invite.
• The next line contains M space-separated integers denoting friends John wants to invite.

Constraints

• 1 <= N <= 10^5
• 1 <= M <= 10^5
• 1 <= u, v <= N

Output Format

For each test case, print a single line containing one integer i.e. the total number of people John has to invite to the party.

Sample Input 0

3
1 2 
2 3
3 2
2
2 3

Sample Output 0

2

solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> bestFriend(N + 1);
    for (int i = 1; i <= N; ++i) {
        int u, v;
        cin >> u >> v;
        bestFriend[u] = v;
    }

    int M;
    cin >> M;
    vector<int> invitees(M);
    for (int i = 0; i < M; ++i) cin >> invitees[i];

    vector<bool> invited(N + 1, false);

    for (int person : invitees) {
        vector<int> stack;
        stack.push_back(person);

        while (!stack.empty()) {
            int current = stack.back();
            stack.pop_back();

            if (!invited[current]) {
                invited[current] = true;
                int bf = bestFriend[current];
                if (bf != current && !invited[bf]) {
                    stack.push_back(bf);
                }
            }
        }
    }

    int count = 0;
    for (int i = 1; i <= N; ++i) {
        if (invited[i]) count++;
    }

    cout << count << "\n";
    return 0;
}