Bajtazar 是一位世界闻名的人力资源管理专家。最近，他受雇于一家 IT 公司，负责对其僵化的组织结构进行重组。

Bajtazar 提出的新结构简单而巧妙，它基于几个基本概念：总监（director）、上司（boss）和上级（superior）。

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

用图论的语言来说：员工是层级树中的节点，总监是树的根，员工的上司是节点的父亲，而上级则是祖先。

Bajtazar 得出结论，公司以往的问题源于处于上级-下属关系的员工之间的反感。为了在重组后避免此类问题，他收集了所有员工的偏好信息。每位员工都可以对任意数量的同事发表意见，方式有两种：“我希望 X 成为我的上级。”或者“我不希望 X 成为我的上级。”现在，Bajtazar 试图制定一个层级结构，以满足所有这些偏好。

输入格式

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

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

输出格式

如果无法创建满足所有员工偏好的层级结构，请输出 NIE。否则，你的程序应输出 $n$ 行，描述任意一个满足所有偏好的层级结构。第 $i$ 行应包含一个整数，表示编号为 $i$ 的员工的上司编号。对于被选为总监的员工，其对应的行应输出 $0$。

样例

输入 1

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

输出 1

0
1
1
2

输入 2

2 2
1 2 N
2 1 N

输出 2

NIE