시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 1024 MB143325.000%

문제

Jukul on põrandal laiali hunnik doominokive. Ema käskis Jukul toa korda teha, seega nüüd peab Juku kivid karpidesse tagasi panema.

Igal doominokivil on kaks sümbolit, mida ülesande tarbeks tähistame positiivsete täisarvudega. Juku mäletab, et kivid pärinevad kahest erinevast komplektist, kusjuures kummaski komplektis ei esinenud ühtki sümbolit mitu korda.

Leia, kas Jukul on võimalik panna kivid kahte karpi nii, et kummaski karbis ei esine ühtki sümbolit mitu korda. (Juku võis ka valesti mäletada, et kivid pärinevad kahest sellisest komplektist.) Kui kivide karpidesse panemine on võimalik, leia ka üks viis neid karpidesse panna.

입력

Sisendi esimesel real on doominokivide arv $N$ ($2 \le N \le 2 \cdot 10^5$). Järgmisel $N$ real on igaühel kaks täisarvu $A_i$ ja $B_i$ ($1 \le A_i, B_i \le 10^9$), mis tähistavad $i$-ndal kivil olevaid sümboleid.

출력

Esimesele reale väljastada "JAH", kui kivide karpidesse paigutamine on võimalik, või "EI", kui ei ole.

Kui kivide karpidesse paigutamine on võimalik, väljastada teisele reale $N$ tähest koosnev sõne, kus $i$-s täht on 'A', kui $i$-s kivi läheb esimesse karpi ning 'B', kui $i$-s kivi läheb teise karpi. Kui võimalikke kivide karpidesse paigutusi on mitu, väljastada neist tähestikulises järjekorras esimene.

예제 입력 1

4
1 2
4 3
2 1
3 4

예제 출력 1

JAH
AABB

예제 입력 2

6
1 2
4 5
1 3
4 6
2 3
5 6

예제 출력 2

EI

예제 입력 3

2
1 1
2 2

예제 출력 3

EI

예제 입력 4

2
1 2
2 1

예제 출력 4

JAH
AB

예제 입력 5

8
2 1
1 2
4 3
4 3
5 6
5 7
8 6
7 8

예제 출력 5

JAH
ABABABBA

예제 입력 6

8
1 2
2 1
4 3
5 3
5 4
6 7
8 6
7 8

예제 출력 6

EI