Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_16_19 - Naszyjnik

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 105 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

Dodane przez:Maciej Boniecki
Data dodania:2022-12-16
Limit czasu wykonania programu:2s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM32-GCC COBOL D-CLANG D-DMD ELIXIR FANTOM GOSU GRV JS-MONKEY NIM OBJC OBJC-CLANG PICO RUST SCM qobi CHICKEN VB.NET

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.