URI Online Judge | 1863

Ramsay's Counter-attack

By Ricardo Oliveira, UFPR BR Brazil

Timelimit: 2

Ramsay: "I don't need an army. I need 20 good men."

The Boltons have conquered the castle of Winterfell and now need to protect it from the incoming invasion of "King" Stannis. Stannis' N soldiers are currently positioned in the way from Castle Black, which is northeast from Winterfell, to Winterfell. For each soldier i (1 ≤ iN), the Boltons know his position (x[i], y[i]) on the map.

Ramsay Bolton decided to counter-attack before the invasion by sending his men to kill some of Stannis' soldiers. Ramsay wants them killed one by one, in an order such that his men must only travel north and east, and all soldier must be stronger than all others killed before him (that's madness, but Ramsay is mad anyway).

In other words, Ramsay wants to find a sequence of soldiers (s1, s2, ..., sK) such that, for all 1 < iK:

A spy gave Ramsay a list of M ordered pairs of soldiers in the form (i, j), indicating that soldier i is stronger than soldier j. Please note that this relation is transitive, i.e., if i is stronger than j and j is stronger than k, then i is stronger than k, even if (i, k) is not in the list. Also, for any pair of soldiers i and j, if it is not possible to determine whether one solder is stronger than the other from the list, then i is not considered stronger than j, and j is not considered stronger than i. Finally, the list is given in such a way that, for all soldier i, there is at most one soldier j such that (i, j) is in the list.

Your task is to determine the maximum number of soldiers Ramsay can have killed.


The first line contains two integers N and M (0 ≤ M < N ≤ 5×104). The next N lines give the positions of the soldiers. The i-th line contains two integers x[i] and y[i] ( -400 ≤ x[i], y[i] ≤ 400 ). No two soldiers are in the same position. The last M lines contains two integers i and j each (1 ≤ i, jN, i j), describing the list given by the spy.


Print a single line containing the maximum number of soldiers that can be killed.

Input Samples Output Samples

6 5
1 3
4 2
5 5
3 7
8 1
9 3
1 4
4 3
2 4
5 1
6 5