Problem E
Jumex-train

Efter en lång dag av problemlösning har Sictor Miölc och resten av den svenska delegationen i BOI 2024 (Bossiga Olympiaden i Internationella Relationer) kommit tillbaka till hotellet med 5 medaljer och en hedersomnämning. De inser snart dock att affären har stängt och att de bara har en burk jumex kvar! Deltagarna bestämmer sig för att spela ett spel om den sista jumex-burken och vad passar bättre än en modifierad version av Mexican Train?
Så här fungerar spelet:
$N$ stycken spelare sitter runt ett bord och delar först ut $S$ stycken domino-brickor slumpmässigt till alla runt bordet. Varje domino-bricka kan representeras som en unik uppsättning av två heltal mellan $0$ och $M$, det vill säga att om en bricka består av talen $(x, y)$ kan inte $(y, x)$ också existera. Det finns alltså totalt $\frac{M(M+1)}{2}$ olika dominobrickor.
I början läggs brickan $(M, M)$ i mitten av bordet, sedan får varje deltagare sina $S$ slumpmässiga domino-brickor. Resten läggs i en hög vid sidan om. Eftersom Sictor presterade bäst av deltagarna i BOI får han börja. Varje spelare har ett privat spår som bara den deltagaren får använda till att börja med. Utöver det finns det även totalt ett sidospår som kan skapas.
Ett vanligt drag ser ut som följande: deltagaren väljer en dominobricka som har vid en sida ett matchande värde till det av något spår som den får bygga vid. Exempelvis i början måste de lägga en bricka som har uppsättningen $(M, x)$ där $x$ är något godtyckligt heltal. Dragen funkar som så att ifall du på ett spår har lagt brickan $(x, y)$ för att det tidigare var ett $x$ där måste du nu på det spåret isåfall lägga en bricka $(y, z)$. Värdet för att lägga på det spåret uppdateras alltså till det icke-matchande värdet när du lägger en bricka.
På sidospåret får alla lägga med kravet att den första brickan är på formen $(M, x)$ där $x$ är något godtyckligt värde.
Om en spelare inte kan lägga en domino-bricka vid dens tur så måste denne ta upp en dominobricka från den hög av oanvända dominobrickor som formades i början av spelet (om det inte finns någon bricka kvar där behöver denne inte ta upp någon bricka alls). Spelarens spår blir också öppet för andra att använda tills det att den spelaren lägger på det spåret igen.
Om en spelare lägger en bricka på formen $(x, x)$ måste nästa spelare i tur lägga en bricka på samma spår på formen $(x, y)$ där $y$ är något heltal. Om denne inte kan göra det så händer samma sak som om de inte kan lägga (ta upp en dominobricka, dennes spår blir öppet), och spelaren därefter måste lägga på det spåret där $(x, x)$ finns med en bricka $(x, y)$. Med andra ord gäller samma regel för de efter tills någon har lagt en bricka $(x, y)$ på det spåret.
Om ingen runt bordet kan göra ett giltigt drag eller om någon blir av med alla sina brickor avslutas spelet och den med lägst summa på sina kvarvarande brickor vinner.
Eftersom Sictor Miölc gjorde så bra i BOI får han inte bara börja utan också säga efter varje drag om han vill byta en bricka med någon. Han väljer då en av sina brickor och en spelare, och den spelaren måste då byta den brickan med en av deras.
Sictor råkar också vara den enda som har spelat förut och eftersom alla andra är så förvirrade av reglerna kör de helt slumpmässigt.
Det är ditt jobb att skriva ett program som ser till så att Sictor Miölc vinner spelet och därmed en burk Jumex.

Indata

Först kommer de tre heltalen $N, M, S$ på en rad.
Därefter kommer följande tills spelet är slut:
En rad med heltalet $Q$, antalet lagliga drag du kan köra
Detta följes av $Q$ rader där varje rad består av tre heltal $s_i, x_i, y_i$, att du kan lägga dominon $(x_i, y_i)$ på spår $s_i$.
Sedan följer en rad med heltalet $D$, antalet dominobrickor du har nu.
Därefter följer $D$ rader med heltalen $a_i, b_i$, vilket innebär att du har dominobrickan $(a_i, b_i)$ på hand.
Efter det följer $N-1$ rader med tre heltal $s_i, x_i, y_i$ som signalerar att spelare $i$ har gjort draget att lägga brickan $(x_i, y_i)$ på spår $s_i$. Om spelaren inte kan lägga skickas istället $-1$ och om spelet är över skickas $-2$.

Utdata

Efter varje gång dina dominobrickor har skrivits ut ska du skriva ut både det draget du vill göra (på formen $s_i$ $x_i$ $y_i$), samt ifall du vill byta ut bricka med någon annan.
Isåfall skriver du på raden under "SWAP", följt av den spelare du vill byta med samt den brickan du vill byta, alltså 3 heltal.
Om du inte vill byta skriv "NO-SWAP" istället.

Se till att flusha outputen efter varje drag, annars kan du få Time Limit Exceeded. I C++ kan detta göras med exempelvis cout << flush eller fflush(stdout); i Python med stdout.flush(); och i Java med System.out.flush().

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. Poäng för ett givet testfall beräknas enligt följande formel:

där "percentile" är vilken percentil av alla spelare du tillhör poängmässigt i slutet av ett spel.
Poängen du får per grupp är medelvärdet av alla testfalls poäng i gruppen.

3 4 3
2
0 1 4
3 1 4
3
3 3
1 4
2 2

0 1 4
SWAP 1 3 3

1 2 4
3 3 4
1
0 1 2
2
2 2
1 2

0 1 2
NO-SWAP

3 3 3
-1
0
1
2 2
0 0

-1

-1
-1
-2