爪图

题目描述

Awerty 是一位巫师，他研究神秘森林中魔法的流动。这片森林可以表示为一个简单无向图 $G=(V, E)$，其中顶点是魔法节点，边是它们之间的通路。每个节点 $v$ 都有一个魔法能量等级，用非负整数 $w_v$ 表示。

Awerty 发现了一种特别强大的魔法结构，他称之为“Y-Graph”（Y形图），它由一个中心节点和它的三个不同的邻居组成。形式上，一个 Y-Graph 是由四个不同的顶点 ${c, v_1, v_2, v_3}$ 和三条边 ${(c, v_1), (c, v_2), (c, v_3)}$ 组成的子图。这种特定的结构也被称为爪形图（claw graph）或 $K_{1,3}$。

单个 Y-Graph 的魔力值（potency）计算为其四个组成节点的能量等级的按位异或和（XOR sum）。对于一个由顶点 ${c, v_1, v_2, v_3}$ 组成的 Y-Graph，其魔力值为：$P = w_c \oplus w_{v_1} \oplus w_{v_2} \oplus w_{v_3}$。其中，$\oplus$ 表示按位异或运算。

Awerty 想要计算整个森林的总魔法能量。为此，他需要求出森林中所有不同的Y-Graph 的魔力值之和。如果两个 Y-Graph 的四个顶点构成的集合不同，或者中心点$c$不同，则认为它们是不同的。

你能帮助 Awerty 完成这项艰巨的任务吗？

输入描述

第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。接下来是 $T$ 个测试用例。

对于每个测试用例：第一行包含两个整数 $N$ 和 $M$ ($1 \le N, M \le 2 \cdot 10^5$)，分别表示图中的节点数和边数。

第二行包含 $N$ 个以空格分隔的整数 $w_1, w_2, \dots, w_N$，其中 $w_i$ 是第 $i$ 个节点的魔法能量 ($0 \le w_i < 2^{60}$)。

接下来的 $M$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le N, u \neq v$)，表示节点 $u$ 和节点 $v$ 之间有一条魔法通路（边）。

保证给定的图是简单的（没有自环，也没有重边）且是无向的。保证所有测试用例中 $N$ 的总和不超过 $2 \cdot 10^5$，且 $M$ 的总和不超过 $2 \cdot 10^5$。

输出描述

对于每个测试用例，输出一行包含一个整数：森林中所有不同的 Y-Graph 的魔力值之和，结果对 $998244353$ 取模。

输入样例

2
5 4
10 1 2 3 4
1 2
1 3
1 4
1 5
4 3
100 200 300 400
1 2
2 3
3 4

输出样例

50
0

提示

按位异或（Bitwise XOR）是指将数值转为二进制后逐位比较，对应位“相同得 0，不同得 1”。例如计算 $5 \oplus 3$：$5$ 的二进制是 $101$，$3$ 的二进制是 $011$，结果的二进制是 $110$（即十进制的 $6$）。