P16930 拱辰封仪

:::info[题目背景] 林间的风依旧缓慢地吹着，树影在地面上交错摇晃，像一层层无声移动的水纹。 菲伦与休塔尔克还坐在那张复杂的路线图旁，为方才那场游戏的胜负低声争论着。 一个神情认真，觉得对方显然是在最后一步犯了错；另一个则皱着眉，坚持说那种走法本来就不可能赢。 这样的小事在漫长的旅途中并不少见，尤其是在被困住之后，能让人暂时忘记焦躁的事情，总归是有价值的。 而芙莉莲没有加入他们。 她安静地站在一旁，目光落在自己先前画下的线路上。 那些看似杂乱无章、不断绕回原点的轨迹，在纸面上重复交错，像是某种刻意隐藏起来的纹样。 对寻常旅人而言，这大概只是一张令人头疼的路线图；可对活过漫长岁月、见过无数古代术式的魔法使而言，很多东西只要重复得足够多，就会暴露出原本的形状。 「原来如此。 」芙莉莲轻声说道。 「哎？」菲伦抬起头。 「这不是单纯让人迷路的结界。 」芙莉莲用指尖轻轻划过纸上的几处交汇点，语气平静，「是把整片森林当作术式基盘来使用的古代迷向术。 我们刚才走过的那些路，并不是在兜圈子，而是在沿着它预设好的魔力回路移动。 」 休塔尔克望着那张几乎看不懂的图，沉默了片刻，最后还是诚实地开口：「虽然听起来很厉害，但我完全没明白。 」 「简单来说，」菲伦替他总结道，「就是这片森林本身就是机关的一部分。 」 「嗯，差不多就是这样。 」芙莉莲合上笔记本，神情里带着一点终于弄清楚麻烦来源的平淡，「既然知道了它的结构，破解起来就不难了。 」 她抬起法杖，杖端亮起柔和的光。 那些原本散布在林间、几乎无法察觉的魔力流向，仿佛在一瞬间被无形的手拨正了位置。 风穿过树梢，枝叶发出轻微的震颤，四周那种若有若无的迟滞感也随之消失不见，像是一张覆盖在森林上的旧网，被人轻轻揭开了一角。 「好了。 」芙莉莲说。 「……这就结束了？」休塔尔克愣住。 「嗯。 」 她答得理所当然，仿佛只是顺手拍掉了肩上的一片落叶。 还没等两人彻底反应过来，芙莉莲便已经将飞行魔法展开。 淡金色的魔力在三人脚下浮起，如同安静托起水面的微光。 下一刻，他们离开了潮湿阴暗的林地，穿过层层叠叠的树冠，向森林上空缓缓升起。 视野豁然开朗。 从高处俯瞰下去，先前困住他们的森林像一片深绿色的海，枝叶连绵起伏，一直铺展到群山的边缘。 而在这片广袤林海的正中央，「沉星书库」正静静坐落其间。 那是一座古老得近乎失去年代感的建筑。 高耸的灰白色外墙在天光下泛着冷淡的光泽，穹顶与尖塔彼此交叠，像是将星空凝固后垒砌而成。 即使隔着这样一段距离，也依旧能感受到那股沉静而深远的魔力，仿佛千百年来，它都只是安静地立在那里，等待真正能够抵达此处的人。 但书库的周围，并非毫无阻拦。 环绕在「沉星书库」四周的，是一座座彼此呼应的古代机关。 它们有的像嵌入地面的石柱，有的像悬浮在半空中的环状碑盘，还有一些则只是分布在林海之间、闪烁着微弱辉光的术式节点。 它们共同构成了一重庞大而精密的封锁结构，如同群星拱卫月轮，将整座书库严密地守护在中央。 「那是什么？」菲伦轻声问。 芙莉莲看了一会儿，才缓缓开口。 「是『拱辰封仪』。 」她说，「古代魔法使很喜欢这种布置方式。 把多个独立的术式节点散布在目标周围，让它们彼此呼应、互相补全。 只要封仪还维持着完整的联结，外来者就无法真正靠近核心区域。 」 休塔尔克皱起眉，看着下方那一片密密分布的机关：「也就是说，想进『沉星书库』，还得先把这些东西处理掉？」 「嗯。 」芙莉莲点了点头，「不过不需要全部破解。 」 她的目光在那些机关之间缓缓移动，像是在无声地计算着什么。 风从高空掠过，吹动她银白色的长发，也吹得法袍边角轻轻扬起。 片刻之后，她抬起手，指向其中几处位置。

