C. Ночная вечеринка Arpa и бесшумное появление Mehrdad
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Заметьте, что девушки в стране Arpa действительно привлекательные.

Arpa любит ночные вечеринки. В середине одной из них неожинанно пришел Mehrdad. Он увидел n пар друзей сидящих вокруг стола. i-я пара состояла из молодого человека, сидящего на ai-м стуле, и его девушки, сидящей на bi-м стуле. Стулья пронумерованы от 1 до 2n по часовой стрелке. На каждом стуле сидел ровно один человек.

На вечеринке было два вида еды: Kooft и Zahre-mar. Сейчас Mehrdad задумался, можно ли было подать еду для гостей таким образом, что:

  • Каждый человек получил бы ровно один вид еды,
  • Ни один молодой человек не получил бы тот же вид еды, что и его девушка,
  • Среди каждых трех гостей, сидящих на последовательных стульях, нашлись бы два, получившие разный вид еды. Заметим, что стулья 2n и 1 также считаются последовательными.

Найдите ответ на вопрос Mehrdad. Если такое было возможно, то найдите распределение видов еды, удовлетворяющее всем условиям.

Входные данные

Первая строка содержит целое число n (1  ≤  n  ≤  105) — количество пар гостей.

Далее следуют n строк. i-я из них содержит два целых числа ai и bi (1  ≤ ai, bi ≤  2n) — номер стула, на котором сидел молодой человек в i-й паре и номер стула, на котором сидела его девушка. Гарантируется, что на каждом стуле сидит ровно один человек.

Выходные данные

Если решения не существует, выведите -1.

Иначе выведите n строк, i-я из них должна содержать два целых числа, описывающие виды еды, поданной для i-й пары. Первое число в этой строке это вид еды, поданной молодому человеку, а второе — тип еды, поданной его девушке. Если человеку подали Kooft, выведите 1, иначе выведите 2.

Если существует несколько решений, выведите любое из них.

Пример
Входные данные
3
1 4
2 5
3 6
Выходные данные
1 2
2 1
1 2