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
#include <bits/stdc++.h>
#define REP(a,b) for(int a=0; a<(b); ++a)
#define FWD(a,b,c) for(int a=(b); a<(c); ++a)
#define FWDS(a,b,c,d) for(int a=(b); a<(c); a+=d)
#define BCK(a,b,c) for(int a=(b); a>(c); --a)
#define ALL(a) (a).begin(), (a).end()
#define SIZE(a) ((int)(a).size())
#define VAR(x) #x ": " << x << " "
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define gcd __gcd
#define x first
#define y second
#define st first
#define nd second
#define pb push_back

using namespace std;

template<typename T> ostream& operator<<(ostream &out, const vector<T> &v){ out << "{"; for(const T &a : v) out << a << ", "; out << "}"; return out; }
template<typename S, typename T> ostream& operator<<(ostream &out, const pair<S,T> &p){ out << "(" << p.st << ", " << p.nd << ")"; return out; }

typedef long long LL;
typedef pair<int, int> PII;
typedef long double K;
typedef vector<int> VI;

const int dx[] = {0,0,-1,1}; //1,1,-1,1};
const int dy[] = {-1,1,0,0}; //1,-1,1,-1};

const int MAXN = 1010;

int n, m, k;
vector<int> anc[MAXN];
vector<int> out[MAXN];
vector<int> ban_anc[MAXN];

int parent[MAXN];
int col[MAXN];
bool ban[MAXN];

int oc, nc;
vector<int> new_nodes;
void recolor(int u){
	new_nodes.push_back(u);
	col[u] = nc;
	for(int v : out[u])
		if(col[v] == oc)
			recolor(v);
}

bool solve(int c, vector<int> nodes){
	for(int u : nodes) ban[u] = 0;
	for(int u : nodes)
		for(int v : ban_anc[u])
			ban[v] = 1;
	int r = -1;
	for(int u : nodes){
		if(!ban[u])
			for(int v : anc[u])
				if(col[v] == c){
					ban[u] = 1;
					break;
				}
		if(!ban[u]){
			r = u;
			break;
		}
	}
	if(r == -1) return 0;
	col[r] = ++k;
	for(int u : nodes) if(u != r) parent[u] = r;
	for(int u : nodes){
		if(col[u] == c){
			oc = c;
			nc = ++k;
			new_nodes.clear();
			recolor(u);
			if(!solve(nc, new_nodes)) return 0;
		}
	}
	return 1;
}

int main(){
	scanf("%d %d", &n, &m);
	FWD(i,1,n+1) new_nodes.push_back(i);
	FWD(i,0,m){
		int a, b;
		char c[3];
		scanf("%d %d %s", &a, &b, c);
		if(c[0] == 'T'){
			out[a].push_back(b);
			out[b].push_back(a);
			anc[a].push_back(b);
		}else{
			ban_anc[a].push_back(b);
		}
	}
	if(!solve(0, new_nodes)){
		printf("NIE\n");
	}else{
		#ifdef LOCAL_JUDGE
			printf("TAK\n");
			FWD(u,1,n+1){
				set<int> ca;
				int p = parent[u];
				while(p){
					ca.insert(p);
					p = parent[p];
				}
				for(int v : anc[u]) assert(ca.find(v) != ca.end());
				for(int v : ban_anc[u]) assert(ca.find(v) == ca.end());
			}
		#else
			FWD(u,1,n+1) printf("%d\n", parent[u]);
		#endif
	}
	return 0;
}