题意回顾

给一个连通无向图，一次操作可以选择一个边集和一个数 (X)，将这些边的权值都异或 (X)。
目标：使图中每个简单环的边权异或和为 0。
求最少操作次数，并给出一种方案。

---

关键转化

1. 条件等价化

设 (W(e)) 是边 (e) 的权值。
图是“好”的
(\iff) 任意环 (C) 满足 (\bigoplus_{e \in C} W(e) = 0)
(\iff) 对于任意两条从 (u) 到 (v) 的路径，路径上的边权异或和相等（因为环 = 路径1 ⊕ 路径2）。

---

2. 生成树与路径异或和

任取一棵生成树 (T)。
定义 (val[x]) 为树根（比如 1）到 (x) 的路径上边权异或和。
那么对于树上路径 (u \to v)，其异或和 = (val[u] \oplus val[v])。

对于一条非树边 ((u,v,w))，它和树上路径构成的环的异或和为： [ (val[u] \oplus val[v]) \oplus w ] 这个必须等于 (0)，所以： [ val[u] \oplus val[v] \oplus w = 0 \quad\text{(目标条件)} ]

记当前图的 (val[u]) 是用当前边权算出来的，当前非树边 ((u,v,w)) 计算出的 [ d = val[u] \oplus val[v] \oplus w ] 若 (d \neq 0)，说明这个环不满足条件。

---

3. 如何修改

一次操作：选一个边集 (S) 和一个数 (X)，把这些边的权异或 (X)。

这样的操作会如何影响 (val[u])？
如果一条边 ((a,b,w)) 在树上，且它的权异或 (X)，那么所有在 (a) 那边子树里的点的 (val) 都会异或 (X)（假设 (a) 是父亲）。
这样比较复杂。更好的角度是：考虑对边权的影响，我们希望改变一些边的权，使得所有 (d=0)。

注意：
[ val[u] = \text{XOR of weights on path root->u in tree} ] 设初始的树边权为 (w_1,\dots,w_{n-1})，非树边权固定。
初始时我们可以算出 (val)，然后算出每个非树边的 (d)。

---

4. 改变权值的效果

设我们把某条边 (e) 的权异或 (X)，它会影响经过 (e) 的所有环。
特别地，它会影响所有包含 (e) 的非树边对应的环。

更精确的：
如果我们改变一条树边的权值，所有包含该树边的环都会变化，也就是所有端点分别在该树边两侧的非树边对应的 (d) 都会异或 (X)。

如果我们改变一条非树边的权值，只影响它自己对应的环的 (d)。

---

5. 线性代数视角

把每条非树边看成一个方程：
设树边权固定时，非树边 (i) 对应的 (d_i) 不为 0。我们希望通过操作让所有 (d_i = 0)。

一次操作：

• 选取一个集合的边，把它们同时异或 (X)。
• 这个操作对所有 (d_j) 的影响是：如果边集包含树边 (t)，且非树边 (j) 在树边 (t) 的两侧（即非树边的环包含 (t)），则 (d_j) 异或 (X)。
• 如果边集包含非树边 (j)，则 (d_j) 异或 (X)。

这样，一次操作就是选一个边集 (S)，对每个包含至少一个 (S) 中边的环（对应的 (d_j)）进行异或 (X)。

实际上，我们可以把非树边的 (d_j) 看作向量空间 (\mathbb{F}_2^k) 中的向量（k 是非树边数量），每个操作就是选一个子集，给这个子集里对应的 (d_j) 异或 (X)，不同的 (X) 可以分开考虑。

重要结论（可通过构造证明）：
最少操作次数等于这些 (d_j) 在 (\mathbb{F}_2) 上的线性基的维数。

---

6. 算法步骤

1. 找一棵生成树，计算 (val[u])（根到 u 的路径异或和）。
2. 对每条非树边 ((u,v,w)) 计算
   [ d = val[u] \oplus val[v] \oplus w ]
3. 对这些 (d) 建立线性基，维数 (r) 就是最少操作次数。
4. 构造方案：
   • 对线性基的每个基向量 (b)（对应一些非树边的环），我们要消除它。
   • 选一个包含这个环上的树边的集合进行操作，使得这个环的 (d) 变为 0，但不影响其它环。
   • 具体构造常用方法：对每个基向量 (b)，选所有“在某个生成树边上的非树边集合”使得它们异或为 b，然后对应的树边就是操作集合。

---

7. 构造细节

简化构造（已知结论）：

• 对每个基向量 (b)，对应的操作 (X) 就是 (b)。
• 操作边的集合：选择所有“在基向量 (b) 对应的非树边环的交集路径”上的树边，加上这些非树边本身也可以。
• 可以通过 DFS 树将非树边分组。

---

样例验证

样例 1

图是一个四边环： 边：
(1,2,10), (2,3,9), (3,4,8), (4,1,7)

选树：比如 1-2, 2-3, 3-4 是树边，非树边 (4,1,7)。

val[1]=0, val[2]=10, val[3]=10⊕9=3, val[4]=3⊕8=11。
非树边 d = val[4] ⊕ val[1] ⊕ 7 = 11 ⊕ 0 ⊕ 7 = 12。

线性基：{12}，维数=1。

一次操作：X=12，选包含这个环的树边集合：边 1,2,3（前三条边）即可。

---

样例 3

略复杂，但按上述方法可得到维数=2，因此两次操作，符合输出。

---

时间复杂度

• 生成树 DFS：(O(N+M))
• 计算 d 值：(O(M))
• 线性基（最多 30 位）：(O(M \times 30)) 可过
• 构造方案可在同复杂度完成

---

总结

这道题的核心是将环异或条件转化为生成树上非树边对应的环的约束，然后用线性基建模操作的影响，最小操作次数即为这些约束的线性基维数。构造方案需要仔细处理，但思想清晰。