丈量扰动

哨兵布好了，但进入Zero核心的路不止一条——废墟里通道交错，像迷宫。

"每条路有不同的扰动。"你说，"电磁干扰、辐射、信号噪声。"

"那咋走？"

"算期望。"你说，"从入口到核心，随机走。每一步选一个邻居，概率均等。"

"随机？那不是送死？"

"不是。"你说，"我们要算的是——平均扰动值。"

"异或和。"Echo说，"每条边有一个扰动值。走一条路径，所有边的扰动异或起来。"

"异或？"

"对。"你说，"相同抵消，不同保留。随机游走，求到达终点的期望异或值。"

"期望异或？"

"按位独立。"你说，"异或的每一位独立。算第$k$位为1的概率，然后累加。"

"咋算概率？"

"高斯消元。"你说，"设$p_u$为从$u$出发，第$k$位最终为1的概率。"

"$p_u=\sum_{v} \frac{1}{deg(u)} \times (p_v \text{ if edge bit k}=0 \text{ else } 1-p_v)$。"

"如果边的第$k$位是0，异或不变；如果是1，异或翻转。"

"对。"

你开始写。对每一位建方程组，高斯消元。

"第0位。"你说，"从入口到核心，概率0.47。"

"第1位。"你说，"概率0.33。"

"……"

"期望异或值。"你说，"$0.47\times 2^0 + 0.33\times 2^1 + \dots = 47$。"

"又是47。"

"对。"你说，"47。"

CC看着你屏幕上密密麻麻的方程——像某种古老的星图。

"我看不懂。"她说，"但47我认得。"

"47是我们的数。"你说，"每次到最后，都是47。"

"47是啥？"

"是希望。"Echo说，"47%的概率，47个节点，47步归途。"

"47%不够。"CC说，"我要100%。"

"100%不存在。"你说，"但我们可以逼近。"

"咋逼近？"

"继续走。"你说，"下一步——叠垒残骸。"

题目描述

给定一个无向图，每条边有一个权值。从点1随机游走（每次等概率选邻居），求到达点$n$的路径异或和的期望。

输入格式

$n,m$。然后$m$条边$u,v,w$。

输出格式

期望异或和。

输入样例

3
1 2 3

输出样例

0.000

提示

• 按位独立。对每一位分别计算。
• 设$p_u$为从$u$出发该位最终为1的概率。
• $p_u = \sum_{v} \frac{1}{deg(u)} \times (p_v \text{ if } w_{uv}\text{ bit }k=0 \text{ else } 1-p_v)$。
• 高斯消元求解。