森林里一共有 $n$ 个「拱辰封仪」，编号为 $1\sim n$。 部分「拱辰封仪」之间存在「魔力通道」，这些「魔力通道」构成一张无向简单图。 此外，每个「拱辰封仪」 $i$ 都有一个魔法值 $a_i$。 如果两个不同的「拱辰封仪」 $x,y$ 之间**存在**一条长度为**奇数**的**路径**，那么这两个「拱辰封仪」无法被同时破坏，如果同时破坏掉会造成魔力紊乱。 请注意，这里的**路径**的定义是一组顶点 $\{v_1, v_2, \dots, v_t\}$，对于任意 $i\in[1, t)$，$v_i$ 与 $v_{i+1}$ 之间存在一条边。 顶点可以重复，换句话说，**路径**允许经过重复的点或边，**路径**的长度定义为经过的边的数量，也就是 $t-1$。 为了解锁「沉星书库」，芙莉莲需要从这 $n$ 个「拱辰封仪」中选出恰好 $k$ 个破坏，而不造成魔力紊乱。 这对于芙莉莲而言简直轻而易举，很快她想出了一个新的花样。 定义： - $E$ 为恰好选出 $k$ 个「拱辰封仪」，且所选「拱辰封仪」魔法值之和为偶数的方案数； - $O$ 为恰好选出 $k$ 个「拱辰封仪」，且所选「拱辰封仪」魔法值之和为奇数的方案数。 芙莉莲想知道 $E^2 - O^2$ 对 $998244353$ 取模后的结果。 此外，空集视为合法，若 $k=0$，其魔法值之和视为 $0$。

第一行包含三个整数 $n,m,k(1\leq n\leq 3\times 10^5, 0\leq m\leq 3\times 10^5, 0\leq k\leq n)$，分别表示「拱辰封仪」的数量、「魔力通道」的数量和需要破坏的数量。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n(-10^9\leq a_i\leq 10^9)$，表示每个「拱辰封仪」的魔法值。 接下来 $m$ 行，每行包含两个整数 $u,v(1\leq u,v\leq n, u\neq v)$，表示「拱辰封仪」 $u$ 与「拱辰封仪」 $v$ 之间存在一条无向「魔力通道」。 输入保证没有重边与自环。

输出一行一个整数，表示 $E^2 - O^2$ 对 $998244353$ 取模后的结果。

对于样例一，需要在 6 个「拱辰封仪」选择 3 个破坏，不难发现 $\{1, 2\}$ 与 $\{2, 3\}$ 由于存在长度为奇数的路径而不能被同时选择，因此在 $\{1, 2, 3\}$ 这个连通块内，只能选择 $\{1, 3\}$ 或其他单点； 在 $\{4, 5, 6\}$ 这个连通块内，选择任意两个「拱辰封仪」都会存在长度为奇数的路径，因此只能单点选择； 综上，合法的方案为 $\{1, 3, 4\}$、$\{1, 3, 5\}$与$\{1, 3, 6\}$，魔法值之和分别为 8、9、10，则$E=2, O=1$，$E^2-O^2=3$。 对于样例二，不难看出只有 $\{1, 3\}$ 与 $\{2, 4\}$ 是合法的方案，魔法值之和分别为 3、3，则 $E=0, O=2$，$E^2-O^2=-4 \equiv 998244349 \pmod{998244353}$。