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
130
131
132
133
134
135
#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define FORW(i,a,b) for(int i = (a); i < (b); ++i)
#define SIZE(X) (int)(X).size()

using namespace std;

typedef pair<int,int> edge;

template<typename T>
ostream& operator<< (ostream& os, const vector<T> &X) {
	os << "<"; for(T x : X) os << x << " "; os << ">";
	return os;
}

template<typename A, typename B>
ostream& operator<< (ostream& os, const pair<A,B> &P) {
	os << "(" << P.first << " " << P.second << ")";
	return os;
}

int ans[1010];
int D[1010], cnt;

int kan(vector<edge> &T, vector<edge> &N, vector<int> &A) {
	cnt++;
	for(edge t : T) D[t.first] = cnt;
	for(edge n : N) D[n.second] = cnt;
	for(int a : A) if(D[a] != cnt) return a;
	return -1;
}

int O[1010], ooo;

vector<int> G[1010];
int SK[1010];

void dfs(int a, vector<int> &R) {
	O[a] = ooo;
	R.push_back(a);
	for(int g : G[a]) if(O[g] != ooo) dfs(g,R);
}

template<typename T>
void CV(vector<T> &V) {
	vector<T> X;
	swap(X,V);
}

void go(vector<edge> &T, vector<edge> &N, vector<int> &A, int f, int cnt = 0) {
	if(A.size() == 1) {
		ans[A[0]] = f;
		return;
	}
	int k = kan(T,N,A);
	if(k == -1) {
		printf("NIE\n");
		exit(0);
	}
	ooo++;
	ans[k] = f;
	O[k] = ooo;
	vector<vector<int>> V;
	vector<vector<edge>> TT;
	vector<vector<edge>> NN;
	for(int a : A) G[a].clear();
	for(edge e : T) {
		G[e.first].push_back(e.second);
		G[e.second].push_back(e.first);
	}
	for(int a : A) {
		if(O[a] != ooo){
			vector<int> tmp;
			dfs(a,tmp);
			V.push_back(tmp);
			TT.push_back({});
			for(int t : tmp) SK[t] = NN.size();
			NN.push_back({});
		}
	}
	SK[k] = NN.size();
	for(edge t : T) {
		assert(SK[t.first] == SK[t.second] or t.first == k or t.second == k);
		//cout << SK[t.first] << " " << SIZE(TT) << endl;
		if(SK[t.first] == SK[t.second]) TT[SK[t.first]].push_back(t);
	}
	for(edge n : N) {
		if(SK[n.first] == SK[n.second]) NN[SK[n.second]].push_back(n);
	}
	FORW(i,0,SIZE(V)) go(TT[i],NN[i],V[i],k,cnt+1);
}

int main() {
	int n,m;
	scanf("%d%d",&n,&m);
	vector<edge> T,N;
	vector<int> A;
	FOR(i,1,n) A.push_back(i);
	FOR(i,1,m) {
		 int a,b;
		 char c;
		 scanf("%d%d %c",&a,&b,&c);
		 if(c == 'T') {
		 	T.push_back(edge(a,b));
		 	G[a].push_back(b);
		 	G[b].push_back(a);
		 }
		 else N.push_back(edge(a,b));
	}
	go(T,N,A,0);	
	FOR(i,1,n) {
		vector<int> mn, mt;
		for(edge t : T) if(t.first == i) mt.push_back(t.second);
		for(edge t : N) if(t.first == i) mn.push_back(t.second);
		set<int> S;
		int ii = i;
		while(ii) {S.insert(ii); ii = ans[ii];}
		for(int t : mt) assert(S.find(t) != S.end());
		for(int nn : mn) {
			if(S.find(nn) != S.end()){
				int iii = i;
				while(iii) {printf("%d ", iii); if(iii == 324) printf("ELO"); iii = ans[iii];} printf("\n");
				printf("%d %d N\n", i,nn);
			}
			assert(S.find(nn) == S.end());
		}
	}
	//printf("TAK\n");
	//return 0;
	FOR(i,1,n) {
		printf("%d\n", ans[i]);
	}
	return 0;
}