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
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> Pii;
int n, m;
int Ans[1100];
int P[1100];
bool B[1100]; //czy może być szefem
stack<Pii> Sym[1100];
stack<Pii> Anty[1100];
stack<int> Num[1100];
int Find(int x)
{
	if(P[x] == x) return x;
	else return P[x] = Find(P[x]);
}
void Union(int a, int b)
{
	P[Find(a)] = Find(b);
}
template<typename T>
void tolist(stack<T>& s, list<T>& d)
{
	while(!s.empty())
	{
		d.push_back(s.top());
		s.pop();
	}
}
void solve(int boss, list<int>& numery, list<Pii>& sympatie, list<Pii>& antypatie) 
{
	if(numery.size() == 0) return;
	if(numery.size() == 1)
	{
		Ans[numery.front()] = boss;
		return;
	}
	for(int x : numery)
		B[x] = true;
	for(Pii para : antypatie)
		B[para.second] = false;
	for(Pii para : sympatie)
		B[para.first] = false;
	int nboss = -1;
	for(int x : numery)
		if(B[x] == true)
			nboss = x;
	if(nboss == -1)
	{
		puts("NIE");
		exit(0);
	}
	Ans[nboss] = boss;
	for(int x : numery)
		P[x] = x;
	
	for(Pii para : sympatie)
		if(para.second != nboss)
			Union(para.first, para.second);
	for(Pii para : sympatie)
		if(nboss != para.second)
			Sym[Find(para.first)].push(para);
	for(Pii para : antypatie)
		if(Find(para.first) == Find(para.second) && para.first != nboss)
			Anty[Find(para.first)].push(para);
	for(int x : numery)
		if(x != nboss)
			Num[Find(x)].push(x);
	for(int x : numery)
		if(P[x] == x && x != nboss)
		{
			list<Pii> Smp;
			list<int> Numy;
			list<Pii> Antyp;
			tolist(Sym[x], Smp);
			tolist(Anty[x], Antyp);
			tolist(Num[x], Numy);
			solve(nboss, Numy, Smp, Antyp);
		}
}
int main()
{
	scanf("%d%d", &n, &m);
	list<int> L;
	list<Pii> S;
	list<Pii> A;
	char in[20];
	int a, b;
	for(int i = 0; i < m; ++i)
	{
		scanf("%d%d%s", &a, &b, in);
		if(in[0] == 'T')
			S.push_back(Pii(a,b));
		else
			A.push_back(Pii(a,b));
	}
	for(int i = 1; i <= n; ++i)
		L.push_back(i);
	solve(0, L, S, A);

	for(int i = 1; i <= n; ++i)
		printf("%d\n", Ans[i]);
	return 0;
}