100 #P1402. *【差分约束】判断约束系统是否有解

*【差分约束】判断约束系统是否有解

【题意】

数轴上有 nn 个点,每个点的位置为 XiX_i

给出 mm 条约束信息。每条信息为以下两种形式之一:

  • P a b cP \ a \ b \ c ,表示 XbXa=cX_b-X_a=c
  • V a bV \ a \ b ,表示 Xb>XaX_b>X_a

问是否可能存在符合以上 mm 个要求的 nn 个点。

【输入格式】

多组数据,每组数据描述如下:

第一行两个整数 n mn \ m1n1000,1m1051 \le n \le 1000,1 \le m \le 10^5)。

下来 mm 行,每行输入 P a b cP \ a \ b \ c 或者 V a bV \ a \ b1a,bn1 \le a,b \le n)。

n=0n=0 时结束。

【输出格式】

若存在这样的点则输出 Reliable ,不存在输出 Unreliable

【样例输入】

3 4
P 1 2 1
P 2 3 1
V 1 3
P 1 3 1
5 5
V 1 2
V 2 3
V 3 4
V 4 5
V 3 5
0

【样例输出】

Unreliable
Reliable