Igualtats i desigualtats P35144

Statement

Tenim un conjunt de variables que prenen valors naturals. Ens van arribant restriccions de la forma $x = y$ , $x = a$ i $x \ne a$ , on $x$ i $y$ són variables i $a$ és un nombre natural. Hi ha solució per al sistema format per totes les restriccions? I si no n’hi ha, a partir de quin moment és irresoluble?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb $n$ , el nombre de restriccions del sistema. A continuació vénen les $n$ restriccions. Els noms de les variables són paraules amb lletres minúscules i dígits que comencen amb una lletra. Podeu assumir $1 \le n \le 10^5$ i $0 \le a \le 10^9$ .

Sortida

Per a cada cas, si el sistema format per totes les restriccions té alguna solució, escriviu “yes”. Altrament, indiqueu després de quantes restriccions el sistema ja no té solució.

Public test cases

Input

3
x == 0
x == 0
x != 1

2
x == 0
x == 1

3
x == 1
x != 1
x == 2

2
x != 0
x != 1

2
x != 0
x == 0

3
hola == adeu
hola == 0
adeu != 0

3
hola42hola == 0
adeu23adeu == 1
hola42hola == adeu23adeu

6
a != 100
a != 200
b != 100
b == 200
b == a
b == 300

3
x == x
x == y
y == x

Output

yes
no from 2
no from 2
yes
no from 2
no from 3
no from 3
no from 5
yes

Information

Author: Enric Rodriguez
Language: Catalan
Official solutions: C++
User solutions: C++