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
#include<bits/stdc++.h>
using namespace std;
vector<int> kraw[1001];
vector<int> nie[1001], tak[1001];
vector<int> pom;
int wyn[1001], zle[1001], czy=1;
char s[3];
int ile=0;
int odw[1001];
void dfs(int x, int il)
{
	odw[x]=0;
	pom.push_back(x);
	for(int i=0; i<int(kraw[x].size()); i++)
		if(odw[kraw[x][i]]==il)
			dfs(kraw[x][i], il);
}
void licz(vector<int> w, int ojc)
{
//	printf("%d\n", ojc);
	if(w.size()==0)
		return;
	ile++;
	int ojciec=0;
	for(int i=0; i<int(w.size()); i++)
	{
		for(int j=0; j<int(nie[w[i]].size()); j++)
			zle[nie[w[i]][j]]=ile;
	}
	for(int i=0; i<int(w.size()); i++)
		odw[w[i]]=ile;
	for(int i=0; i<int(w.size()); i++)
	{
		for(int j=0; j<int(tak[w[i]].size()); j++)
			if(odw[tak[w[i]][j]]==ile)
				zle[w[i]]=ile;
	}
	for(int i=0; i<int(w.size()); i++)
		if(zle[w[i]]!=ile)
			ojciec=w[i];
	if(ojciec==0)
	{
		czy=0;
		return;
	}
	wyn[ojciec]=ojc;
	int il=ile;
	
	odw[ojciec]=0;
	for(int i=0; i<int(w.size()); i++)
	{
		if(odw[w[i]]==il)
		{
			pom.clear();
			dfs(w[i], il);
			licz(pom, ojciec);
		}
		if(czy==0)
			return;
	}
}
int main()
{
	int n,m;
	scanf("%d%d", &n, &m);
	for(int i=1; i<=m; i++)
	{
		int x,y;
		scanf("%d%d%s", &x, &y, s);
		if(s[0]=='T')
		{
			tak[x].push_back(y);
			kraw[x].push_back(y);
			kraw[y].push_back(x);
		}
		if(s[0]=='N')
			nie[x].push_back(y);
	}
	for(int i=1; i<=n; i++)
		pom.push_back(i);
	licz(pom, 0);
	if(czy==0)
		printf("NIE\n");
	else
		for(int i=1; i<=n; i++)
			printf("%d\n", wyn[i]);
}