Gigel este mare fan al muzicii anilor 70. El are o colecţie impresionantă de benzi magnetice cu melodiile compuse în acea perioadă. Tehnica folosită în acea perioadă poate părea rudimentară în zilele noastre, însă Gigel doreşte să reconstituie cât mai mult din atmosfera epocii.
Fiecare melodie este înregistrată pe o bandă magnetică; benzile sunt numerotate de la 1 la N. Fiecare bandă este înfăşurată pe câte o rolă din plastic, iar Gigel mai dispune de o rolă goală. Rolele sunt numerotate de la 0 la N, fiecare bandă avându-şi locul pe rola cu acelaşi număr, iar rola 0 fiind rola goală.
Când Gigel ascultă o melodie, magnetofonul derulează banda de pe rola ei şi o înfăşoară pe rola goală; la final banda se găseşte pe rola ce iniţial era goală, bobinată invers, adică cu începutul benzii în centrul rolei, iar rola pe care se găsea iniţial banda devine goală. Gigel are întotdeauna grijă ca, după ce ascultă o melodie, să rebobineze banda înapoi pe rola ei. Fratele mai mic al lui Gigel este mai dezordonat şi lasă adesea banda pe rola pe care ajunge în urma ascultării. El foloseşte apoi rola proaspăt eliberată pe post de rolă goală pentru a asculta următoarea melodie. Astfel, după o vreme, multe dintre benzi se găsesc pe altă rolă decât cea proprie, şi unele benzi sunt bobinate invers, adică inceputul melodiei este în interiorul înfăşurării (trebuind derulate înainte de-a putea fi ascultate).
Gigel doreşte acum să restabilească ordinea, aducând fiecare bandă pe rola ei şi bobinată cu începutul în exterior. În acest scop el poate executa o secvenţă de operaţii. La o operaţie el poate doar să ia o rolă şi să deruleze banda de pe ea pe singura rolă ce este goală în acel moment, banda inversându-şi cu această ocazie sensul de bobinare.
Cerinţă
Se cere să se determine o secvenţă minimă de operaţii în urma cărora fiecare bandă ajunge pe rola cu numărul egal cu numărul benzii şi înfăşurată cu începutul în exterior.
Date de intrare
Fişierul de intrare role.in va conţine pe prima linie un număr natural N reprezentând numărul de benzi. Pe următoarele N linii se găsesc câte două numere naturale separate printr-un spaţiu, R şi I. A k-a pereche descrie poziţia benzii cu numărul k: R reprezintă numărul rolei pe care se află banda k, iar I are valoarea 0 dacă banda este înfăşurată normal (cu începutul în exterior) şi 1 dacă este înfăşurată invers.
Date de ieşire
Fişierul de ieşire role.out va conţine o secvenţă de numere naturale, câte un număr pe o linie pe linie. Numărul de pe linia i reprezentă numărul rolei de pe care se mută banda pe rola goală la cea de a i-a operaţie executată.
Restricţii
1 ≤ N ≤ 100000
Pe o rolă poate exista cel mult o bandă la un moment dat.
Pentru toate datele de test va exista o soluţie care necesită cel puţin o operaţie. Punctaj. Pentru soluţie optimă se acordă 100% din punctaj.
Dacă soluţia nu este optimă, dar este corectă, se vor acorda punctaje parţiale după cum urmează:
1. dacă diferenţa dintre numărul de operaţii executate de concurent şi numărul optim de operaţii este mai mică sau egală decât 10% din numărul optim (parte întreagă), se acordă 60% din punctaj;
2. dacă diferenţa dintre numărul de operaţii executate de concurent şi numărul optim de operaţii este mai mare decât 10% din numărul optim (parte întreagă), se acordă 20% din punctaj.