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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <vector>
using namespace std;


#define MAXN 1007

vector <int> bosses[MAXN], workers[MAXN], notbosses[MAXN], notworkers[MAXN];


bool exists_path(int x, int y, int *res) {
  while (x != y && x != 0) {
    x = res[x];
  }
  return x == y;
}

bool dfs(int *res, int *vis, int root, int color) {
  if (root == 0)
    return false;
  else if (vis[root] == 0) {
    vis[root] = color;
    bool b = dfs(res, vis, res[root], color);
    if (b)
      return true;
  }
  else if (vis[root] == color)
    return true;
  return false;
}

bool cycle(int n, int *res) {
  int vis[MAXN] = {0};
  for (int root = 1; root <= n; root++) {
    bool b = dfs(res, vis, root, root);
    if (b)
      return true;
  }
  return false;
}

bool check_res(int n, int *res, int dir) {
  if (cycle(n, res))
    return false;
  for (int x = 1; x <= n; x++) {
    for (int j = 0; j < bosses[x].size(); j++) {
      bool b = exists_path(x, bosses[x][j], res);
      if (!b)
        return false;
    }
  }
  for (int x = 1; x <= n; x++) {
    for (int j = 0; j < notbosses[x].size(); j++) {
      bool b = exists_path(x, notbosses[x][j], res);
      if (b)
        return false;
    }
  }
  return true;
}


void print_res(int n, int *res, int dir) {
  for (int i = 1; i <= n; i++)
    printf("%d\n", res[i]);
}


bool check(int n, int *res, int dir, int last) {
  if (last < n) {
    if (last + 1 == dir) {
      bool b = check(n, res, dir, last + 1);
      if (b)
        return true;
    }
    else {
      for (int i = 1; i <= n; i++) {
        res[last + 1] = i;
        bool b = check(n, res, dir, last + 1);
        if (b)
          return true;
      }
    }
    return false;
  }
  else { // last == n
    bool b = check_res(n, res, dir);
    if (b) {
      print_res(n, res, dir);
      return true;
    }
    return false;
  }
}


int main() {
  ios_base :: sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  while (m--) {
    int a, b;
    char c;
    cin >> a >> b >> c;
    if (c == 'T') { // b boss of a
      bosses[a].push_back(b);
      workers[b].push_back(a);
    }
    else {
      notbosses[a].push_back(b);
      notworkers[b].push_back(a);
    }
  }
  int b = false;
  for (int dir = 1; dir <= n; dir++) {
    int res[MAXN] = {0}; //probably not allowed here
    res[dir] = 0;
    b = check(n, res, dir, 0); // last parameter - last filled position
    if (b)
      return 0;
  }
  if (!b)
    cout << "NIE";
  return 0;
}