Dat je niz reči dužine n kojeg ćemo u dalje tekstu zvati rečnik. Reči su sastavljene od malih slova engleskog alfabeta. Za tekst S koji je takođe sastavljen od malih slova engleskog alfabeta, kažemo da ima razbijanje (r₁, r₂, ... , r_m) ukoliko:

• r_i pripada rečniku za i ∈ [1, m]
• r₁r₂ ... r_m = S (konkatenacija, nadovezivanje reči)

Za rečnik kažemo da je nedvosmislen ukoliko svaka reč koja se može dobiti nadovezivanjem reči iz rečnika ima jedinstveno razbijanje.
Napisati program koji za dati rečnik ispituje da li je dvosmislen ili ne.

Ulaz.

(Ulazni podaci se učitavaju iz datoteke recnik.in.) U prvom redu ulazne datoteke nalazi se prirodni broj T ≤ 10 koji označava broj primera. Svaki primer je opisan na sledeći način: u prvom redu se nalazi prirodan broj n (2 ≤ n ≤ 100) koji označava broj reči u rečniku. Narednih n linija opisuju rečnik (u svakom redu je data po jedna reč). Između primera neće biti praznih redova. Reči će biti sastavljene od malih slova engleskog alfabeta i njihova dužina neće biti veća od 1000.

Izlaz.

(Izlazne podatke upisati u datoteku recnik.out) Za svaki primer u uzlaznoj datoteci, u redosledu kojim su dati na ulazu, šampati u posebnom redu dvosmislen ukoliko je rečnik dvosmislen; u suprotnom štampati nedvosmislen.

Primer 1.

2
4
andre
and
jko
rejko
3
a
ab
bb

dvosmislen
nedvosmislen

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <memory.h>

const int MaxN = 110;
const int MaxD = 1010;
const int MaxT = 11;
const int MOD = 10000019;

struct Node {
  int ind, d;
  Node(int _ind, int _d) {
    ind = _ind; d = _d;
  }
  Node() {}
};

int n, T;
char s[MaxN][MaxD];
bool sol[MaxT];
int len[MaxN];
int preff[MaxN][MaxD], pow26[MaxD];
Node Q[MaxN * MaxD];
bool mark[MaxN][MaxD];


void makeHash() {
  int val;

  pow26[0] = 1;
  for (int i = 1; i < MaxD; i++)
    pow26[i] = (pow26[i - 1] * 26 ) % MOD;
  for (int i = 0; i < n; i++) {
    val = 0;
    for (int j = 0; j < len[i]; j++) {
      val = (26 * val + (s[i][j] - 'a')) % MOD;
      preff[i][j] = val;
    }
  }
}


// hash vrednost s[num] od l-tog do r-tog karaktera
int hashValue(int num, int l, int r) {
  int val;
  if (l == 0) return preff[num][r];
  long long tmp = pow26[r - l + 1];
  val = (preff[num][r] - preff[num][l - 1] * tmp) % MOD;
  //val = (preff[num][r] - preff[num][l - 1] * pow26[r - l + 1]) % MOD;
  if (val < 0) val += MOD;
  return val;
}


// da li postoji put [ind1][d] -> [ind2][nesto] u grafu
bool match(int ind1, int d, int ind2) {
  int l1, r1, l2, r2, i, D;
  bool ok;
  if (ind1 == ind2 && d == len[ind1]) return false;

  D = (len[ind2] <= d ? len[ind2] : d);
  l1 = len[ind1] - d;  r1 = l1 + D - 1;
  l2 = 0;  r2 = D - 1;

  if (hashValue(ind1, l1, r1) != hashValue(ind2, l2, r2))
    return false;
  ok = true; i = 0;
  while (i < D && ok) {
    ok = ok && (s[ind1][l1 + i] == s[ind2][l2 + i]);
    i++;
  }
  return ok;
}
      

bool BFS() {
  int first, last, ind, d;
  Node u;
  bool found;

  memset(mark, false, sizeof(mark));
  first = 0; last = 0;
  for (int i = 0; i < n; i++) {
    last++;
    Q[last] = Node(i, len[i]);
    mark[i][len[i]] = true;
  }
  found = false;

  while (first < last && !found) {
    first++;
    u = Q[first];
    for (int i = 0; i < n; i++) {
      if (len[i] <= u.d) {
        ind = u.ind; d = u.d - len[i];
      } 
      else {
        ind = i; d = len[i] - u.d;
      }
      if (!mark[ind][d])
        if (match(u.ind, u.d, i)) {
          last++;
          Q[last] = Node(ind, d);
          mark[ind][d] = true;
          if (d == 0) found = true;
        }
    }
  }
  return found;
}


void solve(int testNum) {
  makeHash();
  sol[testNum] = BFS();
}

int main() {

  FILE* inFile = fopen("recnik.in", "r");
  FILE* outFile = fopen("recnik.out", "w");

  fscanf(inFile, "%d", &T);
  int max = 0;
  for (int i = 0; i < T; i++) {
    fscanf(inFile, "%d", &n);
    for (int j = 0; j < n; j++) {
      fscanf(inFile, "%s", s[j]);
      len[j] = strlen(s[j]);
      if (len [j] > max)
        max = len [j];
    }
    makeHash();
    sol[i] = BFS();
  }

  for (int i = 0; i < T; i++) {
    if (sol[i]) fprintf(outFile, "dvosmislen\n");
    else fprintf(outFile, "nedvosmislen\n");
  }

  fclose(inFile);
  fclose(outFile);
  return 0;
}