题目描述

wmq 最近对破解芯片内部结构产生了极强的兴趣。现有一芯片，它是由外部的 $n$ 个输入端和内部的 $n-1$ 条线路构成（假设输入端被从 $1$ 到 $n$ 编号），其中每条线路连接 2 个不同的输入端，且任意两输入端都通过一条由线路组成的路径连接起来。每条线路都有一个自身的 16 位“逻辑值”。如果对其中的两个输入端通上电源，将会有电流流经连接这两个输入端的路径上经过的线路，芯片将会对这些线路的“逻辑值”取异或 $(\text{xor},\oplus)$ 作为输出。例如，电流流经了 3 条线路，其逻辑值分别为 $2,3,5$，则输出结果为 $2 \oplus 3 \oplus 5=4$。

wmq 非常想知道每条线路上的“逻辑值”。为此他做了 $m$ 次实验，每次实验中他都会选择其中的两个输入端并通上电源，然后记录下输出结果。wmq 后来还通过各种研究得到了芯片内部的线路拓扑结构，他想知道数据是否已经足够确定每条线路的“逻辑值”。

输入格式

首行为数据组数，接下来每组数据的输入格式如下：

第一行为两个整数 $n,m(2\leq n\leq 10^5,1\leq m\leq 2\times 10^5)​$，分别表示芯片输入端个数和实验次数。

接下来 $n-1$ 行每行两个数 $a,b(1\leq a,b\leq n,a\neq b$，表示编号为 $a$ 和 $b$ 的输入端连有一条线路。

接下来 $m$ 行，每行 3 个整数 $s,t,w(1\leq s,t\leq n,s\neq t,0\leq w<2^{16}$，表示对编号为 $s$ 和 $t$ 的输入端通上电源时，输出结果为 $w$。

总输入量 $\sum{n}≤5\times 10^5,\sum{m}≤10^6$。

输出格式

对每组数据，按下面的格式输出一行：

如果能唯一确定所有线路的“逻辑值”，输出最小的和最大的“逻辑值”，中间用一个空格隔开；如果有不止一种可能的结果，输出 No；如果不存在一种可能的结果，表明 wmq 由于粗心大意记错了数据，此时输出 Impossible。

3
3 2
1 2
2 3
1 2 2
2 3 3
3 1
1 2
2 3
1 2 2
3 3
1 2
2 3
1 2 2
2 3 3
1 3 0

2 3
No
Impossible

数据范围与提示

对于一组数据，即使读到一半时已经得出答案，也务必要继续把这组数据读完。