Problem C
Färgningsspelet

Slugas Fulacek har utmanat Oskar på ett färgningsspel som spelas på ett papper med massa cirklar på. Vissa par av cirklar är förbundna med streck, och kallas för vänner.

Spelarna turas om att färglägga en cirkel som ännu inte färglagts i taget. Den spelare som drar först (i det här fallet är det alltid Slugas) använder alltid röd färg, och den andra spelaren använder alltid blå färg. När en spelare ska färglägga en cirkel får dock ingen av cirkelns vänner ha samma färg som cirkeln själv. Den spelare som inte längre kan göra ett drag (antingen för att alla cirklar är färglagda, eller för att alla cirklar som är kvar har en vän av samma färg) förlorar.

Slugas är dock väldigt intelligent, och har lyckats vinna alla tidigare spel han utmanat Oskar på (som fia med knuff, svälta räv och att gissa nästa bit från en slumpgenerator). Oskar har därför bett dig om hjälp med att spela färgningsspelet mot Slugas så bra som möjligt.

I färgningsspelet kan pappret se ut på några olika sätt.

1. Du har $N$ cirklar numrerade från $1, \dots , N$. Cirklarna $(1, 2), (2, 3), \dots , (N-1, N)$ och $(N, 1)$ är vänner. Cirklarna bildar alltså en vänskapscirkel.

2. Du har $N$ cirklar numrerade från $1, \dots , N$. Cirklarna $(1, 2), (2, 3), \dots , (N-1, N)$ är vänner. Cirklarna bildar alltså en vänskapsväg.

Indata

Indatan består av två heltal: $N \ge 1$ (antalet cirklar) samt $M$ som är antingen 1 eller 2. 1 betyder att cirklarna bildar en cirkel, medan 2 betyder att cirklarna bildar en väg. Alla instanser som ges kommer vara så att Oskar alltid har en möjlighet att vinna om han spelar så bra som möjligt.

Interaktivitet

Det här problemet är interaktivt. Efter att du läst in $N$ och $M$ kommer Slugas att göra sitt första drag. Du ska nu läsa in numret på den cirkel som han färgade. Därefter ska du skriva ut numret på den cirkel du vill färga, följt av en nyrad.

Om Slugas inte längre kan göra ett drag kommer han skriva ut -1 istället. Då har du vunnit, och ditt program ska avsluta.

Om du skriver ut ett ogiltigt drag eller inget drag alls trots att spelet inte är slut kommer du förlora.

Kom ihåg att flusha utdataströmmen efter varje utskrift. I C++ görs detta t.ex. med "cout << endl;" eller "cout << flush;", i C med "fflush(stdout);".

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.

Exempel

Först kommer du att få de två första heltalen som anger storleken på grafen och typen av grafen: låt oss säga att dessa i det här exempelfallet är $5$ och $1$. Grafen har alltså fem noder och är cirkelformad.

Slugas printar sedan talet $3$ (Slugas färglägger alltså nod nummer $3$), och du ser detta efter att du läst in talet. Låt oss nu säga att du väljer att färglägga nod $1$ i cirkelgrafen. Slugas väljer nu att färglägga nod nummer $5$, du väljer därefter att färglägga nod nummer $4$. Därefter förlorar Slugas, och du noterar detta genom att läsa in talet $-1$. Den här beskrivna sessionen ser (i exempelvis C++) ut som följer (notera att den antar att Lukas spelar på exakt detta vis):

cin >> n_nodes >> type; // n_nodes = 5, type = 1
cin >> slugas_move; // slugas_move = 3
cout << 1 << endl; // du färgade nu nod 1.
cin >> slugas_move; // slugas_move = 5
cout << 4 << endl; // du färgade nu nod 4.
cin >> slugas_move; // slugas_move = -1