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
#include<cstdio>
#include<cassert>
#include<cstring>
#include<algorithm>
#include<queue>
#include<bitset>
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)
#define foreach(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define all(c) (c).begin(),(c).end()
#define scanf(...) scanf(__VA_ARGS__)?:0
#define e1 first
#define e2 second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int n,m,x,korzen,p[1001],nr[1001],odw[1001],ls[1001],cl[1001],ojc[1001],ws[1001][1001],a[10001],b[10001];
char t[10001];
vector<int> v[1001],vr[1001];
bitset<1001> pot[1001];
void dfssort(int a)
{
	odw[a]=1;
	foreach(it,v[a]) if (!odw[*it]) dfssort(*it);
	nr[a]=x--; ls[nr[a]]=a;
}
vector<int> vs[1001];
int u,odw2[1001],pre[1001],post[1001];
int dfs(int a)
{
	odw2[a]=1;
	pre[a]=u++;
	int ret=1;
	foreach(it,vs[a]) assert(!odw2[*it]),ret+=dfs(*it);
	post[a]=u++;
	return ret;
}
bool przodek(int a,int b)
{
	return pre[a]<pre[b] && post[b]<post[a];
}
void check()
{
	assert(korzen!=0);
	assert(ojc[korzen]==0);
	FOR(i,1,n) vs[ojc[i]].push_back(i);
	assert(dfs(korzen)==n);
	FOR(i,1,m)
		/*if (t[i]=='T'){ if (!przodek(b[i],a[i]))
			{
			printf("assert %d (%d-%d) %d (%d-%d) ",b[i],pre[b[i]],post[b[i]],a[i],pre[a[i]],post[a[i]]);
			if (nr[b[i]]<=nr[a[i]]) puts("popr");
			else puts("zle");
		}
		}*/
		if (t[i]=='T') printf("%d %d %d\n",b[i],a[i],przodek(b[i],a[i]));//,assert(przodek(b[i],a[i]));
		else assert(!przodek(b[i],a[i]));
}
int main()
{
	scanf("%d%d",&n,&m);
	FOR(i,1,m)
	{
		scanf("%d%d %c",&a[i],&b[i],&t[i]);
		if (t[i]=='T') p[a[i]]=1,v[b[i]].push_back(a[i]),vr[a[i]].push_back(b[i]);
		else p[b[i]]=1;
	}
	FOR(i,1,n) if (!p[i]){ korzen=i; break; }
	if (!korzen) puts("NIE"),exit(0);
	FOR(i,1,n) if (i!=korzen) v[korzen].push_back(i),vr[i].push_back(korzen);
	x=n; dfssort(korzen);
	FOR(i,1,n) foreach(it,v[i]) if (nr[*it]<nr[i]) puts("NIE"),exit(0);
	FORD(i,n,1)
	{
		pot[ls[i]][ls[i]]=true;
		foreach(it,v[ls[i]]) pot[ls[i]]|=pot[*it];
	}
	FOR(i,1,n) FOR(j,1,n) ws[i][j]=(pot[i]&pot[j]).any();
	//printf("    "); FOR(i,1,n) printf("%d ",i); puts("");
	//FOR(i,1,n){ printf("%d | ",i); FOR(j,1,n) printf("%d ",(int)pot[i][j]); puts(""); }
	//puts("");
	//FOR(i,1,n){ printf("%d | ",i); FOR(j,1,n) printf("%d ",(int)ws[i][j]); puts(""); }
	FOR(i,1,m) if (t[i]=='N') FOR(j,1,n) if (j!=b[i] && pot[j][a[i]] && ws[b[i]][j] && !pot[j][b[i]]) v[j].push_back(b[i]),vr[b[i]].push_back(j);
	memset(nr+1,0,sizeof(int)*n);
	memset(odw+1,0,sizeof(int)*n);
	x=n; dfssort(korzen);
	FOR(i,1,n) foreach(it,v[i]) if (nr[*it]<nr[i]) puts("NIE"),exit(0);
	FOR(i,1,n) pot[i].reset();
	FORD(i,n,1)
	{
		pot[ls[i]][ls[i]]=true;
		foreach(it,v[ls[i]]) pot[ls[i]]|=pot[*it];
	}
	//FOR(i,1,n) FOR(j,1,n) assert(ws[i][j]==(pot[i]&pot[j]).any());
	FOR(i,1,n) FOR(j,1,n) FOR(k,1,n) ws[j][k]|=ws[i][j]&ws[i][k];
	FOR(i,2,n) FORD(j,i-1,1) if (ws[ls[j]][ls[i]]){ ojc[ls[i]]=ls[j]; break; }
	//FOR(i,1,n) printf("%d-%d ",i,ojc[i]); puts("");
	//puts("");
	//FOR(i,1,n) printf("%d ",ls[i]); puts("");
	//FOR(i,1,n) assert(ls[nr[i]]==i);
	/*FOR(i,2,n) if (!v[i].empty()) { printf("%d: ",i); foreach(it,v[i]) printf("%d ",*it); puts(""); }
	FOR(i,1,n){ FOR(j,1,n) printf("%d ",ws[i][j]); puts(""); }
	printf("%d %d %d\n",ws[2][4],ws[4][6],ws[6][2]);
	FOR(i,1,n) printf("%d ",ls[i]); puts("");
	FOR(i,1,n) printf("%d-%d ",i,nr[i]); puts("");
	FOR(i,1,n) printf("%d-%d ",i,ojc[i]); puts("");
	check();*/
	FOR(i,1,n) printf("%d\n",ojc[i]);
	//puts("TAK");
}