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

const int N = 1003;
const int M = 10003;
int n, m, fa[N], anc[N], last[N];
int n1, u1[M], v1[M];
int n2, u2[M], v2[M];
bool bo[N];

inline int ufs(const int &u) {
  if (anc[u] == u) return u;
  return anc[u] = ufs(anc[u]);
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int a, b;
    char c;
    scanf("%d%d %c", &a, &b, &c);
    if (c == 'T') {
      ++n1;
      u1[n1] = b, v1[n1] = a;
      bo[a] = true;
    } else {
      ++n2;
      u2[n2] = b, v2[n2] = a;
      bo[b] = true;
    }
  }
  
  int rt = -1;
  for (int i = 1; i <= n && !~rt; ++i)
    if (!bo[i]) rt = i;
  if (!~rt) {
    puts("NIE");
    return 0;
  }
  
  for (int i = 1; i <= n; ++i) fa[i] = -1;
  fa[rt] = 0;
  for (int i = 1; i <= n; ++i)
    if (i != rt) last[i] = rt;
  for (int t = n - 1; t; --t) {
    for (int i = 1; i <= n; ++i) {
      bo[i] = false;
      if (~fa[i]) bo[i] = true;
      anc[i] = i;
    }
    for (int i = 1; i <= n1; ++i) {
      int x = u1[i], y = v1[i];
      if (!~fa[x] && !~fa[y]) anc[ufs(x)] = ufs(y);
      if (!~fa[x]) bo[y] = true;
    }
    for (int i = 1; i <= n2; ++i) {
      int x = u2[i], y = v2[i];
      if (ufs(x) == ufs(y)) bo[x] = true;
    }
    rt = -1;
    for (int i = 1; i <= n && !~rt; ++i)
      if (!bo[i]) rt = i;
    if (!~rt) {
      puts("NIE");
      return 0;
    }
    fa[rt] = last[rt];
    for (int i = 1; i <= n; ++i)
      if (!~fa[i] && ufs(i) == ufs(rt))
        last[i] = rt;
  }
  for (int i = 1; i <= n; ++i)
    printf("%d\n", fa[i]);
  return 0;
}