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
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

class wrkr{
public:
    wrkr();
    int boss;
    int id;
    int level;
    vector<int>T;
    vector<int>N;
    vector<int>No;
    bool operator<(const wrkr &o)const{
        return No.size() < o.No.size();
    };
    bool accept(int);
};
wrkr::wrkr(){
    level=-1;
    boss=-1;
};
bool wrkr::accept(int x){
    for(int i=0;i<T.size();i++){
        if(T[i]==x)return true;
    }
    for(int i=0;i<N.size();i++){
        if(N[i]==x)return false;
    }
    return true;
};


main(){
 int n,m,a,b;
 char c;
 wrkr W[1001];
 cin >> n;
 cin >> m;
 for(int i=0;i<m;i++){
    cin >> a;
    cin >> b;
    cin >> c;
    if(c=='T') W[a].T.push_back(b);
    if(c=='N') {
        W[a].N.push_back(b);
        W[b].No.push_back(a);
    }
 }
 for(int i=1;i<=n;i++){
    W[i].id=i;
    W[i].level=-1;
 }
 //for(int i=1;i<=n;i++){cout<<i<<" "<<W[i].id<<" "<<W[i].No.size()<<endl;}
 sort(&W[1],&W[n+1]);
 //for(int i=1;i<=n;i++){cout<<i<<" "<<W[i].id<<" "<<W[i].No.size()<<endl;}
 if(W[1].No.size()>0){
    cout << "NIE" << endl;
    return 0;
 }

 int count=1;
 W[1].boss=0;
 for(int i=1;i<=n;i++){
    W[i].level=1;
    for(int j=2;j<=n;j++){
        if(i==j)continue;
        if(W[j].level!=-1)continue;
        if(W[i].accept(W[j].id)){
            W[j].boss=W[i].id;
            W[j].level=1;
            count++;
        }
    }
 }
 if(count<n){
    cout << "NIE" << endl;
    return 0;
 }
 cout << 0 << endl;
 for(int i=2;i<=n;i++){
    for(int j=2;j<=n;j++){
        if(W[j].id==i){
            cout<<W[i].boss<<endl;
            break;
        }
    }
 }

 return 0;
}