Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

Буба у свом лаптопу има игрицу која садржи бесконачну таблу чије су врсте и колоне индексиране природним бројевима. У почетку, када се игрица покрене, на пољу \((1, 1)\) налази се један жетон. Сваког дана, кад нема шта друго да ради, она кликне на поље на којем се налази бар један жетон, рецимо, поље \((x, y)\), и након тога се један жетон склони са тог поља а по један жетон се додаје на поља \((x+1, y)\) и \((x, y+1)\). Али авај! Зли космички зрак (по својој природи гама фотон енергије неколико десетина мегаелектронволти) је ударио у ћелију RAM меморије и тиме избрисао све жетоне са табле.

Бубу је ово јако потресло па је њен друг одлучио да јој помогне. Они су пронашли и скинули изворни код игрице и покренули је у debug моду. У овом моду играч може кликнути на било које поље табле и на то поље се додаје један жетон. Ако се у неком тренутку табла налази у стању до којег је могуће доћи нормалним играњем игре, Буба ће узвикнути “Стоп!” а затим ће издиктирати низ потеза који би при нормалном игрању игре довео таблу у то стање.

Ваш задатак је да помогнете Бубином другу да, за дати низ кликова у debug моду предвиди у ком тренутку ће она узвикнути “Стоп!”, као и који низ потеза би она тада могла да издиктира.

Опис улаза

Прва линија стандардног улаза садржи један природан број \(N\) - дужину низа кликова. Наредних \(N\) линија садржи по два природна броја \(x_i, y_i\), одвојена размаком - координате поља на која ће кликнути Бубин друг.

Опис излаза

Уколико ће Буба у неком тренутку узвикнути “Стоп!”, исписати тренутак у којем ће се то десити. Прецизније, уколико ће она узвикнути “Стоп!” након \(k\) кликова, у прву линију стандардног излаза исписати број \(k\). У наредних \(k-1\) линија исписати редом потезе, тачније, координате поља одвојене размаком, који би при нормалној игри довели таблу у тај положај. Ако постоји више таквих низова потеза, штампати било који. У супротном, ако Буба неће ни у једном тренутку узвикнути “Стоп!”, у прву и једину линију стандардног излаза исписати број \(-1\).

Пример 1

Улаз

4
2 2
1 2
3 1
2 3

Излаз

3
1 1
2 1

Пример 2

Улаз

4
4 1
3 2
2 3
1 4

Излаз

-1

Објашњење примера

У првом примеру, Буба ће узвикнути “Стоп!” након што њен друг дода три жетона на поља \((2, 2), (1, 2), (3, 1)\). Буба може до истог изгледа табле доћи нормалном игром тако што прво кликне на поље \((1, 1)\), при чему ће се тај жетон обрисати са тог поља а појавиће се по један жетон на пољима \((2, 1)\) и \((1, 2)\). Након тога она може да кликне на поље \((2, 1)\). Са тог поља се жетон брише а додаје се по један жетон на поља \((3, 1)\) и \((2, 2)\). Сада се на табли налазе три жетона на позицијама: \((3, 1), (2, 2), (1, 2)\), односно, добија се исти изглед табле као онај који је њен друг направио након три клика у debug моду.

У другом примеру ни у једном тренутку се не добија табла коју Буба може да направи нормалном игром.

Ограничења

У свим тест примерима важи: \(N, x_i, y_i \leq 500.000\). Тест примери су подељени у 4 дисјунктне групе: