Buba u svom laptopu ima igricu koja sadrži beskonačnu tablu čije su vrste i kolone indeksirane prirodnim brojevima. U početku, kada se igrica pokrene, na polju ~(1, 1)~ nalazi se jedan žeton. Svakog dana, kad nema šta drugo da radi, ona klikne na polje na kojem se nalazi bar jedan žeton, recimo, polje ~(x, y)~, i nakon toga se jedan žeton skloni sa tog polja a po jedan žeton se dodaje na polja ~(x+1, y)~ i ~(x, y+1)~. Ali avaj! Zli kosmički zrak (po svojoj prirodi gama foton energije nekoliko desetina megaelektronvolti) je udario u ćeliju RAM memorije i time izbrisao sve žetone sa table.

Bubu je ovo jako potreslo pa je njen drug odlučio da joj pomogne. Oni su pronašli i skinuli izvorni kod igrice i pokrenuli je u _debug_ modu. U ovom modu igrač može kliknuti na bilo koje polje table i na to polje se dodaje jedan žeton. Ako se u nekom trenutku tabla nalazi u stanju do kojeg je moguće doći normalnim igranjem igre, Buba će uzviknuti "Stop!" a zatim će izdiktirati niz poteza koji bi pri normalnom igranju igre doveo tablu u to stanje.

Vaš zadatak je da pomognete Bubinom drugu da, za dati niz klikova u _debug_ modu predvidi u kom trenutku će ona uzviknuti "Stop!", kao i koji niz poteza bi ona tada mogla da izdiktira.

Opis ulaza

Prva linija standardnog ulaza sadrži jedan prirodan broj ~N~ - dužinu niza klikova. Narednih ~N~ linija sadrži po dva prirodna broja ~x_i, y_i~, odvojena razmakom - koordinate polja na koja će kliknuti Bubin drug.

Opis izlaza

Ukoliko će Buba u nekom trenutku uzviknuti "Stop!", ispisati trenutak u kojem će se to desiti. Preciznije, ukoliko će ona uzviknuti "Stop!" nakon ~k~ klikova, u prvu liniju standardnog izlaza ispisati broj ~k~. U narednih ~k-1~ linija ispisati redom poteze, tačnije, koordinate polja odvojene razmakom, koji bi pri normalnoj igri doveli tablu u taj položaj. Ako postoji više takvih nizova poteza, štampati bilo koji. U suprotnom, ako Buba neće ni u jednom trenutku uzviknuti "Stop!", u prvu i jedinu liniju standardnog izlaza ispisati broj ~-1~.

Primer 1

Ulaz

4
2 2
1 2
3 1
2 3

Izlaz

3
1 1
2 1

Primer 2

Ulaz

4
4 1
3 2
2 3
1 4

Izlaz

-1

Objašnjenje primera

U prvom primeru, Buba će uzviknuti "Stop!" nakon što njen drug doda tri žetona na polja ~(2, 2), (1, 2), (3, 1)~. Buba može do istog izgleda table doći normalnom igrom tako što prvo klikne na polje ~(1, 1)~, pri čemu će se taj žeton obrisati sa tog polja a pojaviće se po jedan žeton na poljima ~(2, 1)~ i ~(1, 2)~. Nakon toga ona može da klikne na polje ~(2, 1)~. Sa tog polja se žeton briše a dodaje se po jedan žeton na polja ~(3, 1)~ i ~(2, 2)~. Sada se na tabli nalaze tri žetona na pozicijama: ~(3, 1), (2, 2), (1, 2)~, odnosno, dobija se isti izgled table kao onaj koji je njen drug napravio nakon tri klika u _debug_ modu.

U drugom primeru ni u jednom trenutku se ne dobija tabla koju Buba može da napravi normalnom igrom.

Ograničenja

U svim test primerima važi: ~N, x_i, y_i \leq 500.000~. Test primeri su podeljeni u 4 disjunktne grupe:

• U test primerima vrednim 8 poena: ~N, x_i, y_i \leq 4~.
• U test primerima vrednim 28 poena: ~N, x_i, y_i \leq 10~.
• U test primerima vrednim 18 poena: ~N, x_i, y_i \leq 100~.
• U test primerima vrednim 54 poena: Nema dodatnih ograničenja.