HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


50683 - Parking Buses

Guest
• Review clarifications (1)

Section problems

• 50526 - Gold Market
• 50488 - Connecting Wires
• 50681 - Center of a Series
• 50561 - Lucky tickets
• 50598 - Minimum Sum
• 50601 - Increasing sequence
• 50613 - Zapakovka
• 50680 - Triangle
• 50683 - Parking Buses
• 50685 - Guest Room Usage
• 50544 - Stock market
• 50545 - Diet

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 3090/9045/8000/4000 ms. Memory limit 15720/79180/65000/65000 Kb.
Question by Osman Ay, It has been first asked in IS 2012 March.

Parking Buses

Shqip

Tirana City has N buses, conveniently numbered from 1 to N, for public transportation. The buses are parked in a parking area at the end of everyday. The buses are parked side by side. They can be parked in any order but there are some restrictions that should be taken into the consideration. The restrictions are about the priority between two certain buses. Some buses should be parked before some other buses due to the schedule of the next day.

Question

Make a program that gives the number of restrictions that are not satisfied with the given order of buses.

Input Specifications

Input has several lines. The first line contains two integers: N and M, where N denotes the number of buses (1 < N ≤ 10000) and M (0 ≤ M ≤ 501000) denotes the number of restrictions. Each of the following M lines represent a restriction with a pair of integer X and Y(1 ≤ X, Y ≤ N). One pair states that bus X should be parked before the bus Y.

The last part of the input contains N integers that denote the available order of the buses. The buses are numbered from 1 to N and there are at most 40 buses in one line, that is, the lines contain less than 255 chars. )

Output Specifications

Give just one integer Res (where 0 ≤ Res ≤ M). That means there are Res restrictions which are not satisfied with the given bus order. If all the restrictions are satisfied with the current bus order, show 0 (zero).

Sample Input

6 7
1 3
2 4
1 6
5 4
4 6
3 6
2 1
2 3 1 5 6 4

Sample Output

2

Explanation for the sample output.

There are two restrictions (the first (1 3) and the fifth (4 6) restrictions) that does not satisfy the given conditions.

Для отправки решений необходимо выполнить вход.

www.contester.ru