7276번 - Lenktynės 다국어

문제

Ralio lenktynėse dalyvavo N automobilių. Pasibaigus varžyboms, televizijos operatoriai nori sumontuoti visą nufilmuotą 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?

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

입력

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.

출력

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).

제한

• 1 < N ≤ 1 000
• 1 ≤ L ≤ 100 000

힌트