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
111
112
113
114
115
116
117
118
119
120
121
122
#include<cstdio>
#include<bitset>
#include<cstdlib>
using namespace std;
const int N=1010,M=10010;
int n,m,i,j,x,y,e[M][3];char op[5];
int G[N],v[M],nxt[M],ed,from[N],now,g[N][N],d[N],f[N],h,t,q[N],st[N],en[N],dfn,F[N];
inline void add(int x,int y){v[++ed]=y;nxt[ed]=G[x];G[x]=ed;}
namespace BIT{
bitset<N>A[N],B[N];//A[i][j]表示j能否走到i,B[i][j]表示i,j是否有共同后继
int d[N],g[N],v[M],nxt[M],ed,h,t,q[N];
inline void add(int x,int y){d[y]++;v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
bool solve(){
  for(i=1;i<=n;i++)A[i][i]=1;
  for(h=i=1;i<=n;i++)if(!d[i])q[++t]=i;
  while(h<=t)for(i=g[x=q[h++]];i;i=nxt[i]){
    A[v[i]]|=A[x];
    if(!(--d[v[i]]))q[++t]=v[i];
  }
  if(t<n)return 0;
  for(i=n;i;i--){
    x=q[i];
    B[x]=A[x];
    for(j=g[x];j;j=nxt[j])B[x]|=B[v[j]];
  }
  return 1;
}
}
int que[N],cnt;
void dfs(int x,int y){
  if(from[x])return;
  from[x]=y;
  for(int i=1;i<=n;i++)if(g[x][i]||g[i][x])dfs(i,y);
}
void dfs2(int x){
  /*que[++cnt]=x;
  for(int i=1;i<=cnt;i++)if(BIT::B[que[i]][x]==0||BIT::B[x][que[i]]==0){
    for(int j=1;j<=cnt;j++)printf("%d\n",que[j]);
    printf("%d %d\n",que[i],x);
    exit(0);
  }*/
  st[x]=++dfn;
  for(int i=G[x];i;i=nxt[i])dfs2(v[i]);
  en[x]=dfn;
  cnt--;
}
inline bool check(int S){
  int i;
  for(ed=0,i=1;i<=n;i++)G[i]=0;
  for(i=1;i<=n;i++){
    if(i==S)F[i]=0;
    else if(!f[i])F[i]=S;
    else if(f[i]==S&&f[S])F[i]=f[S];
    else F[i]=f[i];
  }
  for(i=1;i<=n;i++)if(F[i])add(F[i],i);
  dfn=0;
  dfs2(S);
  for(i=1;i<=m;i++){
    int x=e[i][0],y=e[i][1];
    if((st[y]<=st[x]&&en[x]<=en[y])==e[i][2])return 0;
  }
  //printf("%d\n",S);
  //puts("TAK");
  for(i=1;i<=n;i++)printf("%d\n",F[i]);
  return 1;
}
int main(){
  //freopen("reo.in","r",stdin);freopen("reo.out","w",stdout);
  scanf("%d%d",&n,&m);
  for(i=1;i<=m;i++){
    scanf("%d%d%s",&x,&y,op);
    e[i][0]=x,e[i][1]=y;
    if(op[0]=='T')add(x,y),g[y][x]=1,BIT::add(y,x);else e[i][2]=1;
  }
  if(!BIT::solve())return puts("NIE"),0;
  for(i=1;i<=m;i++)if(e[i][2]){
    x=e[i][0],y=e[i][1];
    for(j=1;j<=n;j++)if(BIT::A[x][j]&&BIT::B[y][j])g[j][y]=1;
  }
  for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(g[i][j])d[j]++;
  for(h=i=1;i<=n;i++)if(!d[i])q[++t]=i;
  while(h<=t)for(x=q[h++],i=1;i<=n;i++)if(g[x][i])if(!(--d[i]))q[++t]=i;
  if(t!=n)return puts("NIE"),0;
  for(i=1;i<=n;i++)if(!from[i])dfs(i,++now);
  for(i=2;i<=n;i++){
    x=q[i];
    for(j=i-1;j;j--)if(BIT::B[x][q[j]]){f[x]=q[j];break;}
    if(j)continue;
    for(j=i-1;j;j--)if(from[x]==from[q[j]]){f[x]=q[j];break;}
  }
  //x选择y当且仅当x和y必须在一条链上
  /*for(i=1;i<=n;i++)if(f[i]){
    if(BIT::B[f[i]][i]==0)while(1);
    if(BIT::B[i][f[i]]==0)while(1);
  }*/
  //printf("->f[422]=%d\n",f[422]);
  /*for(ed=0,i=1;i<=n;i++)G[i]=0;
  for(i=1;i<=n;i++)if(f[i])add(f[i],i);
  dfn=0;
  for(i=1;i<=n;i++)if(!f[i])dfs2(i);*/
 /* for(i=1;i<=m;i++){
    int x=e[i][0],y=e[i][1];
    if((st[y]<=st[x]&&en[x]<=en[y])==e[i][2])while(1);
  }*/
  //for(i=1;i<=n;i++)printf("%d ",q[i]);puts("");
  //for(i=1;i<=n;i++)printf("%d ",f[i]);puts("");
  //for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)if(BIT::B[i][j])printf("%d %d\n",i,j);
  for(i=1;i<=n;i++)if(check(i))return 0;
  return puts("NIE"),0;
}
/*
i和j有共同后继

f[i][j]
i和j在一条树链上，等价于存在某个点v，使得i,j都能到v*/


/*
对于一个T连通块，入度为0的可以按任意方式串成一条链
剩下的
*/