circlepassing
Day2 Tasks

European Girls'
Olympiad in Informatics
21 – 27 July 2024
The Netherlands

German (AUT)

A. Circle Passing
Aufgabenname

circlepassing

Zeit Limit

2 Sekunden

Speicher Limit

1 Gigabyte

Es ist der erste Tag der High School für Anouk; ihre Sportlehrerin lässt die Klasse Kennenlernpiele
zum Aufwärmen machen. Es gibt 2N Schülerinnen in der Klasse. Die meisten von ihnen kennen
sich untereinander nicht, jedoch gibt es M Paare von besten Freundinnen, die alles miteinandermachen. Jede Schülerin hat höchstens eine beste Freundin.
Die Lehrerin stellt alle Schülerinnen in einem Kreis auf. Jeder Schülerin wird fortlaufend eine
Nummer von 0 bis 2N − 1 zugeordnet. Genauer gesagt stehen für jedes 0 ≤ i < 2N − 1 dieSchülerinnen i und i + 1 nebeneinander. Zusätzlich stehen die Schülerinnen 0 und 2N − 1nebeneinander.
Da die Lehrerin möchte, dass jede Schülerin neue Schülerinnen kennenlernt, müssen beste
Freundinnen so weit wie möglich auseinander stehen. Das heißt, dass die Schülerinnen, die das i te Paar bester Freundinnen bilden, an den Positionen ki bzw. ki + N stehen, wobei 0 ≤ ki < N .
Die Lehrerin wählt zwei Schülerinnen x und y aus und gibt der Schülerin x einen Ball. Ziel ist es,den Ball zur Schülerin y zu bringen, dabei darf aber jede Schülerin den Ball nur zu einer Schülerin
werfen, deren Namen sie bereits kennt. Natürlich kennen beste Freundinnen die Namenvoneinander. Während die Regeln erklärt wurden, lernte jede Schülerin die Namen der beiden
Schülerinnen kennen, die direkt neben ihnen standen. Darüber hinaus kennt niemand andereNamen.
Das Spiel wird Q mal gespielt; die Lehrerin wählt jedes Mal zwei Schülerinnen. Da die Schülerinnen
nicht aufmerksam sind, lernen sie keine neuen Namen während der Spiele. Wie hoch ist dieminimale Anzahl von Würfen, die benötigt werden, um den Ball in jeder Spielrunde von derSchülerin x zur Schülerin y zu bringen.

EingabeDie erste Zeile enthält drei ganze Zahlen, N , M und Q, wobei 2N die Anzahl der Schülerinnen inAnouks Klasse ist, M die Anzahl von Paaren von besten Freundinnen und Q die Anzahl dercirclepassing (1 of 5)

Runden ist, die gespielt werden.
Die zweite Zeile enthält M ganze Zahlen k0 , ..., kM −1 , wobei ki das i -te Paar bester Freundinnen
beschreibt. Für jedes i stehen die besten Freundinnen an den Positionen ki beziehungsweiseki + N . Jede Schülerin hat höchstens eine beste Freundin.
Die folgenden Q Zeilen enthalten jeweils zwei ganze Zahlen, xi und yi , nämlich die zweiausgewählten Schülerinnen im Spiel i .

AusgabeGib Q Zeilen aus, wobei die i -te Zeile eine einzige ganze Zahl enthält, nämlich die minimale Anzahl
von erforderlichen Würfen im Spiel i .

Einschränkungen und Bewertung2 ≤ N ≤ 5 ⋅ 108 .
1 ≤ M ≤ 5 ⋅ 105 und M ≤ N .
1 ≤ Q ≤ 2 ⋅ 104 .
0 ≤ k0 < k1 < ... < kM −1 < N .
0 ≤ xi , yi < 2N mit xi ≠ yi .
Deine Lösung wird auf einer Reihe von Testgruppen getestet, welche eine gewisse Anzahl anPunkten wert sind. Jede Testgruppe enthält eine Reihe von Testfällen. Um die Punkte für eine
Testgruppe zu erhalten, musst du alle Testfälle der Testgruppe lösen.
GruppePunkteLimitsM = 1 und xi = k0 . Mit anderen Worten: es gibt nur ein Paar von besten
114Freunden in jedem Spiel und die Schülerin die mit dem Ball startet, hateine beste Freundin.

220N , M , Q ≤ 1000

322N ≤ 107 und M , Q ≤ 1000

417xi = 0 für alle i527Keine weiteren Einschränkungen

Beispiele
Die folgenden zwei Abbildungen beschreiben die Anordnungen im ersten und vierten Beispiel.
Zwei Schülerinnen sind mit einer Kante verbunden, wenn sie die Namen voneinander wissen.

circlepassing (2 of 5)

In der ersten Runde des ersten Beispiels wird der Ball der Schülerin 1 gegeben. Die Schülerin 1
wirft den Ball zu ihrer besten Freundin, Schülerin 5. Der Ball erreicht die Schülerin 4, nachdem
Schülerin 5 ihn zu ihr wirft. Im Ganzen werden zwei Würfe benötigt.

circlepassing (3 of 5)

InputOutput4 1 51211 42

1 5
1 7121 2
1 6

6 1 3255 7

315 1
5 11

4 2 42 3220 2

20 3
0 6

10 7

5 2 5

10 4

30 9
1 8

338 3

2

1 6
3 9

500000000 4 3543234 1234566 2300001 249999999

22108785876730

2334445 123567
6578996 12455726

231106567

3 269979899

circlepassing (4 of 5)

circlepassing (5 of 5)