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

#define fru(j,n) for(int j=0; j<(n); ++j)
#define tr(it,v) for(auto it=(v).begin(); it!=(v).end(); ++it)
//#define tr(it,v) for(typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define x first
#define y second
#define pb push_back
#define ALL(G) (G).begin(),(G).end()

#if 1
	#define DEB printf
#else
	#define DEB(...)
#endif

typedef long long ll;
typedef long long LL;
typedef double D;
typedef pair<int,int> pii;
typedef vector<int> vi;

const int inft = 1000000009;
const int mod = 1000000007;
const int MAXN = 1003;

int n,m,ans[MAXN],odw[MAXN],forb[MAXN],vis[MAXN],NR;
vi V[MAXN],VT[MAXN],N[MAXN],NT[MAXN];

void dfs(int v,vi &T){
	if(vis[v]==NR)return;
	vis[v]=NR;
	T.pb(v);
	tr(it,VT[v])if(!odw[*it])dfs(*it,T);
}
void get(int v,int root){
	//get all in curr place
	if(odw[v])return;
	NR++;
	vi T;
	dfs(v,T);
	//fill forb
	NR++;
	tr(it,T)tr(it2,V[*it])if(!odw[*it2]){vis[*it]=NR;break;}
	tr(it,T)tr(it2,N[*it])vis[*it2]=NR;
	int root2=-1;
	tr(it,T)if(vis[*it]!=NR)root2=*it;
	if(root2==-1){puts("NIE");exit(0);}
	odw[root2]=1;ans[root2]=root;
	tr(it,T)get(*it,root2);
}

int TT[MAXN],in[MAXN],out[MAXN],tim;
vi TR[MAXN];
void Tdfs(int v){
	tim++;
	in[v]=tim;
	tr(it,TR[v])Tdfs(*it);
	out[v]=tim;
}
bool anc(int a,int b){
	return in[b]<=in[a] && out[b]>=out[a];
}
void check(){
	int root=-1;
	fru(i,n)if(ans[i]!=-1)TR[ans[i]].pb(i);else root=i;
	fru(i,n)in[i]=-1;
	assert(root!=-1);
	Tdfs(root);
	fru(i,n)assert(in[i]!=-1);
	fru(i,n)tr(it,V[i])assert(anc(i,*it));
	fru(i,n)tr(it,N[i])assert(!anc(i,*it));
}

void solve() {
	scanf("%d%d",&n,&m);
	fru(i,m){
		int a,b;
		char c;
		scanf("%d%d %c",&a,&b,&c);a--;b--;
		if(c=='T'){V[a].pb(b);VT[a].pb(b);VT[b].pb(a);}
		else {N[a].pb(b);NT[b].pb(a);}
	}
	int root=-1;
	fru(i,n)if(V[i].empty() && NT[i].empty())root=i;
	if(root==-1){puts("NIE");exit(0);}
	ans[root]=-1;odw[root]=1;
	NR=0;
	fru(i,n)get(i,root);
//	printf("TAK\n");
	fru(i,n)printf("%d\n",ans[i]+1);
//	check();
}

int main() {
	int te = 1;
//	scanf("%d",&te);
	fru(ti,te) solve();
	return 0;
}