Пете необходимо переправить стадо коров через болото. Для переправы можно использовать доски, которые соединяют кочки. После того, как на кочке кто-нибудь побывал, она тонет. Вам требуется переправить максимальное количество коров через болото.
Входные данные
В первой строке входного файла записано число досок N (0 <= N <= 1000). Далее для каждой доски записаны координаты кочек - концов доски (-2
31 <= X
i,Y
i <= 2
31). Затем записаны координаты начальной и конечной точек (точки различны и доски, их соединяющей нет). Все числа во входном файле целые.
Выходные данные
Вывести максимально количество коров, которых можно переправить
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
8
0 0 1 0
1 0 2 1
1 0 2 -1
2 1 3 0
2 -1 3 0
1 0 4 0
3 0 4 0
0 0 3 0
0 0
4 0 |
2 |