AT_soundhound2018_summer_qual_e + Graph

kenkoooo 捡到了一张有 $n$ 个顶点 $m$ 条边的简单连通图。图中的顶点编号为 $1$ 到 $n$，第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。此外，第 $i$ 条边上有一个整数 $s_i$。 kenkoooo 想要在每个顶点上写下一个正整数，使得满足以下条件： - 对于任意一条边 $i$，顶点 $u_i$ 和 $v_i$ 上写的正整数之和等于 $s_i$。 请你计算，满足条件的正整数写法有多少种。

输入通过标准输入给出，格式如下： > $n$ $m$ > $u_1$ $v_1$ $s_1$ > $u_2$ $v_2$ $s_2$ > $\vdots$ > $u_m$ $v_m$ $s_m$

输出满足条件的正整数写法的方案数。

### 限制条件 - $2 \leq n \leq 10^5$ - $1 \leq m \leq 10^5$ - $1 \leq u_i < v_i \leq n$ - $2 \leq s_i \leq 10^9$ - 当 $i \neq j$ 时，$u_i \neq u_j$ 或 $v_i \neq v_j$ - 图是连通的 - 输入均为整数 ### 样例解释 1 如果在顶点 $1,2,3$ 上分别写下 $1,2,3$，则满足条件。除此之外，没有其他满足条件的写法，因此答案为 $1$。 ### 样例解释 2 设顶点 $1,2,3,4$ 上写的数分别为 $a,b,c,d$，满足条件的 $(a,b,c,d)$ 共有如下 $3$ 组： - $(a,b,c,d) = (1,5,2,3)$ - $(a,b,c,d) = (2,4,3,2)$ - $(a,b,c,d) = (3,3,4,1)$ 由 ChatGPT 4.1 翻译