Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Mint tudjátok a jelenlegi járványügyi helyzetben a világon sok-sok fesztivál szervezését lemondták. Létezik azonban egy fesztivál, amelyet minden évben megtartanak egy a számotokra jól ismert oroszországi kisvárosban, és amelyet a szervezők mindentől függetlenül megtartanak az idén is. Tekintettel arra, hogy ezen a nyáron más lehetőségetek nem igazán lesz, elhatároztátok, hogy részt vesztek a világhírű Intervallum fesztiválon.
Ezen a fesztiválon minden attrakciót egy intervallum képvisel a számegyenesen. Valamilyen bizarr geometria miatt, amely Oroszország valamilyen rejtett, homályos területein jelentkezik, tudjuk, hogy két attrakció csak akkor szomszédos, ha egyikükhöz tartozó intervallum részintervalluma a másik attrakcióhoz tartozó intervallumnak. Emlékeztetünk titeket, hogy \([a,b]\) intervallum akkor részintervalluma a \([c,d]\) intervallumnak, ha érvényes, hogy \(c\leq a\leq b\leq d\).
Azt nem tudjátok, hogyan fogtok mozogni a fesztiválon, ezért az adott \(u\) és \(v\) attrakciók esetére érdekel titeket, hogy mekkora a legrövidebb út az \(u\) attrakciótól a \(v\) attrakcióig, vagyis, hogy mennyit kell utazni a szomszédos attrakciók között, hogy eljussatok az \(u\) attrakciótól a \(v\)-ig. Nagyon izgatottak vagytok a fesztiválon való részvételetek miatt, és szeretnétek megtudni a választ az előző kérdésre nem is egy, hanem \(Q\) számú attrakciópár \((u,v)\) esetében!
A szabványos bemenet két számot tartalmaz: az intervallumok számát (\(N\)), és a lekérdezések számát (\(Q\)).
A szabványos bement második sora az \(A_i\) sorozatot tartalmazza \(2\cdot N\) számmal, ahol az \(\{1,2,\ldots,N\}\) halmaz minden eleme kétszer fordul elő. Az \(i\) szám első előfordulásának indexe az \(i\) intervallum kezdetét jelöli, míg az \(i\) szám második előfordulásának indexe az \(i\) intervallum végét jelöli.
A szabványos bemenet következő \(Q\) sorának mindegyikében két természetes szám található: \(u_i,v_i\). Ezek a számok azoknak az attrakcióknak az indexét adják, amelyek között a legrövidebb utat keressük.
A szabványos kimeneten kiíratni \(Q\) sort. Az \(i\)-edik sorban az \(i\)-edik lekérdezésre álljon a válasz.
3 2
3 1 2 1 2 3
2 3
1 21
2\(2\)-től \(3\)-ig közvetlenül eljuthatunk, mert a \(2\)-es számú attrakció intervalluma részintervalluma a \(3\)-as számú attrakció intervallumának. Az \(1\)-es és \(2\)-es számú intervallumok nem szomszédosak, ezért közöttük a legrövidebb út az \(1-3-2\).
A tesztfeladatok 4 alfeladatra oszthatók: