Problem I
Branch Manager
You are managing a transportation network of one-way roads between cities. People travel through the transportation network one by one in order all starting from the same city, and each person waits for the person before them to stop moving before starting. The people follow a simple algorithm until they reach their destination: they will look at all the outgoing roads from the current city, and choose the one that leads to the city with the smallest label. A person will stop when they either reach their destination, or reach a city with no outgoing roads. If at any point someone fails to reach their destination, the rest of the people still waiting in line will leave.
Before each person enters the transportation network, you can permanently close down any subset of roads to guarantee they reach their destination. The roads that you choose to close down will not be available for future people.
There are
Input
The first line of input contains two integers
Each of the next
Each of the next
Output
Output a single integer, which is the maximum number of people you can route to the correct destination.
Sample Input 1 | Sample Output 1 |
---|---|
8 5 1 2 4 8 4 6 1 4 2 5 4 7 2 3 5 2 6 4 8 |
5 |
Sample Input 2 | Sample Output 2 |
---|---|
4 4 1 2 1 3 1 4 3 2 3 4 |
1 |