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
#include<iostream>
#include<vector>
#include<queue>

using namespace std;

class gosc {
	vector<int> tak, nie, chca, nchca;
	bool dyr = false;
	bool odw1 = false;
	int chce_go;
	int szef = -1;
	int level = -1;
};

int main() {
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<gosc> V(n+1);
	for (int i = 0; i < m; i++) {
		int a, b;
		char c;
		cin >> a >> b >> c;
		if (c == 'T') {
			//V[a].tak.push_back(b);
			//V[b].chca.push_back(a);
		} else {
			//V[a].nie.push_back(b);
			//V[b].nchca.push_back(a);
		}
	}/*
	bool dyr = false;
	queue<int> Q; int przewinieci = 0;
	
	for (int i = 0; i < n; i++) {
		if (V[i].tak.empty() && V[i].nchca.empty()) {
			V[i].dyr = true;
			dyr = true;
		}
		if (V[i].chca.empty()) {
			Q.push(i);
		}
		V[i].chce_go = V[i].chca.size();
	}
	if (!dyr || Q.empty()) {
		cout << "NIE\n";
		return 0;
	}
	//bool cykl = false;
	while (!Q.empty()) {
		int g = Q.front();
		Q.pop();
		queue<int> q;
		q.push(g);
		V[g].odw1 = true;
		while (!q.empty()) {
			g = q.front();
			q.pop();
			for (auto x : V[g].tak) {
				V[x].chce_go--;
				if (V[x].chce_go == 0) {
					V[x].odw1 = true;
					q.push(x);
				}
			}
			for (auto x : V[g].nie) {
				if (V[x].odw1) {
					V[x].tak.push_back(g);
					V[g].chca.push_back(x);
				}
			}
		}
	}
	
	for (int i = 0; i < n; i++) {
		if (!V[i].odw1) {
			cout << "NIE\n";
			return 0;
		}
		if (V[i].chca.empty()) {
			Q.push(i);
		}
		V[i].chce_go = V[i].chca.size();
		V[i].odw1 = false;
	}
	while (!Q.empty()) {
		int g = Q.front();
		Q.pop();
		
		queue<int> q;
		q.push(g);
		V[g].odw1 = true;
		V[g].level = 0;
		while (!q.empty()) {
			g = q.front();
			q.pop();
			for (auto x : V[g].tak) {
				V[x].chce_go--;
				if (V[x].chce_go == 0) {
					V[x].odw1 = true;
					V[x].level = V[g].level + 1;
					q.push(x);
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		if (!V[i].odw1) {
			cout << "NIE\n";
			return 0;
		}
		if (V[i].chca.empty()) {
			Q.push(i);
		}
		V[i].chce_go = V[i].chca.size();
		V[i].odw1 = false;
	}*/
	cout << "NIE\n";
	
}