题目背景

译自 Potyczki Algorytmiczne 2016 R2 Reorganizacja [A] (REO)。$\texttt{1s,256M}$。

题目描述

构造一棵 $n$ 个节点的有根树，满足 $m$ 条限制，形如「$x$ 必须是 $y$ 的祖先」或者「$x$ 必须不是 $y$ 的祖先」。

输入格式

第一行，两个整数 $n,m$。

接下来 $m$ 行，每行两个正整数和一个字符 $x,y,c$。其中 $x,y$ 为正整数，$c\in \{\texttt{T},\texttt{N}\}$，$x\neq y$。

• 若 $c=\texttt{T}$，表示 $y$ 必须是 $x$ 的祖先；
• 否则，表示 $y$ 必须不是 $x$ 的祖先。

保证不会重复给出同一条信息。

输出格式

若无解，输出一行一个 $\texttt{NIE}$；

否则输出 $n$ 行，每行一个整数，表示 $i$ 号点的父亲。

• 特别地，若 $i$ 是根，则规定其父亲为 $0$。

4 4
4 1 T
4 2 T
3 2 N
4 3 N

0
1
1
2

2 2
1 2 N
2 1 N

NIE

提示

• $1\le n\le 10^3$；
• $0\le m\le \min(n(n-1), 10^4)$；
• $1\le x,y\le n$，$x\neq y$。

保证不会重复给出同一条信息。