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
#include<stdio.h>
#include<vector>
#include<queue>
#include<bitset>
using namespace std;
vector<int> milosc[1000],nienawisc[1000];
bitset<1004> isLove[1000],isLove2[1000],isHate[1000],isHate2[1000];
void print(bitset<1004> b, int n)
{
    printf("%s\n",b.to_string().substr(n).c_str());
}
int ileKocha[1000];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=0;i<m;i++)
    { 
	int a,b;char ch;
	scanf("%d %d %c",&a,&b,&ch);
	a--;b--;
	if(ch=='T')
	{
	    milosc[a].push_back(b);
	    ileKocha[b]++;
	    isLove[a][b] = true;
	    isLove2[b][a]=true;

	}
	else
	{
	    nienawisc[a].push_back(b);
	    isHate[a][b]=true;
	    isHate2[b][a]=true;
	}
    }
    queue<int> kory;
    for (int i =0;i<n;i++)
    {
	if(ileKocha[i] == 0 ) kory.push(i);
    }
    int ile=0;
    while(!kory.empty())
    {
	ile++;
	int u = kory. front();
	kory.pop();
	for (int i =0;i<milosc[u].size();i++)
	{
	    int v=milosc[u][i];
	    ileKocha[v]--;
	    if(ileKocha[v] == 0 ) kory.push(v);
	    isHate[v]|= isHate[u];
	    
	    //nienawisc[v].insert(nienawisc[v].end(), nienawisc[u].begin(), nienawisc[u].end());
	}
    }
    bool fail=0;
    if(ile<n ) {printf("NIE\n"); return 0;}
    for (int i =0;i<n;i++)
	if(isHate[i][i]) {fail=1;break;}
    if(fail) {printf("NIE\n"); return 0;}
    //find boss
    int boss=-1;
    for (int i =0;i<n;i++)
    {
	if(isHate2[i].count() == 0 && milosc[i].size()==0)
	{
	    boss=i;break;
	}
    }
    if(boss==-1) { printf("NIE\n"); return 0;}
    queue<int> bossy;
    bossy.push(boss);
    bool byl[1004]={};
    int level[1004]={};
    int t[1004];
    t[boss]=-1;
    while(!bossy.empty())
    {
	int b = bossy.front();
	byl[b]=true;
	bossy.pop();
	for (int i =0;i<n;i++)
	{
	    if(byl[i]) continue;
	    if(isHate[i][b]) continue;
	    bitset<1004> tmp= isLove2[b] & isLove[i];
	    if(tmp.count() ==0)
	    {
		bossy.push(i);
		t[i]=b;
	    }
	}
    }
    for (int i =0;i<n;i++)
	printf("%d\n",t[i]+1);




}