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

using namespace std;

const int MAX_N = 1001;

struct Node {
  set<int> T;
  vector<int> CHILD;
  set<int> N;
  set<int> NALL;
  set<int> NOT;
  int parent;
};

Node t[MAX_N];
int n, m;

void solve() {
  int *done = new int[n+1];
  for(int i = 0; i <= n; i++)
    done[i] = -1;
  bool res = true;
  int first = 0;
  for(int i = 0; i < n; i++) {
    int ok = -1;
	for(int j = 1; j <= n && ok == -1; j++) {
	  if(done[j]== -1) {
	    if((i > 0 || t[j].NOT.size() == 0) && t[j].T.size() == 0) {
		  ok = j;
		}
	  }
	}
	//printf("%d\n",ok);
	if(ok==-1) break;
	if(i == 0) {
	  done[ok] = 0;
	  t[ok].parent = 0;
	  first = ok;
	} else {
	  if(t[ok].parent == -1) {
	    done[ok] = first;
	  } else {
	    done[ok] = t[ok].parent;
	  }
	}
	for (std::vector<int>::iterator it = t[ok].CHILD.begin(); it != t[ok].CHILD.end(); ++it) {
	  int val = *it;
	  t[val].T.erase(t[val].T.find(ok), t[val].T.end());
	  t[val].parent = ok;
	  //printf("size %d %d\n", val, t[val].T.size());
	}
	for (std::set<int>::iterator it = t[ok].N.begin(); it != t[ok].N.end(); ++it) {
	  int val = *it;
	  t[val].NOT.erase(t[val].NOT.find(ok), t[val].NOT.end());
	}
  }
  
  for(int i = 1; i <= n; i++) { 
    if(done[i] == -1) res = false; 
	int j = done[i];
	while(j > 0) {
	  if(t[i].NALL.find(j) != t[i].NALL.end()) res = false; 
	  j = done[j];
	}
    //printf("%d %d\n", i, done[i]);
  }
  string s = "NIE";
  if(res) s = "TAK";
  if(!res) {
    printf("%s\n", s.c_str()); 
  } else {
    for(int i = 1; i <= n; i++)
	  printf("%d\n", done[i]);
  }
}
int main(int args, char* argv[]) {
  scanf("%d%d", &n, &m);  
  for(int i = 0; i <= n; i++) t[i].parent = -1;
  for(int i = 0; i < m; i++) {
    int a, b;
	char c;
	scanf("%d%d %c", &a, &b, &c);
    if(c=='T') {
      t[a].T.insert(b);
	  t[b].CHILD.push_back(a);
	}
    if(c=='N') {
      t[a].N.insert(b);
      t[a].NALL.insert(b);
	  t[b].NOT.insert(a);
    }	  
  }
  solve();
  return 0;
}