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
127
128
129
#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std;

namespace {

class Impossible {};

class Solver {
private:
  int n;
  vector<vector<int>> upper;
  vector<vector<int>> not_upper;
  vector<vector<int>> lower;
  vector<vector<int>> not_lower;

public:
  Solver(int n_): n{n_}, upper(n), not_upper(n), lower(n), not_lower(n)
  {
  }

  void request(int a, int b, bool wants)
  {
    if (wants) {
      upper[a].emplace_back(b);
      lower[b].emplace_back(a);
    } else {
      not_upper[a].emplace_back(b);
      not_lower[b].emplace_back(a);
    }
  }

  void dfs(int v, vector<int> const& parent, vector<int>& visited, int time, vector<int>& all) const
  {
    if (parent[v] >= 0) return;
    if (visited[v] == time) return;
    visited[v] = time;
    all.emplace_back(v);
    for (int w: upper[v]) dfs(w, parent, visited, time, all);
    for (int w: lower[v]) dfs(w, parent, visited, time, all);
  }

  vector<int> solve() const
  {
    vector<int> parent(n, -1);

    int root = -1;
    for (int v = 0; v < n; ++v) {
      if (!upper[v].empty()) continue;
      if (!not_lower[v].empty()) continue;
      root = v;
      break;
    }
    if (root < 0) throw Impossible{};

    vector<int> group(n, root);

    parent[root] = root;
    int done = 1;

    vector<int> visited(n, -1);
    int time = 0;

    while (done < n) {
      int start = time;
      for (int v = 0; v < n; ++v) {
        if (parent[v] >= 0) continue;
        if (visited[v] >= start) continue;

        vector<int> component;
        dfs(v, parent, visited, time, component);
        ++time;

        auto our_component = [&visited, v](int w) {
          return visited[w] == visited[v];
        };

        int r = -1;
        for (int w: component) {
          if (any_of(upper[w].begin(), upper[w].end(), our_component)) continue;
          if (any_of(not_lower[w].begin(), not_lower[w].end(), our_component)) continue;
          r = w;
          break;
        }
        if (r < 0) throw Impossible{};
        ++done;
        parent[r] = group[r];
        for (int w: component) group[w] = r;
      }
    }

    return parent;
  }
};

}

int main()
{
  iostream::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;

  Solver solver(n);

  for (int i = 0; i < m; ++i) {
    int a, b;
    char c;
    cin >> a >> b >> c;
    solver.request(a-1, b-1, c == 'T');
  }

  try {
    auto parent = solver.solve();
    for (int i = 0; i < n; ++i) {
      if (parent[i] == i) cout << "0\n";
      else cout << parent[i] + 1 << '\n';
    }
  } catch (Impossible&) {
    cout << "NIE\n";
    return 0;
  }

  return 0;
}