Traitor
Time limit1sMemory limit128 MB
Cover as many marked nodes of a forest as possible by assigning each a distinct neighboring watcher with no two marked nodes watching each other.
- Level
Medium7 of 10
- Topics
- Dynamic programming, Tree
- Solved
- No attempts yet
Problem
An intelligence source tells us there is a traitor inside the ACM Security Agency (ASA). ASA has a hierarchical structure: every agent has one manager, and at least one top manager is not managed by anyone. Our source does not know exactly who the traitor is, but he has a list of suspects. So all we know is that the agency has exactly one traitor and that we have this list of suspects. To find the traitor we want to assign one watcher to each suspect, and the assignment has to satisfy three conditions.
- Two suspects cannot watch each other. An assignment in which agent watches agent while watches is forbidden.
- Each suspect must be watched by his manager or by one of his direct employees.
- Nobody can watch more than one suspect.
Under all three conditions it may be impossible to watch every suspect. Write a program that reads the structure of ASA and the list of suspects, then reports the maximum number of suspects for whom the watcher assignment is possible.
The figure below shows the organizational structure of ASA with two top managers and eleven agents, and the suspects are gray. Here an assignment covering 7 of the 8 suspects is possible, drawn with arrows. An arrow from agent to agent means watches . It can be shown that this example has no assignment covering all suspects.

Input
The input contains multiple test cases. The first line of each test case has two integers, the number of agents () and the number of suspected agents (). The agents are numbered from 1 to . The second line has space separated integers, where the th number is the number of the agent who manages agent , and a zero means agent is a top manager. The third line has the numbers of the suspected agents, . The input ends with a line containing 0 0, which should not be processed.
Output
For each test case, print on one line the maximum number of suspects for whom the watcher assignment is possible.