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
#include <stdio.h>
#include <set>
#include <algorithm>

#define MAX 1010

std::vector<int> vertexs[MAX];
std::set<int> notLike[MAX];
std::set<int> mustLike[MAX];
std::vector<int> sorted;

char visited[MAX];
int position[MAX];

void dfs(int n, int v)
{
	visited[v] = 1;
	for(int i : vertexs[v])
		if (visited[i] == 1)
		{
			printf("NIE\n");
			exit(0);
		}
		else if (visited[i] == 0)
			dfs(n, i);
	sorted.push_back(v);
	visited[v] = 2;
}

int main()
{
	int n, m, a, b;
	char c;
	scanf("%d %d", &n, &m);
	for (int i=0; i<m; ++i)
	{
		scanf("%d %d %c", &a, &b, &c);
		if (c == 'T')
		{
			vertexs[a].push_back(b);
			mustLike[a].insert(b);
		}
		else
			notLike[a].insert(b);
	}

	int startedVertex = 0;
	for (int i=1; i<=n; ++i)
	{
		bool ok = true;
		if (!mustLike[i].empty())
		{
			continue;
		}
		for (int j=1; j<=n; ++j)
		{
			if (i != j && notLike[j].count(i) != 0)
			{
				ok = false;
				break;
			}
		}
		if (ok)
		{
			startedVertex = i;
			break;
		}
	}

	if (startedVertex == 0)
	{
		printf("NIE\n");
		return 0;
	}

	dfs(n, startedVertex);
	for (int i=1; i<=n; ++i)
		if (i != startedVertex && visited[i] == 0)
			dfs(n, i);

	int p=0;
	for (int v : sorted)
	{
		position[v] = p++;
		for (int i : vertexs[v])
			for (int i2 : mustLike[i])
				mustLike[v].insert(i2);
		std::vector<int> diff;
		std::set_intersection(mustLike[v].begin(), mustLike[v].end(), notLike[v].begin(), notLike[v].end(), std::inserter(diff, diff.begin()));
		if (!diff.empty())
		{
			printf("NIE\n");
			return 0;
		}
	}

	position[sorted.front()] = MAX;
	for (int v=1; v<=n; ++v)
	{
		int minVertex = sorted.front();
		for (int i : vertexs[v])
			if (position[i] < position[minVertex])
				minVertex = i;
		if (v == sorted.front())
			printf("0\n");
		else
			printf("%d\n", minVertex);
	}

	return 0;
}