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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	
	vector<char> topo(n+1);
	vector<unordered_set<int>> strong_out(n+1), strong_in(n+1), weak_out(n+1), weak_in(n+1);
	vector<vector<bool>> transistive_inferiors(n+1, vector<bool>(n+1));
	vector<int> parents(n+1);
	
	while (m--) {
		int a, b;
		string s;
		cin >> a >> b >> s;
		if (s == "N") {
			weak_out[a].insert(b);
			weak_in[b].insert(a);
		} else {
			strong_out[b].insert(a);
			strong_in[a].insert(b);
		}		
	}
	
	int director = 0;
	for (int i = 1; i <= n; ++i) {
		if (weak_in[i].empty() && strong_in[i].empty()) {
			director = i;
			break;
		}
	}
	
	//cerr << "Director = " << director << endl;
	if (director == 0) {
		cout << "NIE" << endl;
		return 0;
	}
	
	for (int i = 1; i <= n; ++i) {
		if (i == director) continue;
		strong_in[i].insert(director);
		strong_out[director].insert(i);
	}
	
	vector<int> parent(n+1);
	vector<bool> processed(n+1);
	
	for (int z = 0; z<n; ++z) {
		//cerr << "Next round." << endl;
		
		vector<int> component(n+1);
		vector<vector<int>> components(1);
		int component_id = 0;
		
		for (int i = 1; i <= n; ++i) {
			if (processed[i] || component[i]!=0) continue;
			
			component_id++;
			components.emplace_back();
			queue<int> q;
			q.push(i);
			
			while(!q.empty()) {
				int a = q.front(); q.pop();
				component[a] = component_id;
				components[component_id].push_back(a);
				
				for (int b : strong_in[a]) {
					if (!processed[b] && component[b]==0) {
						q.push(b);
						component[b] = component_id;
					}
				}
				for (int b : strong_out[a]) {
					if (!processed[b] && component[b]==0) {
						q.push(b);
						component[b] = component_id;
					}
				}
			}
		}
		
		for (int c = 1; c <= component_id; ++c) {
			//cerr << "Component " << c << endl;
			int director = 0;
			for (int a : components[c]) {
				//cerr << a << ", ";
				bool empty = true;
				for (int x : strong_in[a])
					if (component[x] == component[a])
						empty = false;
				for (int x : weak_in[a])
					if (component[x] == component[a])
						empty = false;
						
				if (empty)
					director = a;
			}
			//cerr << endl;
			//cerr << "Director = " << director << endl;
			
			if (director == 0) {
				cout << "NIE" << endl;
				return 0;
			}
			
			for (int b : weak_out[director])
				weak_in[b].erase(director);
			for (int b : strong_out[director])
				strong_in[b].erase(director);
			weak_out[director].clear();
			strong_out[director].clear();
			
			processed[director] = true;
			
			for (int a : components[c]) {
				if (a!= director)
					parent[a] = director;
			}
		}
	}
	
	for (int i = 1; i<=n; ++i)
		cout << parent[i] << endl;
	
	//cout << "TAK" << endl;
}