Aurora Princess
Time limit1sMemory limit32 MB
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 people, out of , 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 people and Ttukdae's prophecy, write a program that counts the happy people.
Input
The first line contains the number of people . ()
Each of the next lines contains the mother's number and the father's number of person through person , in that order. A mother's number of means the mother is missing, and a father's number of means the father is missing. Every number is between and .
The next line contains the number of people who die or go to the United States. ()
The next line contains the numbers of those people in increasing order. When is , 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.