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
#include <cstdio>
#include <vector>

#define REP(i,n) for(int i=0; i<n; i++)
#define FOR(i,b,e) for(int i=b; i<=e; i++)
#define FORD(i,b,e) for(int i=b; i>=e; i--)
#define PB push_back
using namespace std;

typedef vector <int> VI;
typedef vector < VI > VVI;
typedef pair<int, int> PII;

VVI G, TRANS, NO, GU;

int partID;
int out[10009], no[10009], part[10009], parent[10009];

void dfs(int s, int p){
	if(part[s] != -1 || parent[s] != -2) return;
	part[s] = p;
	REP(i, GU[s].size()){
		dfs(GU[s][i], p);
	}
	return;
}

bool partition(VI & nodes){
	partID = 0;
	REP(i,nodes.size()) part[nodes[i]] = -1;

	REP(i,nodes.size()){
		if(part[nodes[i]] == -1 && parent[nodes[i]] == -2){
			dfs(nodes[i],partID);
			partID++;
		}
	}
}

int getBoss(VI & nodes){
	REP(i, nodes.size()) no[nodes[i]] = 0;
	REP(i, nodes.size()) REP(j, NO[nodes[i]].size()) no[ NO[nodes[i]][j] ]++;
	
	REP(i, nodes.size()){
		if(out[nodes[i]] == 0 && no[nodes[i]] == 0) return nodes[i];
	}
	return -1;
}

int fix(int node, int par){
	REP(i, TRANS[node].size()){
		out[TRANS[node][i]]--;
	}
	part[node] = -1;
	parent[node] = par;
}

bool process(VI& nodes, int root){
	int ceo = getBoss(nodes);
	if(ceo == -1) return false;
	fix(ceo, root);
	
	if(nodes.size() == 1){
		return true;
	}
	partition(nodes);

	VVI parts;
	parts.resize(partID);
	REP(i,nodes.size()){
		if(nodes[i]==ceo) continue;
		parts[part[nodes[i]]].PB(nodes[i]);
	}
	
	REP(i, parts.size()){
		if( !process(parts[i], ceo) ) return false;
	}
	return true;
}

int main(){
	int n,m,b,e;
	char c;
	scanf("%d %d", &n, &m);
	REP(i,n){
		parent[i] = -2;
		part[i] = -1;
	}
	G.resize(n); TRANS.resize(n); NO.resize(n); GU.resize(n);

	REP(i,m){
		scanf("%d %d %c", &b, &e, &c);
		b--; e--;
		if(c == 'T'){
			out[b]++;
			G[b].PB(e);
			GU[b].PB(e);
			GU[e].PB(b);
			TRANS[e].PB(b);
		}
		else{
			NO[b].PB(e);
			no[e]++;
		}
	}

	VI init;
	init.resize(n);
	REP(i,n) init[i] = i;
	if( ! process(init, -1) ){
		printf( "NIE\n");
	} else{
		REP(i,n){
			printf("%d\n", parent[i] + 1);
		}
	}
}