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
#include <cstdio>
#include <cstring>
#include <vector>

const int N = 1000 + 10;

int n, m;

struct Edge {
  int x, y;
  Edge() {}
  Edge(int _x, int _y): x(_x), y(_y) {}
};

std::vector<Edge> tak, nie;

std::vector<int> adj[N];

int anc[N];

int find(int x) { return anc[x] == x ? x : (anc[x] = find(anc[x])); }

int ans[N], deg[N], pre[N];
bool flag[N];

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int a, b;
    char c;
    scanf("%d%d %c", &b, &a, &c);
    if (c == 'T') {
      adj[a].push_back(b);
      tak.push_back(Edge(a, b));
      ++deg[b];
    } else {
      nie.push_back(Edge(a, b));
      flag[a] = true;
    }
  }
  memset(ans, -1, sizeof ans);
  int r = 0;
  for (int i = 1; i <= n; ++i) if (!flag[i] && !deg[i]) r = i;
  if (!r) return puts("NIE"), 0;
  for (int i = 0; i < adj[r].size(); ++i) --deg[adj[r][i]];
  ans[r] = 0;
  for (int i = 1; i <= n; ++i) pre[i] = r;
  for (int i = n - 1; i--;) {
    for (int j = 1; j <= n; ++j) flag[anc[j] = j] = false;
    for (int j = 0; j < tak.size(); ++j) {
      int x = tak[j].x, y = tak[j].y;
      if (ans[x] == -1 && ans[y] == -1) anc[find(x)] = find(y);
    }
    for (int j = 0; j < nie.size(); ++j) {
      int x = nie[j].x, y = nie[j].y;
      if (ans[y] == -1 && find(x) == find(y)) flag[x] = true;
    }
    int p = 0;
    for (int j = 1; j <= n; ++j) if (ans[j] == -1 && !flag[j] && !deg[j]) p = j;
    if (!p) return puts("NIE"), 0;
    ans[p] = pre[p];
    for (int j = 0; j < adj[p].size(); ++j) --deg[adj[p][j]];
    for (int j = 1; j <= n; ++j) if (find(j) == find(p)) pre[j] = p;
  }
  for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
  return 0;
}