Problem description


Ładunki
(ladunki)
Limit pamięci: 128 MB
Limit czasu: 4.00 s

Jasio nauczył się na lekcji fizyki, że ładunki jednoimienne się odpychają, a różnoimienne się przyciągają. Planuje on zrobić konstrukcję z kulek, w której niektóre z nich będą na siebie oddziaływać. Dodatkowo chciałby, żeby była ona stabilna, to znaczy żeby żadna para oddziałujących na siebie kulek nie odpychała się, innymi słowy – by miały różne ładunki. Ustalił już plan konstrukcji (czyli pary kulek oddziałujące na siebie) i dla każdej z kulek musi teraz wybrać, jak będzie naładowana. Dla uproszczenia (albo utrudnienia) przyjmujemy, że są trzy możliwe ładunki kulek: A, B, C i dwie kulki się odpychają jeśli mają takie same ładunki.

Napisz program, który: wczyta plan konstrukcji, wyznaczy takie naładowanie wszystkich kulek, by konstrukcja była stabilna i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i M oznaczające odpowiednio liczbę kulek i liczbę oddziałujących na siebie par. W kolejnych M liniach znajdują się pary liczb postaci ai, bi, oddzielone pojedynczym odstępem oznaczające, że kulka ai oddziałuje z bi.

Kulki numerowane są kolejnymi liczbami naturalnymi od 1 do N włącznie. Żadna (nieuporządkowana) para kulek nie wystąpi na wejściu więcej niż raz.

Wyjście

W pierwszym (jedynym) wierszu wejścia należy wypisać ciąg N znaków A, B lub C. i–ty znak ma określać ładunek i-tej kulki.

Jeśli rozwiązanie nie istnieje, zamiast tego należy wypisać jedno słowo NIE.

Jeśli istnieje wiele rozwiązań, wypisać należy ciąg najmniejszy leksykograficznie.

Ograniczenia

1 ≤ N ≤ 25.

Przykład

Wejście Wyjście
3 2
1 3
2 3
AAB
Wejście Wyjście
4 6
2 4
1 2
3 2
4 1
3 4
3 1
NIE