Wstęp do programowania w C++

Mateusz posiada naszyjnik złożony z wielu kamieni szlachetnych. Nasz bohater opisał go w postaci ciągu małych liter alfabetu angielskiego. Litera i-ta w kolejności określa rodzaj i-tego kamienia szlachetnego. Mateusz chce podzielić swój naszyjnik na dwa, a następnie sprzedać je z zyskiem.

Podział ma zostać wykonany zgodnie z poniższym planem:

1. Nasz bohater wybierze pewien niepusty podciąg kamieni szlachetnych z ciągu reprezentującego naszyjnik. Wybrany podciąg nie musi być spójny.
2. Z połączenia kamieni szlachetnych z wybranego podciągu utworzy pierwszy naszyjnik.
3. Z połączenia pozostałych kamieni szlachetnych utworzy drugi naszyjnik.

Niestety operacja podziału nie jest taka prosta jakby się mogło wydawać i Mateusz musi jeszcze spełnić poniższe wymagania:

• Kolejność kamieni szlachetnych w utworzonych naszyjnikach musi być zgodna z ich kolejnością w początkowym naszyjniku.
• Utworzone naszyjniki muszą być symetryczne. Innymi słowy po zapisaniu ich w postaci ciągu małych liter alfabetu angielskiego, muszą być one palindromami.
• Żaden rodzaj kamienia szlachetnego nie może występować w obydwu naszyjnikach.

Odpowiedz na pytanie, czy podział naszyjnika zgodnie z powyższymi założeniami jest możliwy? Jeżeli tak przypisz każdy z kamieni szlachetnych do odpowiedniego naszyjnika.

Wejście

W pierwszej linii wejścia znajduje się liczba zestawów danych t ∈ [1, 79]. W kolejnych t liniach znajdują się zestawy danych.

Każdy zestaw danych składa się z ciągu małych liter alfabetu angielskiego, który opisuje naszyjnik posiadany przez Mateusza. Długość ciągu nie przekracza 10⁵ liter.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać TAK jeżeli podział naszyjnika zgodnie z powyższymi założeniami jest możliwy albo NIE w przeciwnym wypadku.

Jeżeli podział jest możliwy w kolejnej linii należy wypisać ciąg cyfr 1 lub 2. Cyfra i-ta w kolejności określa czy i-ty kamień szlachetny powinien zostać dołączony do naszyjnika numer 1 czy 2. Jeżeli istnieje wiele podziałów spełniających powyższe założenia, wypisz dowolny z nich.

Przykład

Wejście:

3
uurstaaartsuu
abab
fraktalrf

Wyjście:

TAK
1121111121111
TAK
1212
NIE

Wyjaśnienie do przykładu:

Podziały spełniające powyższe założenia dla pierwszego zestawu danych:

• 1112211112211 - naszyjnik 1: uuraaaruu, naszyjnik 2: stts
• 1112222212211 - naszyjnik 1: uurruu, naszyjnik 2: staaats
• 1121111121111 - naszyjnik 1: uustaaatsuu, naszyjnik 2: rr
• 1121122221111 - naszyjnik 1: uusttsuu, naszyjnik 2: raaar
• 2212211112222 - naszyjnik 1: raaar, naszyjnik 2: uusttsuu
• 2212222212222 - naszyjnik 1: rr, naszyjnik 2: uustaaatsuu
• 2221111121122 - naszyjnik 1: staaats, naszyjnik 2: uurruu
• 2221122221122 - naszyjnik 1: stts, naszyjnik 2: uuraaaruu

Podziały spełniające powyższe założenia dla drugiego zestawu danych:

• 1212 - naszyjnik 1: aa, naszyjnik 2: bb
• 2121 - naszyjnik 1: bb, naszyjnik 2: aa