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
#include <cstdio>
#include <vector>
#include <numeric>

const int MAX_N = 1009;

std::vector<std::vector<int> > haters;
std::vector<std::vector<int> > likes;
std::vector<std::vector<int> > likers;
int likes_left[MAX_N];
int boss[MAX_N];

int groups[MAX_N];
int group_id;

void visit(int a, std::vector<int>& subgroup) {
    int oldid = groups[a];
    groups[a] = group_id;
    subgroup.push_back(a);
    for (int b : likers[a]) {
        if (groups[b] == oldid) {
            visit(b, subgroup);
        }
    }
    for (int b : likes[a]) {
        if (groups[b] == oldid) {
            visit(b, subgroup);
        }
    }
}

bool check(int a) {
    if (likes_left[a] != 0) {
        return false;
    }
    for (int h : haters[a]) {
        if (groups[h] == groups[a]) {
            return false;
        }
    }
    return true;
}

bool build_tree(int r, const std::vector<int>& group) {
    for (int a : group) {
        if (check(a)) {
            boss[a] = r;
            for (int b : likers[a]) {
                --likes_left[b];
            }
            int id = groups[a];
            groups[a] = -1;
            for (int b : group) {
                if (groups[b] == id) {
                    ++group_id;
                    std::vector<int> subgroup;
                    visit(b, subgroup);
                    if (!build_tree(a, subgroup)) {
                        return false;
                    }
                }
            }
            return true;
        }
    }
    return false;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    haters = std::vector<std::vector<int> >(n+1);
    likes = std::vector<std::vector<int> >(n+1);
    likers = std::vector<std::vector<int> >(n+1);
    for (int i = 0; i < m; ++i) {
        int a, b;
        char c[2];
        scanf("%d%d%s", &a, &b, c);
        if (c[0] == 'T') {
            likes[a].push_back(b);
            likers[b].push_back(a);
            ++likes_left[a];
        } else if (c[0] == 'N') {
            haters[b].push_back(a);
        }
    }
    std::vector<int> all(n);
    std::iota(all.begin(), all.end(), 1);
    if (build_tree(0, all)) {
        for (int i = 1; i <= n; ++i) {
            printf("%d\n", boss[i]);
        }
    } else {
        printf("NIE\n");
    }
}