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 `#include #include #include #include #include using namespace std; #define NOPE do {printf("NIE\n"); exit(0);} while(0) const int MAX = 1000; int out[MAX]; vector N[MAX], T[MAX], R[MAX]; bool vis[MAX], inf[MAX]; vector f; int n; void dfs(int u) { vis[u] = true; f.push_back(u); for (int v : T[u]) { if (!vis[v]) { dfs(v); } } for (int v : R[u]) { if (!vis[v]) { dfs(v); } } } queue, int>> Q; void solve(vector v, int parent) { Q.push({move(v), parent}); while (!Q.empty()) { v = Q.front().first; parent = Q.front().second; Q.pop(); for (int i : v) { vis[i] = inf[i] = false; } for (int i : v) { for (int ind=0; ind<(int)T[i].size(); ind++) { if (T[i][ind] == parent) { T[i][ind] = T[i].back(); T[i].pop_back(); break; } } } for (int i : v) { if (vis[i]) { continue; } dfs(i); for (int u : f) { inf[u] = true; } int r = -1; for (int u : f) { if (all_of(T[u].begin(), T[u].end(), [](int t){return !inf[t];}) && all_of(N[u].begin(), N[u].end(), [](int t){return !inf[t]; })) { r = u; break; } } if (r == -1) { NOPE; } for (int u : f) { inf[u] = false; } out[r] = parent; f.erase(find(f.begin(), f.end(), r)); Q.push({move(f), r}); f = vector(); } } } int main() { int m; scanf("%d %d", &n, &m); while (m--) { int a, b; char c; scanf("%d %d %c", &a, &b, &c); a--, b--; if (c == 'T') { T[a].push_back(b); R[b].push_back(a); } else { N[b].push_back(a); } } int root = 0; while (root < n && !(T[root].empty() && N[root].empty())) root++; if (root == n) { NOPE; } out[root] = -1; vector v; v.reserve(n-1); for (int i=0; i