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
// Reorganizacja [A], Jakub Szczugiel
#include <bits/stdc++.h>
#define rep(a,b) for(int a = 0; a < b; a++)

using namespace std;

bool graf[1005][1005];
bool odw[1005];
int s[1005];
int n, root, ile;

void dfs(int v)
{
    odw[v] = 1;
    rep(i, n) if(graf[v][i] && !odw[i]){
        graf[i][v] = 0;
        dfs(i);
    }
}

void cdfs(int v)
{
     odw[v] = 1;
     ile++;
    rep(i, n) if(graf[v][i] && !odw[i]){
        graf[i][v] = 0;
        s[i] = v+1;
        cdfs(i);
    }
}


int main()
{
    ios_base::sync_with_stdio(0);
    int m;
    cin >> n >> m;

    rep(i, n){
        odw[i] = 0;
        rep(j, n) graf[i][j] = 1;
    }

    int a, b;
    char c;
    rep(i, m){
        cin >> a >> b >> c;
        a--;
        b--;
        if(c == 'T') graf[a][b] = 0;
        else graf[b][a] = 0;
    }

    rep(i, n)if(!odw[i]){
        root = i;
        dfs(i);
    }

    rep(i, n) odw[i] = 0;

    ile = 0;
    s[root] = 0;
    cdfs(root);

    if(ile == n){
        rep(i, n) cout << s[i] << ' ';
    }
    else cout << "NIE";

}