Arxeoloqlar
Planet Olimpiya arxeoloq-alimləri yaxınlarda əvvəllər məlum olmayan bir sivilizasiyaya aid qədim bir şəhərin xarabalıqlarını kəşf etdilər. Bu şəhərin qalıqları arasında N qüllə və M divar var, hər biri bəzi qüllə cütlərini birləşdirir. Sadələşdirilmiş modeldə qüllələri müstəvidə nöqtələr, divarları isə onları birləşdirən seqmentlər kimi təsəvvür etmək olar. Təbii ki, iki divar bir-birinin içindən keçə bilməz, lakin eyni qüllədən çıxa bilərlər. Şəhəri öyrənmək üçün ərazidə K arxeoloq yerləşdirilib. Sadələşdirilmiş modeldə onların mövqelərini müstəvidə nöqtələr kimi təsvir etmək olar. Heç bir arxeoloq qüllədə və ya divarda yerləşmir. Şəhər ərazisində heç bir mobil və ya radio rabitəsi yoxdur, buna görə də arxeoloqlar yalnız görüşdükdə bir-biri ilə ünsiyyət qura bilərlər. İki arxeoloqun bir-biri ilə görüşə biləcəyi hesab olunur ki, əgər hər ikisi öz başlanğıc mövqelərindən müstəvinin eyni nöqtəsinə gedə bilərlərsə, divarları və qüllələri keçmədən. Bir nöqtədən digərinə arxeoloq istənilən əyri ilə hərəkət edə bilər.
**Tapşırıq**
Qüllələrin, divarların və arxeoloqların yerləşməsi haqqında məlumatlara əsaslanaraq bir-biri ilə görüşə biləcək arxeoloq cütlərinin sayını tapacaq proqram yazın.
Giriş verilənləri
Faylın birinci sətirində üç natural ədəd N, M və K (1 ≤ N ≤ 5∙10^4, 1 ≤ M ≤ 10^5, 1 ≤ K ≤ 5∙10^4) — müvafiq olaraq qüllələrin, divarların və arxeoloqların sayı. Növbəti N sətir hər biri modulu 10^6-dan çox olmayan 2 tam ədəd — qüllələrin koordinatlarını ehtiva edir. Heç bir 2 qüllə eyni nöqtədə yerləşmir. Növbəti M sətir hər biri fərqli 2 tam ədəd — növbəti divarla birləşdirilən qüllələrin nömrələrini ehtiva edir. Qüllələr 1-dən N-ə qədər nömrələnir. İki divarın öz uclarından başqa heç bir ortaq nöqtəyə malik ola bilməyəcəyinə zəmanət verilir. Həmçinin, heç bir qüllənin divarın üzərində olmadığına, yalnız divarın ucu olduğu halda zəmanət verilir. Növbəti K sətir hər biri modulu 10^6-dan çox olmayan 2 tam ədəd — arxeoloqların koordinatlarını ehtiva edir. Heç bir arxeoloq divarın və ya qüllənin üzərində yerləşmir.
Çıxış verilənləri
Çıxış faylı bir-biri ilə görüşə biləcək arxeoloq cütlərinin sayını ehtiva edən tək bir ədəd olmalıdır.
Nümunələr
Qiymətləndirmə
Test dəsti 6 blokdan ibarətdir, bunlar üçün əlavə şərtlər yerinə yetirilir:
15 bal: 2 ≤ N ≤ 4, 1 ≤ K ≤ 10.
15 bal: 3 ≤ N ≤ 1000, 1 ≤ K ≤ 1000, hər qüllə ən çox iki divarın ucu olur.
20 bal: bütün divarlar koordinat oxlarına paraleldir, bütün koordinatlar modulu 500-dən çox deyil.
15 bal: 2 ≤ N∙K ≤ 1 000 000.
15 bal: bütün divarlar koordinat oxlarına paraleldir.
20 bal: əlavə məhdudiyyətlər yoxdur.