ŠIOM — Lenktynės

Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_2018_2et_lenktynes_vyr.in

Rezultatų failas: lmio_2018_2et_lenktynes_vyr.out

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Lenktynės

Ralio lenktynėse dalyvavo $N$ automobilių. Pasibaigus varžyboms, televizijos operatoriai nori sumontuoti visą nuﬁlmuotą medžiagą. Svarbiausia – jie nori parodyti visus aplenkimus, kurie įvyko lenktynių metu. Tačiau bemontuodami medžiagą operatoriai susimaišė: kaip sužinoti, ar visus aplenkimus jie sumontavo teisinga tvarka?

Užduotis

Jums žinomos pradinės automobilių pozicijos, bei eilė automobilių aplenkimų. Parašykite programą, kuri nustatytų, ar duoti aplenkimai galėjo įvykti tokia tvarka.

Pradiniai duomenys

Pirmoje eilutėje įrašytas automobilių skaičius $N$ , o antroje – automobilių numeriai, įrašyti tokia tvarka, kokia jie startavo (pirmasis startavęs automobilis įrašytas pirmas). Visi automobilių numeriai yra skirtingi sveikieji skaičiai nuo 1 iki $N$ .

Tolimesnėje eilutėje įrašytas lenkimų skaičius $L$ . Toliau pateikta $L$ eilučių kuriose įrašyta po skaičių porą $(a_i,b_i)$ , žyminčią, kad automobilis $a_i$ aplenkė automobilį $b_i$ . Skaičių poros įrašytos tokia tvarka, kokia buvo sumontuota operatorių įraše. Galite būti tikri, kad lenktynių metu įvyko bent vienas lenkimas.

Rezultatai

Jei lenktynės galėjo vykti tokia eiga, kokia yra pateikta, pirmoje eilutėje išveskite žodį TAIP, o antroje – galutinę automobilių tvarką, tokiu pačiu formatu, kaip ir pradiniuose duomenyse.

Jei operatoriai padarė klaidą montuodami, pirmoje eilutėje išveskite žodį NE, o antroje numerį lenkimo, kuris yra neįmanomas (t.y. automobilis $a_i$ negalėjo aplenkti $b_i$ tuo metu).

Pavyzdžiai

Pradiniai duomenys	Rezultatai
3 1 2 3 3 3 2 3 1 2 1	TAIP 3 2 1
3 1 2 3 3 3 2 2 1 3 1	NE 2

Ribojimai