U228905 [NOIP 模拟赛] 数学验算 (mathematics)

Alice 和 Bob 正在研究一个复杂的数学问题，这道题中有 $N$ 个参数 $X_1$ 到 $X_n$。Alice 会依次根据条件求出这些变量之间的 $M$ 个关系式。每一条关系式都是形如 $“X_{a_i}-X_{b_i}=c_i”$ 的等式。 由于题目过于复杂，Alice 的求解过程也难免出现一些错误，因此，她需要 Bob 帮忙验算。然而，Bob 很懒，只想利用想 Alice 推出的关系式互相验证，规则如下： - 若第 $i$ 个式子与前 $i-1$ 个式子中**全部**有效的式子**均不矛盾**，则将这个式子视为有效。 - 若第 $i$ 个式子与前 $i-1$ 个式子中**某些**有效的式子**矛盾**，则将这个式子视为无效。 由于参数数量和式子数量太多，Bob 找你帮忙按照他的规则为 Alice 验算。

第一行两个正整数 $N,M$。 接下来 $M$ 行，每行三个整数 $a_i,b_i,c_i$，表示第 $i$ 个式子$“X_{a_i}-X_{b_i}=c_i”$。

输出一行一个长度为 $M$ 的字符串，规则如下： 若第 $i$ 个式子被判做有效，则输出大写字母$“R”$。 若第 $i$ 个式子被判做无效，则输出大写字母$“W”$。

【输入输出样例 $1$】 见选手目录下的 $mathematics/mathematics1.in$ 和 $mathematics/mathematics1.ans$。 【样例 $1$ 解释】 对于第 $1$ 个式子，由于先前没有任何式子，所以一定判做有效。 对于第 $2$ 个式子，$X_2-X_3=2$ 和 $X_1-X_2=1$ 不矛盾，所以第二个式子判做有效。 对于第 $3、4$ 个式子，第 $1、2$ 个式子相加得：$X_1-X_3=3$。所以第三个式子与前两个式子矛盾，判做无效。第四个式子与前两个式子不矛盾，判做有效。 【输入输出样例 $2$】 见选手目录下的 $mathematics/mathematics2.in$ 和 $mathematics/mathematics2.ans$。 【样例 $2$ 解释】 第 $1$ 个式子判做有效。 第 $2$ 个式子和第 $1$ 个式子矛盾，判做无效。 第 $3$ 个式子判做有效。 第 $4$ 个式子和第 $1、3$ 个式子矛盾，判做无效。 第 $5$ 个式子判做有效。 第 $6$ 个式子和第 $1、5$ 个式子矛盾，判做无效。 第 $7$ 个式子判做有效。 第 $8$ 个式子与第 $1、3、5、7$个式子矛盾，判做无效。 【输入输出样例 $3$】 见选手目录下的 $mathematics/mathematics3.in$ 和 $mathematics/mathematics3.ans$。 【输入输出样例 $4$】 见选手目录下的 $mathematics/mathematics4.in$ 和 $mathematics/mathematics4.ans$。 【输入输出样例 $5$】 见选手目录下的 $mathematics/mathematics5.in$ 和 $mathematics/mathematics5.ans$。 【数据范围约定】 | 测试点编号 | $N\le$ | $M\le$ | 特殊性质 | | :----------: | :----------: | :----------: | :----------: | | $1\sim3$ | $10$ | $15$ | 无 | | $4\sim6$ | $2000$ | $4000$ | 无 | | $7$ | $3\times10^5$ | $5\times10^5$ | 所有 $a_i+1=b_i$ | | $8\sim10$ | $3\times10^5$ | $5\times10^5$ | 无 | 对于全部数据，$1\le N\le3\times10^5,1\le M\le5\times10^5,-10^{18}\le\sum_{i=1}^Mc_i\le10^{18}$。 【说明】 由于样例 $5$ 过大，本题只能上传前 $4$ 组样例，第 $5$ 组放在测试数据中。