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

using namespace std;

int main() {
    int n, m, temp;
    char c;
    scanf("%d%d", &n, &m);
    vector<set<int>> niemozenad(n); // [a] nie moze miec b nad soba
    vector<set<int>> niemozepod(n); // [a] nie moze miec b pod soba
    vector<set<int>> musinad(n); // [a] musi miec b nad soba
    vector<set<int>> musipod(n); // [a] musi miec b pod soba
    vector<set<int>> manad(n); // [a] ma b nad soba
    set<int> wolne;
    queue<int> kol;
    for(int i = 0; i < n; ++i)
        wolne.insert(i);

    vector<int> szef(n);
    for(int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d%d %c", &a, &b, &c);
        --a;
        --b;
        if(c=='N') {
            niemozenad[a].insert(b);
            niemozepod[b].insert(a);
        } else {
            musinad[a].insert(b);
            musipod[b].insert(a);
            for(auto &&x : musinad[b]) {
                musinad[a].insert(x);
            }
            for(auto &&x : niemozenad[b]) {
                niemozenad[a].insert(x);
            }
        }
    }
    for(int j = 0; j < n; ++j) {
        if(musinad[j].size() == 0 && niemozepod[j].size() == 0) {
            szef[j] = -1;
            wolne.erase(j);
            kol.push(j);
            break;
        }
    }

    if(kol.empty()) {
        printf("NIE\n");
        return 0;
    }

    while(kol.size()) {
        set<int> nowe;
        for(auto &&a : wolne) {
            int b = kol.front();
            set<int> jeszczenad = musinad[a];
            bool dobrze = true;
            for(auto &&x : manad[b]) {
                jeszczenad.erase(x);
                if(niemozenad[a].count(x)) {
                    dobrze = false;
                    break;
                }
            }
            jeszczenad.erase(b);
            if(jeszczenad.empty() && dobrze) {
                szef[a] = b;
                nowe.insert(a);
                manad[a] = manad[b];
                manad[a].insert(b);
            }
        }
        for(auto &&a : nowe) {
            kol.push(a);
            wolne.erase(a);
        }
        kol.pop();
    }

    if(wolne.empty()) {
        for (int i = 0; i < n; ++i) {
            printf("%d\n", szef[i] + 1);
        }
    } else {
        printf("NIE\n");
    }
}