Problem description

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 a_i, b_i, oddzielone pojedynczym odstępem oznaczające, że kulka a_i oddziałuje z b_i.

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

3 2
1 3
2 3

AAB

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

NIE