시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 74 | 54 | 28 | 66.667% |
Na gozbu je pozvano 2n studenata. Oni sjede oko okruglog stola i označeni su redom u smjeru kazaljke na satu od 1 do 2n. Student s oznakom j sjedi pored studenata s oznakama (j − 1) te (j + 1), gdje smatramo da su studenti s oznakama 1 i 2n također susjedni. Dodatno, studenti su podijeljeni u n parova najboljih prijatelja. Parovi su disjunktni, dakle svaki student je u točno jednom paru.
Gospodin Malnar će odrediti koje je jelo najbolje za svakog studenta. Danas su u ponudi dvije vrste jela, A i B, a gospodin Malnar zbog raznolikosti jela želi napraviti odabir koji zadovoljava sljedeće:
Gospodin Malnar se već dosjetio jednog rasporeda, a sada ga zanima možete li i vi pronaći jedan. Ispišite bilo koji odabir jela za studente koji zadovoljava navedene uvjete, a u slučaju da se gospodin Malnar našalio i takav raspored ne postoji, ispišite "Malnar se nasalio"
(bez navodnika).
U prvom je retku prirodan broj n (2 ≤ n ≤ 5 · 105), broj parova studenata.
U sljedećih n redaka nalazi se par različitih prirodnih brojeva x i y (1 ≤ x, y ≤ 2n) koji označava par studenata koji su najbolji prijatelji.
Svaki student će biti član točno jednog para.
U slučaju da ne postoji rješenje ispišite "Malnar se nasalio"
(bez navodnika).
U protivnom, u jedini redak ispišite niz od 2n znakova A
ili B
koji opisuje valjani izbor jela za studente. Po redu i-ti znak treba predstavljati odabir za i-tog studenta.
Ako postoji više valjanih odabira, ispišite bilo koji.
3 1 4 2 3 5 6
AABBAB