题目描述

题目译自 PA 2016 Runda 2 Reorganizacja

Bajtazar 是一位享誉全球的人力资源管理专家。最近，他被一家信息技术公司聘请，负责对其僵化的组织结构进行重组。

Bajtazar 提出的新结构以其简洁性而显得天才。它基于几个基本概念：总监、直接上司和上级。

• 公司中恰好有一名员工将成为总监，不会有任何直接上司。
• 除总监外，每名员工将有且仅有一名直接上司。
• 员工的上级包括其直接上司以及直接上司的上级。
• 总监是其他所有员工的上级。

用图论语言描述：员工是层级树的一个节点，总监是树的根节点，员工的直接上司是节点的父节点，上级是节点的祖先节点。

Bajtazar 认为，公司此前的诸多问题源于上级与下属之间的矛盾。为了在重组后避免此类问题，他收集了所有员工的偏好信息。每名员工可以对任意数量的同事表达两种意见：「我希望 $X$ 成为我的上级。」或「我不希望 $X$ 成为我的上级。」现在，Bajtazar 将尝试设计一个层级结构，以满足所有员工的偏好。

输入格式

输入数据的第一行包含两个整数 $n$ 和 $m$ $(1 \leq n \leq 1000, 0 \leq m \leq \min\{n(n-1), 10000\})$，分别表示公司员工数量和收集到的偏好数量。员工编号为从 $1$ 到 $n$ 的连续整数。

接下来的 $m$ 行描述员工的偏好。每行格式为 $a$ $b$ $c$，其中 $a$ 和 $b$ $(a \neq b)$ 是员工编号，$c$ 是集合 $\{\texttt{T}, \texttt{N}\}$ 中的一个字符。如果 $c = \texttt{T}$，表示员工 $a$ 希望员工 $b$ 成为他的上级；如果 $c = \texttt{N}$，表示员工 $a$ 不希望员工 $b$ 成为他的上级。对于每对有序员工编号 $(a, b)$，格式为 $a$ $b$ $c$ 的行在输入中最多出现一次。

输出格式

如果无法创建满足所有员工偏好的层级结构，则输出 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