{"raw_statement":[{"iden":"statement","content":"_Note that girls in Arpa’s land are really attractive._\n\nArpa loves overnight parties. In the middle of one of these parties Mehrdad suddenly appeared. He saw _n_ pairs of friends sitting around a table. _i_\\-th pair consisted of a boy, sitting on the _a__i_\\-th chair, and his girlfriend, sitting on the _b__i_\\-th chair. The chairs were numbered 1 through 2_n_ in clockwise direction. There was exactly one person sitting on each chair.\n\n<center>![image](https://espresso.codeforces.com/04bcea95f25c850d6caf7e8b61d565c842217e0d.png)</center>There were two types of food: Kooft and Zahre-mar. Now Mehrdad wonders, was there any way to serve food for the guests such that:\n\n*   Each person had exactly one type of food,\n*   No boy had the same type of food as his girlfriend,\n*   Among any three guests sitting on consecutive chairs, there was two of them who had different type of food. Note that chairs 2_n_ and 1 are considered consecutive.\n\nFind the answer for the Mehrdad question. If it was possible, find some arrangement of food types that satisfies the conditions."},{"iden":"input","content":"The first line contains an integer _n_ (1  ≤  _n_  ≤  105) — the number of pairs of guests.\n\nThe _i_\\-th of the next _n_ lines contains a pair of integers _a__i_ and _b__i_ (1  ≤ _a__i_, _b__i_ ≤  2_n_) — the number of chair on which the boy in the _i_\\-th pair was sitting and the number of chair on which his girlfriend was sitting. It's guaranteed that there was exactly one person sitting on each chair."},{"iden":"output","content":"If there is no solution, print _\\-1_.\n\nOtherwise print _n_ lines, the _i_\\-th of them should contain two integers which represent the type of food for the _i_\\-th pair. The first integer in the line is the type of food the boy had, and the second integer is the type of food the girl had. If someone had Kooft, print 1, otherwise print 2.\n\nIf there are multiple solutions, print any of them."},{"iden":"example","content":"Input\n\n3\n1 4\n2 5\n3 6\n\nOutput\n\n1 2\n2 1\n1 2"}],"translated_statement":[{"iden":"statement","content":"_注意，阿尔帕国度的女生非常迷人。_\n\n阿尔帕热爱通宵派对。在其中一个派对的高潮时刻，梅赫尔达德突然出现了。他看到有 #cf_span[n] 对朋友围坐在一张桌子旁。第 #cf_span[i] 对由一名男孩和他女朋友组成，男孩坐在第 #cf_span[ai] 号椅子上，女朋友坐在第 #cf_span[bi] 号椅子上。椅子按顺时针方向编号为 #cf_span[1] 到 #cf_span[2n]，每把椅子上恰好有一人。\n\n有两种食物：Kooft 和 Zahre-mar。现在梅赫尔达德想知道，是否存在一种方式为客人分配食物，使得：\n\n请回答梅赫尔达德的问题。如果可能，请找出一种满足条件的食物分配方案。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1  ≤  n  ≤  105]）——客人的对数。\n\n接下来的 #cf_span[n] 行中，第 #cf_span[i] 行包含一对整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[1  ≤ ai, bi ≤  2n]）——第 #cf_span[i] 对中男孩和他女朋友所坐的椅子编号。保证每把椅子上恰好有一人。\n\n如果无解，请输出 _-1_。\n\n否则，请输出 #cf_span[n] 行，第 #cf_span[i] 行包含两个整数，分别表示第 #cf_span[i] 对中男孩和女孩所吃的食物类型。如果某人吃了 Kooft，请输出 #cf_span[1]，否则输出 #cf_span[2]。\n\n如果有多个解，请输出任意一个。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n]（#cf_span[1  ≤  n  ≤  105]）——客人的对数。第 #cf_span[i] 行包含一对整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[1  ≤ ai, bi ≤  2n]）——第 #cf_span[i] 对中男孩和他女朋友所坐的椅子编号。保证每把椅子上恰好有一人。"},{"iden":"output","content":"如果无解，请输出 _-1_。否则，请输出 #cf_span[n] 行，第 #cf_span[i] 行包含两个整数，分别表示第 #cf_span[i] 对中男孩和女孩所吃的食物类型。如果某人吃了 Kooft，请输出 #cf_span[1]，否则输出 #cf_span[2]。如果有多个解，请输出任意一个。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of pairs.  \nLet $ G = \\{ (a_i, b_i) \\mid i \\in \\{1, \\dots, n\\} \\} $ be the set of pairs, where $ a_i, b_i \\in \\{1, \\dots, 2n\\} $ are the chair numbers of the boy and girl in the $ i $-th pair.  \nLet $ C = \\{1, 2, \\dots, 2n\\} $ be the set of chairs, each occupied by exactly one person.  \n\nDefine a graph $ H = (V, E) $ where:  \n- $ V = \\{1, 2, \\dots, 2n\\} $ (chairs as vertices),  \n- $ E = \\{ (a_i, b_i) \\mid i \\in \\{1, \\dots, n\\} \\} \\cup \\{ (j, j+1) \\mid j \\in \\{1, \\dots, 2n-1\\} \\} \\cup \\{ (2n, 1) \\} $ (edges: each couple + adjacent chairs in circle).  \n\n**Constraints**  \n1. $ 1 \\le n \\le 10^5 $  \n2. Each chair $ c \\in C $ appears in exactly one pair $ (a_i, b_i) $.  \n3. The graph $ H $ is 2-regular (each vertex has degree 2), hence a disjoint union of cycles.  \n\n**Objective**  \nAssign to each person (chair) a food type $ f(c) \\in \\{1, 2\\} $ such that:  \n- For each pair $ (a_i, b_i) $, $ f(a_i) \\ne f(b_i) $.  \n- For each adjacent pair of chairs $ (c, c') $ (including $ (2n, 1) $), $ f(c) \\ne f(c') $.  \n\nIf such an assignment exists, output for each pair $ i $: $ (f(a_i), f(b_i)) $.  \nOtherwise, output $-1$.","simple_statement":null,"has_page_source":false}