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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
int cnt;
int flag[1005];
int res[1005];
vector<vector<int> > hrany; // ale opacne
vector<vector<int> > hranyopak;
vector<vector<int> > nehrany;
vector<vector<int> > nehranyopak;// pouze odkud kam
vector<int> pocet; // pocet hran dovnitr
vector<int> poc; // pocet nehran ven
queue <int> fronta;
int main(void){
    //freopen("in.txt", "r", stdin);
    int N, M;
    scanf("%i %i", &N, &M);
    pocet.resize(N, 0);
    poc.resize(N, 0);
    hrany.resize(N);
    hranyopak.resize(N);
    nehrany.resize(N);
    nehranyopak.resize(N);
    int i,j;
    int a,b;
    char c;
    for(i=0;i<N;i++){
        flag[i]=0;
    }
    for(i=0;i<M;i++){
        scanf("%i %i", &a, &b);
        scanf("%c", &c);
        scanf("%c", &c);
        if(c=='T') {hrany[a-1].push_back(b-1); hranyopak[b-1].push_back(a-1); pocet[a-1]++;}
        else {nehrany[a-1].push_back(b-1); nehranyopak[b-1].push_back(a-1); poc[b-1]++;}
    }
    cnt=-1;
    int zpet;
    int r[1005];
    for(i=0;i<N;i++){
        if(poc[i]==0&&pocet[i]==0){
            res[i]=-1;
            flag[i]=-2;
            for(j=0;j<hranyopak[i].size();j++){
                pocet[hranyopak[i][j]]--;
            }
            r[0]=i;
            break;
        }
        if(i==N-1){
            printf("NIE\n"); return 0;
        }
    }
    cnt=0;
    while(1){
        //if(cnt==8) return 0;
        cnt++;
        int stav=0;
        for(i=0;i<N;i++){
            poc[i]=0;
        }
        for(i=0;i<N;i++){
            if(flag[i]==-2) continue;
            else stav=1;
            if(pocet[i]==0){
                //printf("%i\n", i);
                r[cnt]=i;
                zpet=flag[i];
                flag[i]=cnt;
                stav=2;
                fronta.push(i);
                while(!fronta.empty()){
                    j=fronta.front();
                    fronta.pop();
                    for(int l=0;l<hrany[j].size();l++){
                        if(flag[hrany[j][l]]<cnt&&flag[hrany[j][l]]!=-2) {flag[hrany[j][l]]=cnt; fronta.push(hrany[j][l]);}
                    }
                    for(int l=0;l<hranyopak[j].size();l++){
                        if(flag[hranyopak[j][l]]<cnt&&flag[hranyopak[j][l]]!=-2) flag[hranyopak[j][l]]=cnt, fronta.push(hranyopak[j][l]);
                    }
                }
                break;
            }
        }
        /*for(i=0;i<N;i++){
            printf("%i ", flag[i]);
        }
        printf("\n");*/
        if(stav==0) break;
        if(stav==1) {printf("NIE\n"); return 0;}
        for(i=0;i<N;i++){
            if(flag[i]==cnt){
                for(j=0;j<nehrany[i].size();j++){
                    if(flag[nehrany[i][j]]==cnt){
                        poc[nehrany[i][j]]++;
                    }
                }
            }
        }
        stav=0;
        for(i=0;i<N;i++){
            if(flag[i]==cnt&&poc[i]==0&&pocet[i]==0){
                stav=1;
                res[i]=r[zpet];
                //printf("%i %i\n", i, res[i]);
                flag[i]=-2;
                for(j=0;j<hranyopak[i].size();j++){
                    pocet[hranyopak[i][j]]--;
                }
                break;
            }
        }
        /*for(i=0;i<N;i++){
            printf("%i ", flag[i]);
        }
        printf("\n");*/
        if(stav==0) {printf("NIE\n"); return 0;}
    }
    for(i=0;i<N;i++){
        printf("%i\n", res[i]+1);
    }
    return 0;

}