{**
 * Przykladowe rozwiazanie zadania dzialajace w czasie prawie liniowym.
 *}
program wp10zad4;

const
    PIERWSZA = 'a';
    OSTATNIA = 'z';

type
    Kolor = (BIALY, SZARY, CZARNY);
    Lilista = ^WezelLilisty;
    WezelLilisty = record
        glowa, ogon, reprezentant : Lilista;
        ranga : Integer;
        znacznik : Kolor        
    end;

var l1, l2, mojNil : Lilista;
    zmienne : array [PIERWSZA .. OSTATNIA] of Lilista;
    c : Char;

function nowy(glowa, ogon : Lilista) : Lilista;
var wynik : Lilista;
begin
    new(wynik);
    wynik^.glowa := glowa;
    wynik^.ogon := ogon;
    wynik^.reprezentant := wynik;
    wynik^.ranga := 0;
    wynik^.znacznik := BIALY;
    nowy := wynik
end;

function jestZmienna(l : Lilista) : Boolean;
begin
    jestZmienna := ((l^.glowa = nil) and (l^.ogon = mojNil))
end;

function jestNiepusta(l : Lilista) : Boolean;
begin
    jestNiepusta := (l^.glowa <> nil)
end;

procedure znajdz(var l : Lilista);
begin
    if l <> l^.reprezentant then begin
        znajdz(l^.reprezentant);
        l := l^.reprezentant
    end
end;

procedure polacz(l1, l2 : Lilista);
begin
    if l1^.ranga < l2^.ranga then
        l1^.reprezentant := l2
    else begin
        l2^.reprezentant := l1;
        if l1^.ranga = l2^.ranga then
            inc(l1^.ranga)
    end
end;

function wczytaj : Lilista;
var w : Lilista;
    c : Char;
begin
    if eoln then
        wczytaj := mojNil
    else begin
        read(c);
        if c = ')' then
            wczytaj := mojNil
        else begin
            if c in [PIERWSZA .. OSTATNIA] then begin
                if zmienne[c] = nil then
                    zmienne[c] := nowy(nil, mojNil);
                w := zmienne[c]
            end else begin
                assert(c = '(');
                w := wczytaj()
            end;
            wczytaj := nowy(w, wczytaj())
        end
    end
end;

procedure wypisz(l : Lilista);
begin
    znajdz(l);
    if jestNiepusta(l) then begin
        write('(');
        wypisz(l^.glowa);
        write(')');
        wypisz(l^.ogon)
    end
end;

procedure usun(l : Lilista);
begin
    if jestNiepusta(l) then begin
        usun(l^.glowa);
        usun(l^.ogon);
        dispose(l)
    end
end;

function jestCykl(l : Lilista) : Boolean;
begin
    znajdz(l);
    if jestNiepusta(l) and (l^.znacznik = BIALY) then begin
        l^.znacznik := SZARY;
        if jestCykl(l^.glowa) then
            jestCykl := true
        else
            jestCykl := jestCykl(l^.ogon);
        l^.znacznik := CZARNY
   end else
       jestCykl := (l^.znacznik = SZARY)
end;

function prawieUzgadnialne(l1, l2 : Lilista) : Boolean;
begin
    znajdz(l1);
    znajdz(l2);
    if l1 = l2 then
        prawieUzgadnialne := true
    else if jestZmienna(l1) or jestZmienna(l2) then begin
        prawieUzgadnialne := true;
        if jestZmienna(l1) then
            l1^.reprezentant := l2
        else
            l2^.reprezentant := l1
    end else if jestNiepusta(l1) and jestNiepusta(l2) then begin
        if not prawieUzgadnialne(l1^.glowa, l2^.glowa) then
            prawieUzgadnialne := false
        else
            prawieUzgadnialne := prawieUzgadnialne(l1^.ogon, l2^.ogon);
        polacz(l1, l2)
    end else
        prawieUzgadnialne := false
end;

begin
    while not eof do begin
        mojNil := nowy(nil, nil);
        for c := PIERWSZA to OSTATNIA do
            zmienne[c] := nil;
        l1 := wczytaj;
        readln;
        l2 := wczytaj;
        readln;
        if prawieUzgadnialne(l1, l2) then
            if not jestCykl(l1) then begin
                wypisz(l1);
                writeln
            end else
                writeln('nie')
        else
            writeln('nie');
        usun(l1);
        usun(l2);
        for c := PIERWSZA to OSTATNIA do
            if zmienne[c] <> nil then
                dispose(zmienne[c]);
        dispose(mojNil)
    end
end.
