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
#include <cstdio>
#include <cstring>
#include <vector>

int N,M;
std::vector<int> supervisor[1010];
std::vector<int> bsupervisor[1010];
std::vector<int> enemy[1010];
int parent[1010];

void search(int node, const std::vector<bool> &isset, std::vector<int> &ngroup, int group) {
	ngroup[node]=group;
	for (unsigned i=0; i<bsupervisor[node].size(); ++i) {
		int child = bsupervisor[node][i];
		if (isset[child] && ngroup[child]==0) {
			search(child, isset, ngroup, group);
		}
	}
}

bool create(const std::vector<int> &nodes, int p) {
	std::vector<bool> disliked(N+1, false);
	std::vector<bool> likes(N+1, false);
	std::vector<bool> isset(N+1, false);
	std::vector<int> ngroup(N+1,0);
	std::vector<std::vector<int> > gnodes(nodes.size(), std::vector<int>());
	int root = 0;
	int group = 0;

	for (unsigned i=0; i<nodes.size(); ++i) {
		isset[nodes[i]] = true;
	}

	for (unsigned i=0; i<nodes.size(); ++i) {
		for (unsigned j=0; j<enemy[nodes[i]].size(); ++j) {
			disliked[enemy[nodes[i]][j]] = true;
		}

		for (unsigned j=0; j<supervisor[nodes[i]].size(); ++j) {
			if (isset[supervisor[nodes[i]][j]]) likes[nodes[i]] = true;
		}
	}

	for (unsigned i=0; i<nodes.size(); ++i) {
		if (disliked[nodes[i]] == false && likes[nodes[i]] == false) root = nodes[i];
	}

	if (root == 0) return false;
	isset[root] = false;
	parent[root] = p;

	//split
	for (unsigned i=0; i<nodes.size(); ++i) {
		if (ngroup[nodes[i]]==0 && nodes[i]!=root) {
			search(nodes[i],isset,ngroup,++group);
		}

		if (nodes[i]!=root) {
			gnodes[ngroup[nodes[i]]].push_back(nodes[i]);
		}
	}

	for (int i=1; i<=group; ++i) {
		if (create(gnodes[i], root) == false) return false;
	}

	return true;
}

int main() {
	std::vector<int> all;

	memset(parent,0,sizeof(parent));
	scanf("%d %d",&N,&M);

	for (int i=1; i<=N; ++i) {
		all.push_back(i);
	}
	
	for (int i=1; i<=M; ++i) {
		int a,b;
		char c;

		scanf("%d %d %c",&a,&b,&c);

		if (c=='T') {
			supervisor[a].push_back(b);
			bsupervisor[b].push_back(a);
			bsupervisor[a].push_back(b);
		} else {
			enemy[a].push_back(b);
		}
	}

	if (create(all,0)) {
		for (int i=1;i<=N;++i) {
			printf("%d\n",parent[i]);
		}
	} else {
		printf("NIE\n");
	}

	return 0;
}