Sel
1964-cü ildə Zaqreb şəhəri dağıdıcı bir daşqınla üzləşdi. Bu daşqın nəticəsində bir çox binaların divarları suyun gücü ilə yıxıldı. Bu məsələdə, sizə daşqından əvvəl şəhərin sadələşdirilmiş modeli təqdim olunur və sizdən hansı divarların daşqından sonra salamat qalacağını müəyyən etmək tələb olunur.
Model, koordinat müstəvisində yerləşən N nöqtədən və W divardan ibarətdir. Hər bir divar iki nöqtəni birləşdirir və digər nöqtələrdən keçmir. Modelin aşağıdakı xüsusiyyətləri var:
- Heç bir iki divar bir-birini kəsmir və ya üst-üstə düşmür, yalnız ortaq ucları ola bilər;
- Hər bir divar ya üfüqi, ya da şaquli koordinat oxuna paraleldir.
Başlanğıcda bütün koordinat müstəvisi qurudur. Sıfır vaxtında su dərhal xarici məkanı (divarlarla məhdudlaşdırılmayan məkanı) su basır. Tam bir saat sonra, bir tərəfi su, digər tərəfi hava olan hər bir divar suyun təzyiqi altında dağılır. Bundan sonra su dərhal bütöv divarlarla məhdudlaşdırılmayan məkanı su basır. Nəticədə, bir tərəfi su, digər tərəfi hava olan yeni divarlar yarana bilər. Bir saat sonra bu divarlar da dağılır və su yeni məkana daxil olur. Bu proses su bütün ərazini basana qədər davam edir.
Dağılma prosesinin nümunəsi şəkildə göstərilmişdir (vəziyyətlər arasında interval bir saatdır).
Tapşırıq
Verilmiş N nöqtənin koordinatları və bu nöqtələri birləşdirən W divarların təsviri əsasında daşqından sonra salamat qalacaq divarları müəyyən edən proqram yazın.
Giriş verilənləri
Giriş məlumatlarının ilk sətiri müstəvidəki nöqtələrin sayı olan N (2 ≤ N ≤ 100 000) tam ədədini ehtiva edir. Növbəti N sətirin hər biri iki tam ədəd X və Y (hər biri 0 ilə 1 000 000 arasında daxil olmaqla) ehtiva edir - nöqtənin koordinatları. Nöqtələr verildiyi ardıcıllıqla 1 -dən N -ə qədər nömrələnir. Heç bir iki nöqtə üst-üstə düşmür.
Növbəti sətir divarların sayı olan W (1 ≤ W ≤ 2N) tam ədədini ehtiva edir.
Növbəti W sətirin hər biri iki fərqli tam ədəd A və B (1 ≤ A, B ≤ N) ehtiva edir ki, bu da daşqından əvvəl A və B nöqtələrini birləşdirən divarın olduğunu göstərir. Divarlar verildiyi ardıcıllıqla 1 -dən W -ə qədər nömrələnir.
Çıxış verilənləri
Çıxış məlumatlarının ilk sətiri daşqından sonra salamat qalacaq divarların sayı olan K tam ədədini ehtiva etməlidir.
Növbəti K sətir hər biri bir divarın nömrəsini ehtiva etməlidir. Divarların nömrələri istənilən ardıcıllıqla verilə bilər.