eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Остоз

Остоз

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Для лікування від ниркового фіброкистозного остозу необхідно переправитись через болото. Для переправи можна використовувати дошки, які з'єднують купини. Після того, як на купині хто-небудь побував, вона тоне.

Вам потрібно вилікувати максимальну кількість людей від ниркового фіброкистозного остозу.

Вхідні дані

У першому рядку вхідного файлу записано число дощок n (1n1000). Далі для кожної дошки записані координати купин — кінців дошки (-2^31x_i, y_i2^31). Потім записані координати початкової та кінцевої точок (точки різні і дошки, що їх з'єднує, немає). Усі числа у вхідному файлі цілі.

Вихідні дані

Виведіть максимальну кількість людей, яких можна вилікувати.

Приклад

Вхідні дані #1
50
-1437631685 -1360931160 1034650579 1761690038
-96316407 1866517818 -540011503 2067778674
682284995 515765286 1696339001 -1238191020
682284995 515765286 118275291 1687229310
1696339001 -1238191020 925027165 -1783025200
587379207 -943776970 1622772255 -1918353186
-2033632427 1895061198 118275291 1687229310
925027165 -1783025200 -1814343143 189627818
-1582694761 24442204 682284995 515765286
587379207 -943776970 1244556799 -1773993986
1696339001 -1238191020 -1377448401 808841092
1889223905 -454773780 118275291 1687229310
1244556799 -1773993986 333635569 -715387044
713634739 293760662 -540011503 2067778674
1244556799 -1773993986 1218160321 -1607457524
-1437631685 -1360931160 529163451 644970590
-96316407 1866517818 -2033632427 1895061198
-980788965 1817411192 -1229087853 1117208768
-1814343143 189627818 -1652231371 -1485070830
118275291 1687229310 -1377448401 808841092
-1377448401 808841092 -540011503 2067778674
-1582694761 24442204 -2033632427 1895061198
713634739 293760662 -1377448401 
...
Вихідні дані #1
3