Təsadüfi Gəzinti
Maymunların Pul Atma Ordusu (ACM) təsadüfi ədədlər yaratmaqla məşğuldur. Təsadüfi ədədlər kriptoqrafiya, onlayn qumar, təsadüfi alqoritmlər və proqramlaşdırma yarışmalarında son dəqiqə həlləri kimi bir çox sahədə vacibdir.
Son vaxtlar, ən yaxşı maymunlardan biri təqaüdə çıxdı. Lakin, getməzdən əvvəl, o, pul atan maymunların yaratdığı təsadüfiliyi birbaşa istifadə etməkdən daha ucuz bir üsul icad etdi. Bu metod, 2^n düyünləri 0, 1, ..., 2^n - 1 ilə işarələnmiş istiqamətsiz qrafı götürməklə başlayır. k təsadüfi n-bit ədədləri yaratmaq üçün, maymunlar qrafda haradan başlayacaqlarını qərar vermək üçün n sikkə atacaqlar. Bu düyün nömrəsi ilk çıxış ədədi olacaq. Sonra maymunlar bu düyündən təsadüfi bir kənar seçəcək və bu kənarın bağlandığı düyünə keçəcəklər. Bu yeni düyün ikinci təsadüfi ədəd çıxışı olacaq. Sonra bu düyündən təsadüfi bir kənar seçəcəklər (mümkün ki, son addımda gəldikləri düyünə geri), onu izləyəcəklər və endikləri düyünün nömrəsini çıxış edəcəklər. Bu gəzinti k ədəd çıxış edilənə qədər davam edəcək.
Eksperimentlər zamanı ACM fərqli qrafların fərqli çıxış paylanmaları verdiyini müşahidə edib, bəziləri çox da təsadüfi deyil. Buna görə də, təsadüfiliyin satılacaq qədər keyfiyyətli olub-olmadığını yoxlamaq üçün qrafların test edilməsində köməyinizə ehtiyac duyurlar.
Onlar qrafı yaxşı hesab edirlər əgər, yaradılan hər k ədədin hər n bitində, bu bitin 1 olaraq çıxış edilmə ehtimalı 25%-dən böyük və 75%-dən kiçikdirsə.
Giriş verilənləri
Bir neçə məlumat dəstindən ibarətdir. Hər dəst bir sətirdən başlayacaq və burada k, n, e rəqəmləri tək boşluqlarla ayrılmış şəkildə veriləcək, burada k yaradılacaq n-bit ədədlərin sayı, e isə qrafdakı kənarların sayıdır (1 ≤ k ≤ 100, 1 ≤ n ≤ 10 və 1 ≤ e ≤ 2000). Növbəti e sətir iki boşluqla ayrılmış tam ədəd v_1, v_2 ibarət olacaq, burada 0 ≤ v_1, v_2 < 2^n və v_1 ≠ v_2. Kənarlar istiqamətsizdir və hər düyün ən azı bir kənara malikdir. Eyni düyün cütləri arasında çoxlu kənarlar ola bilər.
Son test halı k = n = e = 0 olan bir sətirlə izlənəcək və bu işlənməməlidir.
Çıxış verilənləri
Hər giriş halı üçün, qraf yaxşıdırsa Bəli, əks halda Xeyr sözündən ibarət bir sətir çıxış edin.