1050. Satisfiability of Equality Equations

Given equations of the form "a==b" or "a!=b" over single lowercase-letter variables, determine whether it is possible to assign values so that all equations hold. Return true or false. The input is JSON {equations}.

Input: JSON {equations}.

Output: Boolean — true or false.

Examples

Input: {"equations":["a==b","b!=a"]}
Output: false
Explanation: Contradiction.

Input: {"equations":["a==b","b==c","a==c"]}
Output: true
Explanation: Consistent equalities.

Input: {"equations":["a!=a"]}
Output: false
Explanation: A variable cannot differ from itself.

Constraints

• 1<=equations<=500
• single lowercase letters

Asked by