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
//Aleksander Łukasiewicz
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1000;

#define pb push_back
#define mp make_pair

int n, m;
int tree[MAXN + 3], sets[MAXN + 3];
vector< pair< pair<int,int>, char > > edges;

int Find(int x){
	if(sets[x] == x)
		return x;
	return sets[x] = Find(sets[x]);
}

void Union(int x, int y){
	int fx = Find(x);
	int fy = Find(y);
	sets[fx] = fy;
}

bool isParent(int son, int parent){
	while(son != 0){
		if(son == parent) return true;
		son = tree[son];
	}
	
	return false;
}

bool Connectivity(){
	for(int i=1; i<=n; i++)
		sets[i] = i;
	for(int i=1; i<=n; i++)
		Union(i, tree[i]);
	for(int i=1; i<=n; i++)
		if(Find(i) != Find(1))
			return false;
	return true;
}

bool Check(){
	if(!Connectivity())
		return false;
	for(auto E : edges){
		if(E.second == 'T'){
			if(!isParent(E.first.first, E.first.second))
				return false;
		}
		else{
			if(isParent(E.first.first, E.first.second))
				return false;
		}
	}
	
	return true;
}

bool Generate(int ind){
	if(ind == n+1){
		for(int i=1; i<=n; i++){
			int tmp = tree[i];
			tree[i] = 0;
			bool cand = Check();
			if(cand)
				return true;
			tree[i] = tmp;
		}
		
		return false;
	}
	else{
		for(int i=1; i<=n; i++)
			if(i!=ind){
				tree[ind] = i;
				bool cand = Generate(ind+1);
				if(cand)
					return true;
			}
		return false;
	}
}

int main(){
	scanf("%d %d", &n, &m);
	for(int i=0; i<m; i++){
		int a, b;
		char c;
		scanf("%d %d %c", &a, &b, &c);
		edges.pb(mp(mp(a, b), c));
	}
	
	bool ans = Generate(1);
	if(!ans)
		puts("NIE");
	else
		for(int i=1; i<=n; i++)
			printf("%d\n", tree[i]);

return 0;
}