1422 - 等式方程的可满足性

通过次数

4

提交次数

15

时间限制 : 1 秒
内存限制 : 128 MB

给定一个由表示变量之间关系的字符串方程组成的数组,每个字符串方程 equations[i] 的长度为 4,并采用两种不同的形式之一:"a==b""a!=b"。在这里,a 和 b 是小写字母(不一定不同),表示单字母变量名。

只有当可以将整数分配给变量名,以便满足所有给定的方程时才返回 true,否则返回 false

输入

第一行为1个整数,表示 equations 的长度

以下n行,每行为1个字符串,表示 equations 的内容

输出

如果将整数分配给变量名后,能够满足所有给定方程,输出true,否则输出false

样例

输入

2
a==b
b!=a

输出

false

输入

2
a==b
b==a

输出

true

输入

3
a==b
b==c
c==a

输出

true

提示

  1. 1 <= equations.length <= 500

  2. equations[i].length == 4

  3. equations[i][0]equations[i][3] 是小写字母

  4. equations[i][1] 要么是 '=',要么是 '!'

  5. equations[i][2]'='