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
#include<bits/stdc++.h>

using namespace std;

vector<int> tos[1009];
vector<int> ntos[1009];
vector<int> nrnad;
int n, m;
int fat[1009];
vector<int> sons[1009];
int odw[1009];
int licz;
int wyp;

int spr(int gfat){
	if(odw[gfat]==0){++licz;++odw[gfat];}
	int ret=1;
	int wst=0, wsnt=0, wsd=0;
	sort(nrnad.begin(), nrnad.end());
	while(1){
		if(tos[gfat][wst]==nrnad[wsd]){++wsd;if(wsd==nrnad.size())break;}
		else if(tos[gfat][wst]<nrnad[wsd]){++wst;if(wst==tos[gfat].size())return 0;}
		else return 0;
	}
	wst=0;wsd=0;
	while(1){
		if(ntos[gfat][wst]==nrnad[wsd]){return 0;}
		else if(ntos[gfat][wst]<nrnad[wsd]){++wst;if(wst==ntos[gfat].size())break;}
		else {++wsd;if(wsd==nrnad.size())break;}
	}
	nrnad.push_back(gfat);
	for(int i=0;i<sons[gfat].size();++i){

		ret=min(ret, spr(sons[gfat][i]));
	}
	nrnad.pop_back();

	return ret;
}

int cccc(int gfat, int nr){
	if(wyp==1)return 1;
	if(nr==gfat)return cccc(gfat, nr+1);
	int ret=0;
	if(nr==n+1){
		ret=spr(gfat);
		for(int i=1;i<n;++i)odw[i]=0;
		if(licz!=n)ret=0;
		licz=0;
		if(ret==1){
			wyp=1;
			for(int i=1;i<=n;++i){
				printf("%d\n", fat[i]);
			}
		}
		return ret;
	}

	for(int i=1;i<=n;++i){
		sons[i].push_back(nr);
		fat[nr]=i;
		ret=max(ret,cccc(gfat, nr+1));
		sons[i].pop_back();
		fat[nr]=0;
	}

	return ret;
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i=0;i<m;++i){
		int a, b;char c;
		scanf("%d%d %c", &a, &b, &c);
		if(c=='T'){
			tos[a].push_back(b);
		}
		else{
			ntos[a].push_back(a);
		}
	}
	for(int i=1;i<=n;++i){
		sort(tos[i].begin(), tos[i].end());
		sort(ntos[i].begin(), ntos[i].end());
	}

	int wyn=0;
	for(int i=1;i<=n;++i){
		wyn=max(wyn, cccc(i, 1));
	}
	if(wyn==0)printf("NIE\n");

	return 0;
}