1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
#include <iostream>
#include <vector>
using namespace std;

int n, m;
vector <int> wynik;
vector <pair <int, int> > T, N;
vector <vector <int> > parent;

int find_par(int lvl, int n) {
    if (n != parent[lvl][n])
        parent[lvl][n] = find_par(lvl, parent[lvl][n]);
    return parent[lvl][n];
}

void happy_union(int lvl, int a, int b) {
    parent[lvl][find_par(lvl, a)] = find_par(lvl, b);
    return;
}

bool rozwiaz(int lv, int ojc, int prze_dyr)
{
  int lv2 = lv + 1;
  //szukanie dyrektora
  vector <bool> dyr;
  dyr.resize(n+1, false);
  int nowy_dyrektor = -1;
  for (int i = 1; i <= n; i++)
    if (find_par(lv,i) == ojc)
      dyr[i] = true;

  for (int i = 0; i < T.size(); i++)
  {
    int a = T[i].first, b = T[i].second;
    if ((parent[lv][a] == ojc) && (parent[lv][a] == parent[lv][b]))
      dyr[a] = false;
  }

  for (int i = 0; i < N.size(); i++)
  {
    int a = N[i].first, b = N[i].second;
    if ((parent[lv][a] == ojc) && (parent[lv][a] == parent[lv][b]))
      dyr[b] = false;
  }
  for (int i = 1; i <= n; i++)
    if (dyr[i])
    {
      nowy_dyrektor = i;
      wynik[i] = prze_dyr;
      break;
    }
  if (nowy_dyrektor == -1){
    return false;
  }

  //tworzenie workow
  for (int i = 0; i < T.size(); i++)
  {
    int a = T[i].first, b = T[i].second;
    if ((b != nowy_dyrektor) && (find_par(lv, a) == ojc) && (find_par(lv, a) == find_par(lv, b)))
      happy_union(lv2, a, b);
  }

  //wywolania rekurencyjne
  vector <bool> worek;
  worek.resize(n+1, false);
  for (int i = 1; i <= n; i++)
    if ((i != nowy_dyrektor) && (parent[lv][i] == ojc) && (!worek[find_par(lv2, i)])){
      worek[parent[lv2][i]] = true;
      if(!rozwiaz(lv2, parent[lv2][i], nowy_dyrektor))
        return false;
    }
  return true;
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin >> n >> m;
  wynik.resize(n+1);
  parent.resize(n+1);
  parent[0].resize(n+1, 0);
  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= n; j++)
      parent[i].push_back(j);
  for (int i = 0; i < m; i++)
  {
    int a, b;
    char c;
    cin >> a >> b >> c;
    if (c == 'T')
      T.push_back(make_pair(a, b));
    else
      N.push_back(make_pair(a, b));
  }

  if (rozwiaz(0, 0, 0))
    for (int i = 1; i <= n; i++)
      cout << wynik[i] << endl;
  else
    cout << "NIE";
  return 0;
}