染色

设一条边的两个端点颜色相同时有 $s$ 种染法，不同时有 $d$ 种染法。整张图的方案数就是对所有点染色求边权乘积之和。

本题的数据分成两类：$n\le12$ 时图可能较密；$n>12$ 时图很稀疏，最大的非树边数量只有约 $10$。因此分别处理即可。

先做一个统一的化简。若同一对点之间有多条重边，因为这些边看到的“端点是否同色”完全相同，所以可以直接合并：新的 $s$ 是所有 $s_i$ 的乘积，新的 $d$ 是所有 $d_i$ 的乘积。之后图可以看成简单图，但每条边仍带有一对权值 $(s,d)$。

对于 $n\le12$，直接枚举点颜色形成的集合划分。具体地，用限制增长序列表示一个集合划分：第一个点属于第 $0$ 类，之后每个点可以放进已有颜色类，也可以新开一个颜色类。若最终用了 $r$ 个颜色类，那么这些抽象颜色类映射到实际的 $k$ 种颜色共有$k(k-1)\cdots(k-r+1)$种方式。枚举过程中，每给一个新点确定所属颜色类，就可以立即乘上它与此前所有点之间边的 $s$ 或 $d$。这样只枚举 Bell 数（参考https://oi-wiki.org/math/combinatorics/bell）量级的状态，$B_{12}=4213597$，足够通过所有 $n\le12$ 的数据。

下面考虑 $n>12$ 的稀疏数据。

记当前图的答案为 $Z(G)$。有几种非常有用的局部消元。若一条边满足 $s=d$，它无论两端是否同色都贡献同一个常数 $s$，可以直接把 $s$ 乘入答案并删掉这条边；若点 $v$ 的度数为 $0$，它可以任选一种颜色，因此产生因子 $k$，然后删掉 $v$；若点 $v$ 的度数为 $1$，唯一相邻边权为 $(s,d)$。固定邻点颜色后，$v$ 与其同色有 $1$ 种颜色选择，异色有 $k-1$ 种，因此产生因子$s+(k-1)d$，然后可以把 $v$ 删除。

对度数为 $2$ 的点。设 $v$ 的两个邻点是 $x,y$，两条边权分别为 $(s_1,d_1),(s_2,d_2)$。把 $v$ 的颜色求和后，可以用一条新的 $x-y$ 边完全代替这两条边。若 $x,y$ 同色，新边的同色权为$s'=s_1s_2+(k-1)d_1d_2$；若 $x,y$ 异色，$v$ 可以等于 $x$、等于 $y$，或者与两者都不同，因此新边的异色权为$d'=s_1d_2+d_1s_2+(k-2)d_1d_2$；如果 $x,y$ 原本已经有边，就再按照重边规则把两条边合并。不断进行上述消元后，若图被分成若干连通块，各连通块完全独立，答案直接相乘。

于是只剩下所有点度数都至少为 $3$ 的核。设某个连通块有 $n'$ 个点、$m'$ 条边，圈数为$c=m'-n'+1$。因为最小度至少为 $3$，$3n'\le2m'=2(n'-1+c)$，所以$n'\le2c-2$。在本题的大数据中，原图的 $c=m-n+1$ 最大只有 $10$，而前面的消元不会增大 $c$，因此最后的核至多只有 $18$ 个点。

对这个很小的核使用删除-收缩。任选一条非桥边 $e=(u,v)$，边权为 $(s,d)$。把边权写成$d+(s-d)[c_u=c_v]$，于是有$Z(G)=dZ(G-e)+(s-d)Z(G/e)$，其中 $G/e$ 表示把 $u,v$ 合并为一个点。收缩后出现的重边继续直接合并。选择非桥边有一个好处：删除它会让圈数减少 $1$；收缩它会让点数减少 $1$。再配合前面的度数不超过 $2$ 消元，递归规模非常小。数据还保证随机生成，因此实际递归节点数很少。树的情况根本不会进入删除-收缩：不断删叶子就能直接算完。

复杂度方面，$n\le12$ 时为 Bell 数量级，最大只到 $B_{12}$。对于大数据，设圈数为 $c$，消元后的核只有 $O(c)$ 个点，删除-收缩的复杂度只指数依赖于 $c$；本题 $c\le10$。空间复杂度很小。