#CW4. 异或约束(xor)

异或约束(xor)

题目描述

有一棵包含 nn 个节点的树,每条边上都标有一个未知的整数,范围为 [0,260−1][0, 2^{60} - 1]。

现在依次收到 mm 条约束。每条约束形如:已知从节点 uu 到节点 vv 的路径上,所有边权的异或和必须等于 valval。

这些约束可能并不全部正确。

定义 pp 为满足以下条件的最大整数:

  • 前 pp 条约束可以同时成立,即存在一种边权分配方案满足它们;
  • 而加入第 p+1p + 1 条约束后,不再存在满足所有这些约束的边权分配方案;或者 p=mp = m,即不存在第 p+1p + 1 条约束。

请求出每组数据对应的 pp。

输入格式

第一行包含两个整数 n,mn, m(1≤n,m≤1051 \le n, m \le 10^5),分别表示树的节点数和约束数量。

接下来 n−1n - 1 行,每行包含两个整数 u,vu, v(1≤u,v≤n1 \le u, v \le n),表示一条连接节点 uu 与节点 vv 的无向边。

接下来 mm 行,每行包含三个整数 u,v,valu, v, val,表示一条约束:

xor⁡(u→v)=val\operatorname{xor}(u \to v) = val

其中 1≤u,v≤n1 \le u, v \le n,且 0≤val<2600 \le val < 2^{60}。

输出格式

输出一个整数 pp,表示能够同时满足的最长前缀约束长度。

样例 1 输入

7 5
1 2
2 3
3 4
4 5
5 6
6 7
1 3 1
3 5 0
5 7 1
1 7 1
2 3 2

样例 1 输出

3

数据范围

对于所有测试数据,保证:1≤n,m≤1051 \le n, m \le 10^5,1≤u,v≤n1 \le u, v \le n,0≤val<2600 \le val < 2^{60}。

测试点 n≤n \le m≤m \le val<val < 特殊性质
1∼41 \sim 4 1010 232^3 无
5∼75 \sim 7 10001000 2602^{60} 树是一条链
8∼98 \sim 9 2102^{10} 无
10∼1210 \sim 12 10510^5
13∼1513 \sim 15 2602^{60} 每个约束中,有 u=1u = 1
16∼2016 \sim 20 无