I. Cosmic Bit Flip
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Bob visited the country of Bakdum not so long ago. The country has $$$n$$$ cities and they are all connected by two-way roads. Also, from one city, there is exactly one way to reach any other city.

Among the cities, there are several with high security because they have magical ley-lines running through them. Any city has at most 1 ley-line running through it. Bob went to a total of $$$m$$$ tours to see the ley-lines. During each tour, he was able to ride on a tracker bus, which could detect the presence of ley-lines. The $$$i$$$th tour can be represented as Bob going from city $$$u_i$$$ to city $$$v_i$$$, and during the whole tour the tracker was always on. But due to magical interference, Bob was only able to determine whether there was an even or odd number of ley-lines on that path, given as $$$p_i \in \{0, 1\}$$$.

Now after Bob returned, he was confused about the data he had collected. He has a suspicion that one of his tour results got flipped by a high energy cosmic ray bit flip incident. Now, for each tour report, assuming it was flipped individually, calculate the revised total number of ley-lines in Bakdum. If it is impossible to determine it uniquely or the data is inconsistent report them too.

Input

The first line of the input contains $$$n$$$ ($$$1 \leq n \leq 500$$$) and $$$m$$$ ($$$1 \leq m \leq 50,000$$$).

Then follows $$$n - 1$$$ lines providing the city connections. Each line contains two integers $$$u$$$ and $$$v$$$, meaning there is a road between the cities $$$u$$$ and $$$v$$$. It is guaranteed that the layout satisfies the conditions in the statement.

Then there are $$$m$$$ lines, the $$$i$$$th line contains $$$u_i, v_i, p_i$$$ $$$(1 \leq u_i, v_i \leq n, p_i \in \{0, 1\})$$$. Here, $$$p_i = 0$$$ means the total number of ley-lines on that path was even, and $$$p_i = 1$$$ otherwise.

Output

Output $$$m$$$ lines. The $$$i$$$th line should contain the total number of ley-lines in the country if the $$$i$$$th tour result was flipped. If the data is inconsistent output "impossible". If it is not possible to determine it uniquely, output "unknown". The output is case-sensitive.

Examples
Input
5 6
1 2
2 3
2 4
4 5
1 1 0
1 3 1
3 4 1
1 4 1
1 5 0
1 2 0
Output
5
2
3
1
impossible
2
Input
4 4
1 2
1 3
3 4
1 1 1
2 2 1
1 2 0
3 3 1
Output
impossible
impossible
impossible
unknown