루미 알고리즘

#1367플래티넘Portaler

PO 2015 온라인 예선코딩출제 Bjarki Ágúst Guðmundsson, Simon Lindholm, Oskar Werkelin Ahlin스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Det nya företaget Sveriges Portaltrafik vill revolutionera hur svenska pendlare tar sig runt i landet. Företaget har lagt fram ett banbrytande förslag på hur ett portalsystem ska byggas i Sverige, för att ersätta tåg, flyg och busstrafik med bränslesnåla portaler. Regeringen har nu fått i uppdrag att granska förslaget i detalj, och vädjar till svenska elitprogrammerare om hjälp. Det är här du kommer in i bilden.

Du har fått ta del av en ritning av portalsystemet för att analysera det. Portalsystemet består av N portaler utplacerade på olika platser i landet. Varje portal a har en viss destinationsportal b. Det betyder att varje gång man går in i a så kommer man ut ur b. Notera att man inte nödvändigtvis kommer tillbaka till a när man går in i b. Sveriges Portaltrafiks nya idé är att genom att låta resenärer gå i en portal och sedan upprepade gånger gå in i portalen man dyker upp vid så kommer man snabbt kunna ta sig runt i landet.

Regeringen vill nu veta för ett antal givna start- och slutportaler a och b hur många gånger man behöver gå in i portalen man dyker upp vid för att ta sig från a till b – eller om det ens är möjligt. För varje sådan förfrågning ska du svara med antalet gånger man behöver gå in i portalerna för att ta sig från a till b. Om det är omöjligt så ska du svara -1.

Hjälp regeringen!

Input

På första raden i indata står heltalet N, antalet portaler som kommer att placeras ut i landet. Sedan följer N rader med tal 1 ≤ d_i ≤ N som beskriver att portalen på rad i leder till portal d_i. Portalerna är ett-indexerade (den lägsta har nummer 1, den högsta har nummer N), och kommer i ordning från 1 till N i indata.

Sedan följer en rad med ett heltal Q, antalet förfrågningar som du måste svara på. Efter det följer Q rader med två heltal 1 ≤ s, e ≤ N. Dessa tal beskriver nummer på en startportal s och en slutportal e, och ditt uppdrag är att svara på hur många gånger man behöver gå igenom portalerna för att ta sig till e när man börjar vid s. För varje förfrågan gäller s ≠ e.

Output

Du ska skriva ut Q rader, ett tal per förfrågan: antalet gånger man behöver gå igenom portalerna för att ta sig från den givna startportalen till slutportalen. Om det är omöjligt så skriver du ut -1. Skriv ut svaret för varje förfrågan på en separat rad.

Förklaring av exempel

(그림은 원문 저장소에서 볼 수 있습니다)

Figur 1: En illustration av Sample Input 1.

Nätverket i exempelfallet ser ut som i figuren. Vi får tre stycken förfrågningar. Den första undrar hur många gånger vi behöver gå in i portalerna när vi börjar vid 1 och vill hamna vid 2. Eftersom man direkt hamnar vid 2 när man går in i 1 så är svaret 1. För att ta sig från 1 till 4 så krävs tre hopp. För den sista förfrågan är svaret -1, eftersom vi aldrig kan ta oss från 2 till 5, oavsett hur länge vi går igenom portalerna.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

GruppPoängvärdeGränserÖvrigt
1101 ≤ N ≤ 1000, 1 ≤ Q ≤ 1000Det kommer alltid finnas en väg mellan start- och slutportalerna.
2201 ≤ N ≤ 1000, 1 ≤ Q ≤ 1000
3101 ≤ N ≤ 7000, 1 ≤ Q ≤ 120000Det kommer alltid finnas en väg mellan start- och slutportalerna.
4101 ≤ N ≤ 7000, 1 ≤ Q ≤ 120000
5101 ≤ N ≤ 50000, 1 ≤ Q ≤ 70000Det kommer alltid finnas en väg mellan start- och slutportalerna. Testfallen är också lite snällare än grupp 6.
6301 ≤ N ≤ 50000, 1 ≤ Q ≤ 70000Det kommer alltid finnas en väg mellan start- och slutportalerna.
7101 ≤ N ≤ 50000, 1 ≤ Q ≤ 70000

예제

예제 1

입력
5
2
3
4
3
4
3
1 2
1 4
2 5
출력
1
3
-1

출처 표기

출처: Programmeringsolympiaden 2015년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.