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
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1002;
int P[N][N];
vector<int> G[N];
int odw[N], oj[N];
int n, i, m, a, b, j, l;
char c;
void dfs(int v){
	odw[v] = 1;
	//cout << v <<" ";
	l++;
	for(int i = 0; i < G[v].size(); ++i)
		if(odw[G[v][i]] == 0) {
			oj[G[v][i]]  = v;
			dfs(G[v][i]);
		}
	
}
void wypisz(){
	for(int i = 1; i <= n; ++i) cout <<oj[i] << endl;
}
void wypiszgraf(){
	for(int i = 1; i <= n; ++i) {
		cout << i <<": ";
		for(int j = 0; j < G[i].size(); ++j) cout << G[i][j] <<" ";
		cout << endl;
	}
}
int main()
{
ios_base::sync_with_stdio(0);
cin >> n >> m;
	
for(i = 0; i < m; ++i){
	cin >> a >> b >> c;
	if(c == 'N') P[b][a] = 1; //nie
}
for(i = 1; i <= n; ++i) 
	for(j = 1; j <= n; ++j) if(P[i][j] == 0 && i != j) G[i].push_back(j);
//wypiszgraf();	
for(j = 1; j <= n; ++j)
	{
	l = 0;	
	for(i = 1; i <= n; ++i) odw[i] = oj[i] = 0;	
	dfs(j);
	if(l == n) {
		wypisz();
		break;
		}
	}
if(j == n + 1) cout <<"NIE";
return 0; 
}