Müsabiqə!
Berlyandiyada hər il keçirilən "Berland Open" adlı idman proqramlaşdırma müsabiqəsi baş tutur. Bildiyiniz kimi, sabah n dörddəbir final keçiriləcək və bu yarışlarda 2n proqramçı iştirak edəcək, hər dörddəbir finalda iki nəfər yarışacaq. Yarışlardan sonra bütün n qaliblərin dəvət olunacağı mükafatlandırma mərasimi təşkil ediləcək.
Təəssüf ki, Berlyandiyada proqramçılar arasında münasibətlər çox gərgindir. Xüsusilə, m cüt iştirakçı var ki, onlar bir-birini o qədər sevmirlər ki, əgər mükafatlandırma mərasimində bir cütdən hər iki iştirakçı iştirak edərsə, mərasim pozulacaq.
Vasinin çətin vəzifəsi mükafatlandırma mərasimini idarə etmək və proqramçıları əyləndirməkdir. O, bunu etmək istəmir və mərasimin pozulacağına ümid edir. Bu gün o, proqramçıların n dörddəbir finala bölünməsi üçün gizli planı əldə edib. Ona mərasimin uğurla keçirilməsi üçün heç olmasa bir şansın olub-olmadığını müəyyən etməyə kömək edin.
Giriş məlumatları
Birinci sətir iki tam qeyri-mənfi ədəd n və m (0 ≤ n ≤ 10^5, 0 ≤ m ≤ 10^6) ehtiva edir. Sonra n sətir gəlir, hər birində iki ədəd - i-ci dörddəbir final iştirakçılarının nömrələri. Daha sonra m sətir gəlir, hər biri iki ədəd u, v ehtiva edir (1 ≤ u, v ≤ 2n), bu da u-ci və v-ci proqramçıların münaqişə etdiyini və onların mükafatlandırma mərasimində eyni vaxtda iştirak etməsinin mərasimin pozulması demək olduğunu göstərir. Eyni cüt bir neçə dəfə qeyd edilə bilər.
Proqramçılar 1-dən 2n-ə qədər təbii ədədlərlə nömrələnib.
Çıxış məlumatları
Əgər mərasimin uğurla keçirilməsi üçün heç olmasa bir şans varsa, n ədəd çıxarın - bu mərasimdə iştirak etməli olan proqramçıların nömrələri (uğurlu mərasimin bir neçə variantı varsa, istənilənini çıxarın).
Əgər münaqişəsiz qalibləri seçmək mümkün deyilsə, bir ədəd -1 çıxarın.