#P3266. 图上方程组
图上方程组
图上方程组
题目描述
给定一张无向图 和一个质数 。在每条边的两个方向上定义 三个权值。已知 ,求 。保证每条边的 均不等于 。
每个节点 满足
$$\sum_{q:\,\{v,q\}\in\mathcal E} C(v,q)\equiv0\pmod P .$$对每条回路 ,其中 ,要求
$$\sum_{i=0}^{k-1} B(v_i,v_{i+1})\,C(v_i,v_{i+1}) \equiv \sum_{i=0}^{k-1}A(v_i,v_{i+1})\pmod P .$$同一条边的两个方向满足
$$\begin{aligned} A(u,v)&\equiv-A(v,u)\pmod P,\\ B(u,v)&\equiv B(v,u)\pmod P,\\ C(u,v)&\equiv-C(v,u)\pmod P. \end{aligned}$$输入格式
第一行三个整数 ,表示节点数、边数和模数。节点编号从 到 。
接下来 行,每行四个整数 ,表示一条连接 与 的无向边,,。反向权值按题目中的关系确定。没有重边或自环。
输出格式
若无解,输出一行 -1。有解时可以输出任意一组解。按输入顺序输出 行,第 行是对应输入方向上的 在 中的代表值。
样例
3 3 7
1 2 15 -6
2 3 22 8
3 1 1 -69
1
1
1
数据规模与约定
,,。