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 <bitset>
#include <cstdio>
#include <vector>
using namespace std;

void getoud() {
    printf("NIE\n");
    exit(0);
}

const int maxN = 1024;
bitset<maxN>reach[maxN];
vector<int>yup[maxN];
vector<int>_yup[maxN];
vector<int>nope[maxN];

bool B[maxN];
bool _B[maxN];
bool not_liked[maxN];
int director;

void pre_dfs(int v) {
    reach[v].set(v);
    B[v] = 1;
    for(int a: yup[v]) {
        if(B[a] && !_B[a]) getoud();
        if(!B[a]) pre_dfs(a);
        reach[v] |= reach[a];
    }
    _B[v] = 1;
}

void dfs_set(int v) {
    B[v] = _B[v] = 0;
    for(int a: _yup[v]) {
        if(B[a]) dfs_set(a);
        reach[v] |= reach[a];
    }
}

int ans[maxN];
int color[maxN];
int merge(vector<int> const& v) {
    static int c = 0;
    c++;
    int x = v[0], attach_to = v[0];
    while(x) {
        color[x] = c;
        x = ans[x];
    }
    for(int a: v) if(color[a] != c) {
        color[x = a] = c;
        while(ans[x] && color[ans[x]] != c) {
            x = ans[x];
            color[x] = c;
        }
        ans[x] = attach_to;
        attach_to = a;
    }
    return attach_to;
}

void dfs_ans(int v) {
    B[v] = 1;
    for(int a: yup[v]) {
        if(B[a] && !_B[a]) getoud();
        if(!B[a]) dfs_ans(a);
    }
    if(yup[v].size()) ans[v] = merge(yup[v]);
    _B[v] = 1;
}

int main() {
    int n, m; scanf("%d%d", &n, &m);
    char c[10];
    for(int a, b, i = 0; i < m; ++i) {
        scanf("%d%d%s", &a, &b, c);
        if(c[0] == 'T') {
            yup[a].push_back(b);
            _yup[b].push_back(a);
        }
        else {
            nope[a].push_back(b);
            not_liked[b] = 1;
        }
    }

    for(int i = 1; i <= n; ++i) if(yup[i].empty() && !not_liked[i]) director = i;
    if(!director) getoud();
    for(int i = 1; i <= n; ++i) if(i != director) yup[i].push_back(director);

    for(int i = 1; i <= n; ++i) if(!B[i]) pre_dfs(i);
    for(int i = 1; i <= n; ++i) if(B[i]) dfs_set(i);
    for(int v = 1; v <= n; ++v) {
        for(int a: nope[v]) {
            if(reach[v][a]) {
                yup[a].push_back(v);
            }
            else {
                for(int i = 1; i <= n; ++i)
                    if(reach[v][i] && reach[a][i]) {
                        yup[a].push_back(i);
                    }
            }
        }
    }

    for(int i = 1; i <= n; ++i) if(!B[i]) dfs_ans(i);
    for(int i = 1; i <= n; ++i) if(!ans[i] && i != director) ans[i] = director;
    for(int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
}