This page is still under construction.

Parts of this page are still being built. What you see may change.

Aurora Princess

Time limit1sMemory limit32 MB

Summary
Given each person's parents and a list of people who die or leave the country, count how many remain alive with both parents alive in Korea.
Level

Medium5 of 10

Topics
Graph, DFS, Implementation
Solved
No attempts yet

Problem

Aurora and the people around her lived quietly until a stranger nobody could identify showed up. After that, strange incidents kept happening. One by one the people around Aurora dropped dead of a heart attack or were carried off to the United States.

The incidents would not stop, so Aurora asked Ttukdae, a dog that sees the future, for help. After a few treats Ttukdae named the MM people, out of NN, who will be caught up in the incidents.

Ttukdae says he himself will collapse in thirty minutes, and he wants to know how many happy people will be left once every incident is over. A happy person is someone who is alive in Korea and whose mother and father are both alive in Korea as well. A person who is missing does not count as alive in Korea.

Given the family information of the NN people and Ttukdae's prophecy, write a program that counts the happy people.

Input

The first line contains the number of people NN. (2≤N≤5002 \le N \le 500)

Each of the next NN lines contains the mother's number and the father's number of person 11 through person NN, in that order. A mother's number of 00 means the mother is missing, and a father's number of 00 means the father is missing. Every number is between 00 and NN.

The next line contains the number of people MM who die or go to the United States. (0≤M≤N0 \le M \le N)

The next line contains the numbers of those MM people in increasing order. When MM is 00, this line is empty.

The world Aurora lives in is strange enough that a person can be their own mother, so keep that in mind.

Output

Print the number of happy people left after every incident, on the first line.

Examples2

  1. Example 1

    Input
    17
    0 0
    0 0
    0 0
    2 1
    0 0
    2 1
    0 0
    2 1
    2 1
    0 0
    0 0
    0 0
    0 0
    0 0
    14 0
    14 0
    14 0
    11
    1 2 3 4 5 6 7 8 13 14 17
    
    Expected output
    0
    
  2. Example 2

    Input
    6
    0 0
    0 0
    1 2
    1 2
    3 4
    5 5
    0
    
    
    Expected output
    4