Bajtazar is a world-renowned human resources management specialist. He was recently hired by an IT corporation to reorganize its rigid structure.

The new structure proposed by Bajtazar is brilliant in its simplicity. It is based on a few basic concepts: director, boss, and superior.

• Exactly one employee of the corporation will be the director and will have no boss.
• Every employee other than the director will have exactly one boss.
• The superiors of an employee include their boss and the superiors of that boss.
• The director will be the superior of every other employee.

Using the language of graph theory: an employee is a node in the hierarchy tree, the director is its root, an employee's boss is the parent of the node, and a superior is an ancestor.

Bajtazar concluded that the previous problems in the corporation stemmed from antipathy between employees in a superior-subordinate relationship. To avoid such problems after the reorganization, he collected information about the preferences of all employees. Each of them could express their opinion about any number of colleagues in one of two ways: "I want X to be my superior" or "I do not want X to be my superior." Now, Bajtazar will try to develop a hierarchy such that all preferences are satisfied.

Input

The first line of input contains two integers $n$ and $m$ ($1 \le n \le 1000$, $0 \le m \le \min\{n(n-1), 10\,000\}$), representing the number of employees in the corporation and the number of collected preferences, respectively. Employees are numbered with consecutive integers from $1$ to $n$.

The next $m$ lines describe the employees' preferences. Each line is of the form $a\ b\ c$, where $a$ and $b$ ($a \neq b$) are employee numbers, and $c$ is a character from the set $\{T, N\}$. If $c = T$, then such a line means that employee $a$ wants employee $b$ to be their superior. If $c = N$, then $a$ does not want $b$ to be their superior. For each ordered pair of employee numbers $(a, b)$, a line of the form $a\ b\ c$ appears in the input at most once.

Output

If it is impossible to create a hierarchy that satisfies all employee preferences, output the word NIE. Otherwise, your program should output $n$ lines describing any hierarchy that satisfies all employee preferences; the $i$-th line should contain a single integer – the boss number of employee $i$. The line corresponding to the employee who is to be the director should contain the number $0$.

Examples

Input 1

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

Output 1

0
1
1
2

Input 2

2 2
1 2 N
2 1 N

Output 2

NIE