Kao i njegov kolega Draganče na prošlom takmičenju, i profesor Đurić je shvatio da matematika i programiranje nisu bili isplativi kako je mislio. Zbog toga je odlučio da promeni profesiju i da se ubuduće bavi trgovinom. Na prošlogodišnjem saveznom takmičenju saznali ste da on baš nije sklon savremenim tehnologijama (svakako se sećate, on još programira koristeći bušene kartice), i stoga nije želeo da daje pare za neku savremenu vagu, koja bi, po njegovim rečima, bila "mnogo bre neozbiljna". Zbog toga je odlučio da je sam napravi, i to je i učinio.

Vaga profesora Đurića ima jedan tas na koji se mogu stavljati balegovi. Balegovi su objekti koji imaju celobrojnu težinu. Profesor Đurić je, naravno, svojeručno napravio i razne balegove, a obezbedio se i u slučaju da se neki baleg zagubi: naime, svaki baleg može se zameniti nekim dvama (ni manje ni više) tako da se ukupna težina ne promeni. Kako mu se sav ovaj posao oko pravljenja balegova jako dopao, odlučio je da se upravo oni prodaju u njegovoj radnji. Međutim, godine ga pritiskaju, te je zaboravio da na balegovima označi težine; na svakom je zabeležio samo redne brojeve balegova kojima se može zameniti. Nedugo potom, došla mu je i prva mušterija, koja želi da kupi komplet balegova čija je ukupna težina jednaka nuli. S obzirom na to što svi znamo da je mušterija uvek u pravu, pomozite profesoru Đuriću da ispuni svoju dužnost kao valjanog trgovca. Ukoliko mu ne pomognete, ne samo što ćete ostati bez bodova, već će vas sigurno i bar dva puta opsovati.

Ulaz:

(Ulazni podaci se nalaze u datoteci balegovi.in) U prvom redu ulazne datoteke nalazi se prirodan broj n, broj različitih balegova koje profesor Đurić ima (pri tom smatrati da od svakog poseduje dovoljno primeraka). Narednih n redova karakterišu balegove profesora Đurića redom, i to na sledeći način: u prvom od njih nalaze se dva prirodna broja koji predstavljaju redne brojeve balegova kojima se prvi baleg može zameniti; u sledećem redu se nalaze dva prirodna broja koji predstavljaju redne brojeve balegova kojima se drugi baleg može zameniti, itd.

Izlaz:

(Izlazne podatke upisati u datoteku balegovi.out) U prvom redu izlazne datoteke treba upisati koliko je balegova profesor Đurić prodao. U narednom redu treba upisati njihove redne brojeve, razdvojene prazninom. Ukoliko profesor Đurić može da zadovolji mušteriju na više načina, odabrati bilo koji.

• 1 ≤ n ≤ 10⁶
• težine balegova nalaze se u rasponu od -2^1000000 do 2^1000000
• vremensko ograničenje za izvršavanje programa je 1 s
• memorijsko ograničenje za izvršavanje programa je 32 MB

Primer 1:

7
4 7
1 1
2 1
3 5
1 6
4 4
2 3

4
7 5 1 1

Objašnjenje:

Profesor Đurić ima balegove težina 1, 2, 3, -4, -7, -8, 5 (redom). Prvi baleg (čija je težina 1) može se predstaviti pomoću balegova 4 i 7 (čije su težine -4 i 5), što je prikazano na slici levo. Takođe, primera radi, šesti baleg (čija je težina -8) može se predstaviti pomoću dva jednaka balega 4 (čija je težina -4), što je ilustrovano slikom u sredini. Slično važi za ostale balegove. Na desnoj slici vidite kako je profesor Đurić uslužio mušteriju: prodao mu je balegove 7 i 5 i dva balega broj 1 (čije su težine 5, -7 i dva puta 1 pa im ukupan zbir jeste jednak nuli, kao što je traženo). Neophodno je imati u vidu da nije poznato koje balegove profesor Đurić ima, i zato ponuđeno rešenje mora ispunjavati traženi uslov za svaki mogući set balegova koji odgovara ulaznim podacima (pogledati i sledeći primer).

Primer 2:

17
12 12
15 8
7 11
3 3
14 14
9 13
4 2
16 16
14 10
6 1
7 7
13 5
10 1
12 1
4 17
2 2
3 4

6
5 1 1 13 10 1

Objašnjenje:

I set
(-12, -5, 3, 6, -36, 54, 1, -20, 24, 42, 2, -6, 30, -18, 15, -10, 9)
i set
(8, -15, 9, 18, 24, -36, 3, -60, -16, -28, 6, 4, -20, 12, 45, -30, 27)
zadovoljavaju početne uslove (postoji još ovakvih setova). Budući da ne znamo koji od njih profesor Đurić poseduje, rešenja — primera radi — (4, 12) i (3, 6, 17) nisu ispravna, jer čine zbir nula samo u prvom, odnosno drugom slučaju. Traži se rešenje koje u svakom mogućem slučaju daje zbir nula; jedno od njih je prikazano.

Formiramo orijentisani multigraf čiji su čvorovi balegovi profesora Đurića, i iz svakog čvora vode tačno dve usmerene grane: ka čvorovima kojima se on može zameniti. Pronađemo konturu u tom grafu (recimo tako što krenemo od jednog čvora i pratimo po jednu granu dok ne dođemo u neki čvor u kom smo već bili; ovo se sigurno mora dogoditi, jer imamo konačan broj čvorova, a iz svakog vode po dve grane). Čvorovi na koje ukazuju preostale grane čvorova s pronađene konture čine rešenje zadatka.

Zaista, ukoliko su čvorovi na konturi a₁, a₂, ..., a_k (tim redom), i ukoliko njihove preostale grane vode ka čvorovima b₁, b₂, ..., b_k, važe sledeće relacije:

a₁ = a₂ + b₁
a₂ = a₃ + b₂
.
.
.
a_k-1 = a_k + b_k-1
a_k = a₁ + b_k

Sabiranjem svih ovih jednakosti dobijamo:

a₁ + a₂ + ... + a_k-1 + a_k = a₂ + a₃ + ... + a_k + a₁ + b₁ + b₂ + ... + b_k-1 + b_k,

gde možemo skratiti sve članove s oznakom a, posle čega ostaje:

0 = b₁ + b₂ + ... + b_k-1 + b_k,

što smo i tražili.

Zadatak se može rešiti na još načina. Pomenućemo, recimo, ideju da svaki baleg (tj. njegov redni broj) uključimo u rešenje za jedan manje puta nego što se on ukupno pojavljuje u ulazu. Takmičarima ostavljamo za vežbu da sami dokažu korektnost i ovog rešenja.

{
ZADATAK: balegovi
JEZIK: pascal
}
var n,i,poc,kraj:longint;
    a,b,inde:array[1..1000000] of longint;
    ui:array[1..1000000] of boolean;
    f:text;
begin
 assign(f,'balegovi.in');
 reset(f);
 readln(f,n);
 for i:=1 to n do
   readln(f,a[i],b[i]);
 close(f);
 inde[1]:=1;
 ui[1]:=true;
 kraj:=1;
 while not ui[a[inde[kraj]]] do
    begin
     inde[kraj+1]:=a[inde[kraj]];
     inc(kraj);
     ui[inde[kraj]]:=true;
    end;
 poc:=1;
 while inde[poc]<>a[inde[kraj]] do
    inc(poc);
 assign(f,'balegovi.out');
 rewrite(f);
 writeln(f,kraj-poc+1);
 for i:=poc to kraj do
   write(f,b[inde[i]],' ');
 close(f);
end.