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
#include <bits/stdc++.h>

using namespace std;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug{
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(c) { ris; }
#endif
};
#define imie(x) " [" << #x ": " << (x) << "] "

const int N = 1005;
vector<pair<pair<int,int>, bool>> edges;
int group[N], parent[N];
vector<int> members[N];
bool isRoot[N];
bool FAIL;
void uni(int a, int b) {
	a = group[a], b = group[b];
	if(a == b) return;
	if(members[a].size() > members[b].size()) swap(a, b);
	for(int i : members[a]) {
		group[i] = b;
		members[b].push_back(i);
	}
	members[a].clear();
}
void solve(const vector<int> & vertices, const int lastRoot) {
	// debug() << imie(vertices);
	if(vertices.empty()) return;
	for(int i : vertices) {
		group[i] = i;
		members[i].push_back(i);
		isRoot[i] = true;
	}
	if(lastRoot == 0) // there must be only one group in the first iteration
		for(int i : vertices)
			uni(i, vertices[0]);
	for(int rep = 0; rep < 2; ++rep) {
		for(auto & edge : edges) {
			int a = edge.first.first, b = edge.first.second;
			if(!group[a] || !group[b]) continue;
			bool type = edge.second;
			if(rep == 0 && type) {
				isRoot[a] = false;
				uni(a, b);
			}
			if(rep == 1 && !type && group[a] == group[b]) {
				isRoot[b] = false;
			}
		}
	}
	for(int i : vertices) group[i] = 0;
	for(int i : vertices) if(!members[i].empty()) {
		int root = -1;
		for(int j : members[i]) if(isRoot[j]) root = j;
		if(root == -1) {
			// debug() << "FAIL";
			FAIL = true;
			break;
		}
		parent[root] = lastRoot;
		vector<int> remaining;
		for(int j : members[i]) if(j != root) remaining.push_back(j);
		members[i].clear();
		solve(remaining, root);
	}
}
void te() {
	int n, m;
	scanf("%d%d", &n, &m);
	while(m--) {
		int a, b;
		char ch;
		scanf("%d %d %c", &a, &b, &ch);
		edges.push_back({{a,b}, ch == 'T'});
	}
	vector<int> vertices;
	for(int i = 1; i <= n; ++i) vertices.push_back(i);
	solve(vertices, 0);
	if(FAIL) puts("NIE");
	else for(int i = 1; i <= n; ++i) printf("%d\n", parent[i]);
}
int main() {
	te();
}