eolymp
bolt
Try our new interface for solving problems
Problems

Археологи

Археологи

Time limit 0.2 seconds
Memory limit 256 MiB

Ученые-археологи планеты Олимпия недавно обнаружили руины древнего города, кторый принадлежал неизвестной ранее цивилизации. Все, что сохранилось, — это N башен и M стен, каждая из которых соединяет некоторую пару башен между собой. В упрощенной модели башни можно представить точками на плоскости, а стены — отрезками, которые их соединяют. Само собой, две стены не могут пересекаться в середине, хоть и могут выходить из одной и той же башни. С целью изучения города были задействованы K археологов, которые расположились на территории города. В упрощенной модели их положения можно изобразить точками на плоскости. Ни один археолог не находится на башне или на стене. На территории города нет никакой мобильной или радио- связи, поэтому общаться между собой археологи могут только при встрече. Считается, что два археолога могут встретиться друг с другом, если они оба могут дойти от своих изначальных позиций до одной и той же точки плоскости, при этом не пересекая стен и башен. Между двумя точками археолог может передвигаться по произвольной кривой.

Задание

Напишите программу archaeology, которая по данным о расположении башен, стен и археологов найдет количество пар археологов, которые могут встретиться друг с другом.

Input data

В первой строке файла содержатся 3 натуральных числа N, M и K (1 ≤ N ≤ 5∙10^4, 1 ≤ M ≤ 10^5, 1 ≤ K ≤ 5∙10^4) — количество башен, стен и археологов соответственно. СледующиеNстрок содержат по 2 целых числа, каждое из которых не превосходит 10^6 по абсолютной величине — координаты башен. Никакие две башни не расположены в одной точке. Следующие M строк содержат по 2 разных целых числа — номера башен, которые соединены очередной стеной. Башни нумеруются числами от 1 до N. Гарантируется, что 2 стены не могут иметь никаких других общих точек, кроме их концов. Также гарантируется, что никакая башня не лежит ни на какой стене, кроме случая, когда эта башня является концом стены. Следующие K строк содержат по целых числа, каждое из которых по модулю не превосходит 10^6, — координаты археологов. Ни один археолог не находится на стене или на башне.

Output data

Выходной файл должен содержать одно число — количество пар археологов, которые могут встретиться друг с другом.

Examples

Input example #1
4 5 7
0 0
10 0
10 10
0 10
1 2
2 3
3 4
4 1
4 2
1 1
2 2
9 9
8 8
-1 -1
-5 -5
100 100
Output example #1
5

Scoring

Набор тестов состоит из 6 блоков, для которых дополнительно выполняются такие условия:

  1. 15 баллов: 2 ≤ N ≤ 4, 1 ≤ K ≤ 10.

  2. 15 баллов: 3 ≤ N ≤ 1000, 1 ≤ K ≤ 1000, каждая башня являеся концом не более чем двух стен.

  3. 20 баллов: все стены параллельны осям координат, все координаты не превосходят 500 по абсолютной величине.

  4. 15 баллов: 2 ≤ NK ≤ 1 000 000.

  5. 15 баллов: все стены параллельны осям координат.

  6. 20 баллов: нет дополнительных ограничений.

Author Ярослав Твердохлеб
Source XXVII Всеукраинская ученическая олимпиада по информатике (2014) Днепропетровск