#6157. A ^ B Problem

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: igoodvegetablea

题目描述

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

数据范围与提示

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