Przyjęcie

To zadanie pochodzi z Codeforces. Tam też znajdują się testy do zadania.
Jeśli Twoje rozwiązanie zostanie pozytywnie ocenione na tamtych testach, należy wysłać tu zgłoszenie wypisujące "Zrobione".

Limit pamięci: 256MB

Na przyjęciu u Bartka znajduje się n par siedziących przy okrągłym stole. Dla i-tej pary wiemy, że chłopak siedzi na a_i-tym krześle, a dziewczyna na b_i-tym krześle.
Chcemy każdemu gościowi dać do jedzenia schabowego albo kurczaka. Muszą być spełnione jednak dwa warunki:

  • Każdy chłopak i jego dziewczyna muszą dostać inne dania (żeby móc od siebie nawzajem skosztować)
  • Nie może wystąpić sytuacja, że pewne kolejne trzy osoby dostaną takie samo jedzenie (byłoby to zbyt monotonne)
Czy Bartek może rozdzielić jedzenie tak, by powyższe warunki były spełnione?

Wejście

W pierwszym wieszu znajduje się liczba całkowita n (n<=105) oznaczająca liczbę par gości. W następnych n wierszach znajdują się po dwie liczby a_i i b_i oznaczające miejsca przy stole, które zajmuje kolejno chłopak i dziewczyna z i-tej pary. Gwarantowane jest, że każde miejsce jest zajmowane przez dokładnie jedną osobę, a miejsca numerowane są od 1 do 2n (oczywiście miejsca 1 i 2n są obok siebie).

Wyjście

Jeśli nie istnieje dobre rozłożenie jedzenia, wypisz -1. W przeciwnym wypadku wypisz n lini, w każdej z nich dwie liczby - numer jedzenia które dostał chłopak i numer jedzenia które dostała dziewczyna (z i-tej pary). Jeśli dana osoba dostała schabowego, wypisz 1, a jeśli kurczaka - 2. Jeśli istnieje wiele rozwiązań, wypisz dowolne.

Przykład

Wejście:
3
1 4
2 5
3 6

Przykladowe wyjscie:
1 2
2 1
1 2