{"problem":{"name":"E. Arpa’s overnight party and Mehrdad’s silent entering","description":{"content":"_Note that girls in Arpa’s land are really attractive._ Arpa loves overnight parties. In the middle of one of these parties Mehrdad suddenly appeared. He saw _n_ pairs of friends sitting around a tab","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF742E"},"statements":[{"statement_type":"Markdown","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.\n\n## Input\n\nThe 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.\n\n## Output\n\nIf 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.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","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如果有多个解，输出任意一个即可。\n\n## Input\n\n第一行包含一个整数 #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] 对情侣中男孩和女友所坐的椅子编号。保证每张椅子上恰好有一人。\n\n## Output\n\n如果没有解，请输出 _-1_。否则，请输出 #cf_span[n] 行，第 #cf_span[i] 行应包含两个整数，表示第 #cf_span[i] 对情侣的食物类型。该行第一个整数是男孩的食物类型，第二个整数是女孩的食物类型。如果某人吃了 Kooft，请输出 #cf_span[1]，否则输出 #cf_span[2]。如果有多个解，输出任意一个即可。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**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\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. For all $ i $, $ a_i \\ne b_i $, and all $ a_i, b_i $ are distinct across all pairs (each chair has exactly one person).  \n\n**Objective**  \nAssign to each person a food type $ f: C \\to \\{1, 2\\} $ (1 = Kooft, 2 = Zahre-mar) such that:  \n- For each pair $ (a_i, b_i) $, $ f(a_i) \\ne f(b_i) $.  \n- For each adjacent pair of chairs $ (j, j+1) $ for $ j = 1, \\dots, 2n-1 $, and $ (2n, 1) $, $ f(j) \\ne f(j+1) $ (circular adjacency).  \n\nIf such an assignment exists, output for each pair $ i $: $ (f(a_i), f(b_i)) $.  \nIf no such assignment exists, output $-1$.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF742E","tags":["graphs"],"sample_group":[["3\n1 4\n2 5\n3 6","1 2\n2 1\n1 2"]],"created_at":"2026-03-03 11:00:39"}}