Ramsey nəzəriyyəsi
Karta "Among Us" oyununda qeyri-yonlu bir qraf kimi təsvir edilir, burada zirvələr otaqları, kənarlar isə bu otaqlar arasındakı iki tərəfli tunelləri təmsil edir. Oyunun inkişafçısı Ramseya, xəritənin maraqlı olması üçün müəyyən xüsusiyyətlərə sahib olmasının vacib olduğunu düşünür.
Oyunda k xəyanətkar və l adi ekipaj üzvü olacaq. Əgər qrafda l-klik varsa - yəni hər bir cütü kənarla birləşdirilmiş l zirvədən ibarət dəst - ekipaj üzvləri bu zirvələr arasında paylanacaq və onlardan biri öldürüldükdə, qonşu otaqlardakı bütün oyunçular dərhal toplaşacaq, qatili tapacaq və cəzalandıracaq. Bu vəziyyət oyunu maraqsız edəcək.
Digər tərəfdən, əgər qrafda k-antiklik varsa - yəni hər bir cütü kənarla birləşdirilməmiş k zirvədən ibarət dəst - xəyanətkarlar bu zirvələrdə durub, yaxşı oyunçuları ora cəlb edib öldürə biləcəklər və çox güman ki, bu zaman gözə dəymədən qalacaqlar. Ramseya belə bir strategiyanın da oyunu maraqsız edəcəyini düşünür.
Qrafda l-klik və ya k-antiklik tapacaq və ya onların qrafda olmadığını müəyyən edəcək bir proqram yazın (və bu halda oyun maraqlı olacaq).
Giriş məlumatları
Birinci sətirdə dörd ədəd n, m, k, l (1 ≤ n ≤ 300 000, 0 ≤ m ≤ 300 000, 1 ≤ k, l ≤ min(5, n)) - qrafın zirvə və kənarlarının sayı, həmçinin axtarılan antiklik və klik ölçüləri.
Növbəti m sətirdə iki tam ədəd a[i], b[i] (1 ≤ a[i] < b[i] ≤ n) - qrafın növbəti kənarının ucları. Bütün kənarların fərqli olduğu təmin edilir.
Çıxış məlumatları
Əgər siz zirvələr dəstini tapmısınızsa, hansı ki, ya k-antiklik, ya da l-klikdir, bu zirvələrin nömrələrini boşluqla ayıraraq çıxarın. Əgər belə bir zirvələr dəsti yoxdursa, "-1" çıxarın.
Qeyd
Birinci nümunə bütün tərəfləri çəkilmiş, lakin diaqonalları çəkilməmiş beşbucağa bənzəyir. Orada nə üçbucaq, nə də anti-üçbucaq yoxdur, buna görə cavab "-1".
İkinci və üçüncü nümunələrdə qraf boşdur. İkinci nümunədə ya antikənar, ya da zirvələrdə 4-klik tapmaq tələb olunur. Cavab 1-dən 4-ə qədər olan müxtəlif ədədlərin istənilən cütü olacaq. Üçüncü nümunədə isə əksinə - ya 4-antiklik, ya da kənar tapmaq lazımdır. Kənarlar olmadığı üçün, bu nümunəyə yeganə düzgün cavab 1-dən 4-ə qədər olan bütün ədədlərin dəstidir (istənilən ardıcıllıqla sadalanmış).
Dördüncü nümunədə tam qraf verilir və düzgün cavab onun zirvələrinin istənilən dördlüyüdür (çünki o, onun kliki olacaq). Lakin bir zirvədən ibarət dəst həmişə həm klik, həm də antiklikdir; buna görə də, nümunədə 1-antiklik çıxarmağa icazə verildiyi üçün, istənilən bir zirvədən ibarət çoxluq da düzgün cavabdır.