Problem E
Monitoring Ski Paths
Fresh powder on a sunny day: it is a great time to ski! Hardcore skiers flock to a large mountain in the Rockies to enjoy these perfect conditions. The only way up the mountain is by helicopter; skiers jump out and ski down the mountain.
This process sounds a bit chaotic, so some regulations are in place. Skiers can only enter or exit the mountain at a set of designated locations called junctions. Once on the mountain, they are only allowed to travel along designated ski paths, each of which starts at one junction and ends at another junction lower on the mountain. Multiple ski paths might start at the same junction, but no two ski paths end at the same junction to avoid collisions between skiers.
Finally, each skier must register a ski plan a day in advance with the helicopter service. The ski plan specifies the junction they fly up to and the junction lower on the mountain where they get picked up. If a skier shows up to the mountain, they must follow their plan; but some skiers get sick and do not show up at all.
Your job is to look through the ski plans and set up monitors at some of the junctions to count how many skiers actually show up. To keep operating costs as low as possible, you should determine the minimum number of junctions that need to be monitored so that each skier passes through at least one monitored junction.
Figure 1 shows the first sample input. The dashed lines
indicate the five different plans that were registered by
skiers. By monitoring junctions
Input
The first line of input has three integers
Then
Then
Output
Output the minimum number of junctions that need to be monitored so each ski plan includes at least one monitored junction.
Sample Input 1 | Sample Output 1 |
---|---|
10 8 5 1 5 5 6 5 4 7 3 3 10 3 9 10 2 10 8 1 6 5 4 7 2 3 9 10 8 |
3 |
Sample Input 2 | Sample Output 2 |
---|---|
6 5 4 1 2 4 6 2 3 4 5 2 4 1 6 2 6 1 3 2 5 |
1 |