P11606 [PA 2016] 构树 / Reorganizacja

译自 [Potyczki Algorytmiczne 2016](https://sio2.mimuw.edu.pl/c/pa-2016-1/p/) 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$。

- $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$。 保证不会重复给出同一条信息。