1422 - 等式方程的可满足性

给定一个由表示变量之间关系的字符串方程组成的数组,每个字符串方程 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]'='

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题