F. Carbon Neutral
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Kazakhstan is a country that takes the problem of global warming very seriously. For this reason, the Kazakh government is implementing Green Economy in the country. To achieve this, it is necessary for all companies in the country to reach carbon neutrality.

There are $$$n$$$ companies in Kazakhstan, and we can model the transactions between them as a directed graph with $$$m$$$ edges. An edge that goes from $$$u$$$ to $$$v$$$ indicates a transaction made from company $$$u$$$ to company $$$v$$$. The Kazakh government needs to make a decision for each of these transactions, which can be modeled as assigning an integer weight $$$-1 \leq w \leq 1$$$ to the corresponding edge. The weight $$$w = 0$$$ indicates that the transaction is prohibited. Weights $$$w = -1$$$ and $$$w = 1$$$ indicate that the transaction absorbs or emits carbon, respectively.

For a company $$$v$$$ to achieve carbon neutrality, it must hold that $$$c^+(v) = c^-(v)$$$, where $$$c^+(v)$$$ indicates the sum of the weights of the edges that leave $$$v$$$ and $$$c^-(v)$$$ indicates the sum of the weights of the edges that enter it. It is clear that, by prohibiting all transactions, the Kazakh government could achieve its Green Economy goal; however, the important transactions cannot be prohibited because the country's economy would collapse! A transaction $$$i$$$ is important if $$$t_i = 1$$$.

Given the description of the transactions between the companies in Kazakhstan, determine if it is possible to implement carbon neutrality in all companies. If it is possible, provide a solution.

Input

The first line of input contains two integers $$$n$$$ ($$$1 \leq n \leq 10^6$$$) and $$$m$$$ ($$$1 \leq m \leq 10^6$$$).

The following $$$m$$$ lines describe the edges of the graph. The $$$i$$$-th line describes the $$$i$$$-th edge with 3 integers: $$$u_i, v_i, t_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$, $$$0 \leq t_i \leq 1$$$). The value $$$t_i = 1$$$ indicates that the $$$i$$$-th edge represents an important transaction that cannot be prohibited.

Output

Print a line with the letter "S" if a solution exists or "N" if it does not. If a solution exists, on the second line, print $$$m$$$ integers. The $$$i$$$-th of these integers should be the weight assigned to the $$$i$$$-th edge.

Examples
Input
4 5
1 2 1
1 3 0
3 2 0
2 4 0
3 4 1
Output
S
-1 1 0 -1 1
Input
2 1
1 2 1
Output
N
Input
3 2
1 3 1
1 3 0
Output
S
-1 1