Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

Након што је провео цео дан гледајући научнофантастичне филмове, Петар је одлучио да искористи идеје и знање које је из њих покупио и направи механичког пророка, односно машину која одговара на било какво да-не питање које јој се постави.

Након што је направио пророка, Петар му је поставио \(N\) питања и бележио одговоре које је добио. Да не би трошио превише папира, свако питање је скраћено обележио идентификационим бројем (тако да истим бројевима одговара исто питање – Петар је нека питања поставио више пута). Приметио је да су одговори које је добио контрадикторни, тј. да је на нека питања добио и одговор “да” и одговор “не”.

Петар претпоставља да је проблем у неисправној простор-временској ферфуцни, због које пророк на свако \(K\)-то постављено питање одговара супротно од тачног одговора (где \(2 \leq K \leq N\)). Да би могао да почне поправке одмах, уместо да чека да сазна праве одговоре, замолио вас је да нађете најмање \(K\) које одговара овој претпоставци и добијеним одговорима.

Опис улаза

У првом реду стандардног улаза налази се један природан број \(N\) – број питања која је Петар поставио. У наредних \(N\) редова налазе се идентификациони број \(i\)-тог питања \(Q_i\) и одговор који је пророк дао \(A_i\). Све вредности \(A_i\) ће бити или “da” или “ne”.

Опис излаза

У првом и једином реду стандардног излаза исписати \(K\) – најмању вредност “периода” са којим је могуће да пророк греши. Уколико такво \(K\) не постоји, исписати -1.

Примери

<div class="panel panel-default">
    <div class="panel-heading">
        <span class="pull-left" style="width: 48%;">Ulaz</span>
        <span style="padding-left: 15px;">Izlaz</span>
    </div>
    <div class="panel-body">
        <span class="pull-left exampleinput">
            5<br/>
            1 da<br/>
            2 ne<br/>
            1 ne<br/>
            3 da<br/>
            2 ne
        </span>
        <span class="exampleoutput">
            3
        </span>
    </div>
</div>
<div class="panel panel-default">
    <div class="panel-heading">
        <span class="pull-left" style="width: 48%;">Ulaz</span>
        <span style="padding-left: 15px;">Izlaz</span>
    </div>
    <div class="panel-body">
        <span class="pull-left exampleinput">
            3<br/>
            1 da<br/>
            1 ne<br/>
            1 ne
        </span>
        <span class="exampleoutput">
            -1
        </span>
    </div>
</div>

Објашњење примера

У првом примеру, ако су одговори на питања са идентификационим бројевима \(1, 2, 3\) редом “да”, “не” и “да”, одговори пророка су конзистентни ако је на треће постављено питање дао супротан одговор (тј. \(K = 3\)). За \(K = 2\) се не слажу одговори на прво и треће питање (пророк на њих не би одговорио супротно), као ни одговори на друго и пето (пророк би на друго питање одговорио супротно а не пето не би).

Ограничења и подзадаци

Постоје \(3\) подзадатака, у којима додатно важи: