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
#include<algorithm>
#include<cassert>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<deque>
#include<iostream>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<string>
#include<vector>
using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef vector<bool> BI;

#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
#define FOREACH(i,c) for(__typeof((c).begin())i = (c).begin();i!=(c).end(); ++i)

struct E {
    int a, b;
    char c;
    bool r;

    E(int a_, int b_, char c_, bool r_) : a(a_), b(b_), c(c_), r(r_) {}
};

int n, m;
vector< vector<E> > e;
VI p;

int find_root(BI& bitset, VI& v) {
    for (int vv : v) {
        bool can_root = true;
        for (E& ee : e[vv]) {
            if (!bitset[ee.b]) continue;
            if (ee.r == false && ee.c == 'T') {
                can_root = false;
                break;
            }
            if (ee.r == true && ee.c == 'N') {
                can_root = false;
                break;
            }
        }
        if (can_root) return vv;
    }
    return -1;
}

void find_component(VI& component, BI& bitset, int vv) {
    component.push_back(vv);
    bitset[vv] = false;
    for (E& ee : e[vv]) {
        if (!bitset[ee.b]) continue;
        if (ee.c == 'N') continue;
        find_component(component, bitset, ee.b);
    }
}

int distribute(VI& v) {
    BI bitset(n, false);
    for (int vv : v) {
        bitset[vv] = true;
    }
    int root = find_root(bitset, v);
    if (root == -1) return -1;
    bitset[root] = false;
    for (int vv : v) {
        if (!bitset[vv]) continue;
        VI component;
        find_component(component, bitset, vv);
        int son = distribute(component);
        if (son == -1) return -1;
        p[son] = root;        
    }
    return root;
}

int main() {
    scanf("%d %d", &n, &m);
    e.resize(n);
    p.resize(n, -1);
    REP(i, m) {
        int a, b; char c;
        scanf("%d %d %c", &a, &b, &c); --a; --b;
        e[a].push_back(E(a,b,c,false));
        e[b].push_back(E(b,a,c,true));
    }

    VI v;
    REP(i, n) v.push_back(i);
    if (distribute(v) == -1) {
        cout << "NIE" << endl;
        return 0;
    }

    REP(i, n) {
        cout << p[i]+1 << endl;
    }
    return 0;
}