Doominokivid

시간 제한1.5초메모리 제한1024 MB

요약

N개의 도미노를 두 상자에 나눠 담되 각 상자에서 기호가 겹치지 않게 하고, 사전순으로 가장 앞선 배치를 출력한다.

난이도: 보통10점 중 6점
유형: 그래프, DFS, 유니온 파인드, 그리디
정답자: 아직 제출이 없습니다

문제

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.

예제6

예제 1
입력
```
4
1 2
4 3
2 1
3 4
```
예상 출력
```
JAH
AABB
```
예제 2
입력
```
6
1 2
4 5
1 3
4 6
2 3
5 6
```
예상 출력
```
EI
```
예제 3
입력
```
2
1 1
2 2
```
예상 출력
```
EI
```
예제 4
입력
```
2
1 2
2 1
```
예상 출력
```
JAH
AB
```

예제 5

입력

예상 출력

JAH
ABABABBA

예제 6
입력
```
8
1 2
2 1
4 3
5 3
5 4
6 7
8 6
7 8
```
예상 출력
```
EI
```