不妨设 $G$ 连通。在此前提下无自环，容易从 $u$ 走一个 $2a_i$ 的来回使得任意自环的 $b$ 都可以被满足。考虑每条边经过 $x_i$ 次合法的条件是存在欧拉路径，即有 $0/2$ 个点度数为奇数，且图连通。发现图连通的限制可以对任意 $x_i$ 加上 $2a_i$ 而不改变 $b$ 来满足，那么只剩下度数限制。

对于 $a_i\bmod 2=1$ 的边，可以任意决策是否加上，那么影响就是反转端点的度数奇偶性，此时 $b$ 就是不重要的，可以任意取。反之 $a_i\bmod 2=0$ 的边就只由 $b_i$ 来决定对端点的修改。将 $a_i\bmod 2=1$ 的边连起来，会形成若干极大的连通块。我们只关心一整个连通块的度数和的奇偶性。此时 $a_i\bmod2=0$ 的边会反转 $u,v$ 所属连通块的奇偶性。

而 $a_i\bmod 2=0,b_i\bmod2=0/1$ 的数量是相同的，所以不需要区分奇偶的选边权值。端点在同一个连通块也是任取。那么原图合法就要求，度数和为奇数的连通块为 $0/2$ 个。问题转化为给定一张连通图 $G$，有若干边（代表原图 $a_i\bmod2=0$ 连接的两个连通块），求选边子集的方案数使得至多两个点度数为奇数的方案数。

考虑 dfs 生成树，那么如果有 $2$ 个奇数就可以反转树上的路径变成全偶。对于全偶的方案数乘以 $\binom{|V|}{2}+1$ 即可。在 dfs 生成树中，对于非树边任意决策，树边的选取情况可以从下往上递推，显然可以保证根节点度数为偶。方案数即为 $2^{|E|-|V|+1}(\binom{|V|}{2}+1)$。

注意全 $0$ 会被多算。时间复杂度 $O(n+m)$。