Problem B
Lönnträd

Som kryptoarborist sysslar du med studiet av hemliga träd. Idag har du varit ute i skogen och stött på ett spännande exemplar, med $N$ noder, och $N-1$ olika långa kanter, alla av positiv längd. Det är dessutom känt att varje nod har högst $3$ kanter.

Det är inte helt lätt att avgöra strukturen av trädet – vilka noder som är sammankopplade med varandra – men du har fått tag på en apparat som du tror kan hjälpa dig. Apparaten jämför avstånd i trädet. Låt $d(x, y)$ beteckna summan av kantlängder på vägen mellan noderna $x$ och $y$. Med en användning av apparaten kan du, givet tre noder $A, B, C$ (där $A \neq B$) jämföra huruvida $d(A, C)$ är mindre eller större än $d(B, C)$.

Med hjälp av högst $20\, 000$ användningar av apparaten, kan du hitta vilka kanter som finns i trädet? Du behöver inte hitta längden på kanterna.

Interaktion

Ditt program ska först läsa in ett heltal $N$ ($3 \leq N \leq 1000$), antalet noder i trädet.

Därefter får du börja utföra mätningar med din apparat, högst $20\, 000$ stycken. För varje mätning ska du skriva ut en rad på formatet ? A B C ($1 \le A, B, C \le N$, $A \neq B$), och sedan läsa in en rad, som kommer innehålla antingen tecknet A (om $d(A, C) < d(B, C)$) eller B (om $d(A, C) > d(B, C)$). Det garanteras att $d(A, C) \neq d(B, C)$ för alla $A \neq B$.

Till slut ska du skriva ut en rad med tecknet !, och sedan $N-1$ rader, med kanterna i trädet. Varje rad ska innehålla två tal $a, b$ ($1 \le a, b \le N$), namnen på noderna kanten går mellan.

Det är garanterat att trädet i varje testfall är bestämt på förhand och inte ändras adaptivt i respons till dina mätningar.

För att förenkla testning av ditt program tillhandahåller vi ett verktyg som du kan ladda ned i sidebaren för det här problemets Kattissida. Se kommentaren högst upp i filen för en beskrivning av hur det kan användas.

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.

Exempelförklaring

I exempelinteraktionen studeras ett lönnträd med $5$ noder. Med mätapparaturen konstateras att längden på vägen mellan nod $1$ och $3$ är kortare än den mellan $2$ och $3$, och att längden på vägen mellan $1$ och $5$ är längre än den mellan $4$ och $5$. Utifrån den informationen görs gissningen att trädet har de fyra kanterna $(1, 3)$, $(2, 3)$, $(4, 3)$ och $(4, 5)$. I verkligheten skulle fler mätningar än så behöva utföras för att avgöra trädets utseende med säkerhet.

 5

 ? 1 2 3

 A

 ? 1 4 5

 B

 !
 1 3
 2 3
 4 3
 4 5