Zadovoljivost jednakosti

Dato je skup od \(n\) jednačina oblika a == b ili a != b. Ispitati da li je taj skup jednačina zadovoljiv ili nije. Skup jednačina je zadovoljiv ukoliko je moguće dodeliti vrednosti promenljivama tako da sve jednačine budu zadovoljene. Ukoliko takva dodela ne postoji, onda je skup jednačina nezadovoljiv.

Ulaz

Sa standardnog ulaza se učitava ceo broj \(n\) (\(1 \leq n \leq 350\)), a zatim i \(n\) jednačina oblika <var1> == <var2> ili <var1> != <var2>. Ime promenljive <var> je iz skupa malih slova engleske abecede \(\{a, b, \ldots, z\}\) (\(|\{a, b, \ldots, z\}| = 26\)).

Izlaz

Na standardni izlaz ispisati SAT ukoliko je skup jednačina zadovoljiv, inače ispisati UNSAT.

Primer

Ulaz

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

Izlaz

UNSAT

Objašnjenje

Iz prve dve jednačine \(a\), \(b\) i \(c\) moraju uzeti istu vrednost. Tada nije zadovoljena poslednja jednačina \(a != c\).

Primer

Ulaz

4
a == b
b == c
a == c
d != e

Izlaz

SAT

Objašnjenje

Iz prve tri jednačine \(a\), \(b\) i \(c\) moraju uzeti istu vrednost. Iz poslednje jednačine \(d\) i \(e\) moraju biti različiti. Zbog toga postoji dodela tako da su sve jednačine zadovoljene. Na primer, to može biti \(a := 1\), \(b := 1\), \(c := 1\), \(d := 2\) i \(e := 3\).

Опис улаза

Опис излаза

Решење

#include <iostream>

using namespace std;

int main() 
{

    return 0;
}