{"raw_statement":[{"iden":"statement","content":"There are _n_ students in Polycarp's class (including himself). A few days ago all students wrote an essay \"My best friend\". Each student's essay was dedicated to one of the students of class, to his/her best friend. Note that student _b_'s best friend is not necessarily student _a_, if _a_'s best friend is _b_.\n\nAnd now the teacher leads the whole class to the museum of the history of sports programming. Exciting stories of legendary heroes await the students: tourist, Petr, tomek, SnapDragon — that's who they will hear about!\n\nThe teacher decided to divide students into pairs so that each pair consisted of a student and his best friend. She may not be able to split all the students into pairs, it's not a problem — she wants to pick out the maximum number of such pairs. If there is more than one variant of doing so, she wants to pick out the pairs so that there were as much boy-girl pairs as possible. Of course, each student must not be included in more than one pair."},{"iden":"input","content":"The first line contains an integer _n_ (2 ≤ _n_ ≤ 105), _n_ is the number of students per class. Next, _n_ lines contain information about the students, one per line. Each line contains two integers _f__i_, _s__i_ (1 ≤ _f__i_ ≤ _n_, _f__i_ ≠ _i_, 1 ≤ _s__i_ ≤ 2), where _f__i_ is the number of _i_\\-th student's best friend and _s__i_ denotes the _i_\\-th pupil's sex (_s__i_ = 1 for a boy and _s__i_ = 2 for a girl)."},{"iden":"output","content":"Print on the first line two numbers _t_, _e_, where _t_ is the maximum number of formed pairs, and _e_ is the maximum number of boy-girl type pairs among them. Then print _t_ lines, each line must contain a pair _a__i_, _b__i_ (1 ≤ _a__i_, _b__i_ ≤ _n_), they are numbers of pupils in the _i_\\-th pair. Print the pairs in any order. Print the numbers in pairs in any order. If there are several solutions, output any of them."},{"iden":"examples","content":"Input\n\n5\n5 2\n3 2\n5 1\n2 1\n4 2\n\nOutput\n\n2 2\n5 3\n4 2\n\nInput\n\n6\n5 2\n3 2\n5 1\n2 1\n4 2\n3 1\n\nOutput\n\n3 1\n4 2\n5 1\n3 6\n\nInput\n\n8\n2 2\n3 2\n5 1\n3 1\n6 1\n5 1\n8 2\n7 1\n\nOutput\n\n4 1\n5 6\n3 4\n2 1\n7 8"},{"iden":"note","content":"The picture corresponds to the first sample. On the picture rhomb stand for boys, squares stand for girls, arrows lead from a pupil to his/her best friend. Bold non-dashed arrows stand for pairs in the answer.\n\n<center>![image](https://espresso.codeforces.com/3151a62e5a452c116f43bb338e6a57fec36c7561.png)</center>"}],"translated_statement":"[{\"iden\":\"statement\",\"content\":\"Polycarp 的班级中有 #cf_span[n] 名学生（包括他自己）。几天前，所有学生都写了一篇题为 \\\"我最好的朋友\\\" 的作文。每名学生的作文都献给了班级中的一名学生，即他/她的最好的朋友。注意，如果学生 #cf_span[a] 的最好的朋友是 #cf_span[b]，学生 #cf_span[b] 的最好的朋友不一定是 #cf_span[a]。\\n\\n现在，老师带领全班同学参观体育编程历史博物馆。学生们将听到关于传奇英雄的激动人心的故事：tourist、Petr、tomek、SnapDragon —— 这些就是他们将听到的名字！\\n\\n老师决定将学生分成若干对，使得每对由一名学生和他的最好的朋友组成。她可能无法将所有学生都配成对，这没关系——她希望选出尽可能多的这样的配对。如果有多种方式达到最大配对数，她希望在这些方案中选出尽可能多的异性配对（即男孩-女孩配对）。当然，每个学生最多只能出现在一对中。\\n\\n第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 105]），#cf_span[n] 是班级的学生人数。接下来的 #cf_span[n] 行每行包含一名学生的信息。每行包含两个整数 #cf_span[fi, si]（#cf_span[1 ≤ fi ≤ n, fi ≠ i, 1 ≤ si ≤ 2]），其中 #cf_span[fi] 表示第 #cf_span[i] 名学生的最好的朋友的编号，#cf_span[si] 表示第 #cf_span[i] 名学生的性别（#cf_span[si = 1] 表示男孩，#cf_span[si = 2] 表示女孩）。\\n\\n请在第一行输出两个数字 #cf_span[t], #cf_span[e]，其中 #cf_span[t] 是形成的配对的最大数量，#cf_span[e] 是其中异性配对（男孩-女孩）的最大数量。然后输出 #cf_span[t] 行，每行包含一对 #cf_span[ai, bi]（#cf_span[1 ≤ ai, bi ≤ n]），表示第 #cf_span[i] 对中的两名学生编号。配对的输出顺序任意，每对中的两个编号顺序也任意。如果有多个解，输出任意一个即可。\\n\\n下图对应第一个样例。图中菱形代表男孩，正方形代表女孩，箭头从学生指向其最好的朋友。粗体非虚线箭头表示答案中的配对。 \\n\\n\"},{\"iden\":\"input\",\"content\":\"第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 105]），#cf_span[n] 是班级的学生人数。接下来的 #cf_span[n] 行每行包含一名学生的信息。每行包含两个整数 #cf_span[fi, si]（#cf_span[1 ≤ fi ≤ n, fi ≠ i, 1 ≤ si ≤ 2]），其中 #cf_span[fi] 表示第 #cf_span[i] 名学生的最好的朋友的编号，#cf_span[si] 表示第 #cf_span[i] 名学生的性别（#cf_span[si = 1] 表示男孩，#cf_span[si = 2] 表示女孩）。\"},{\"iden\":\"output\",\"content\":\"请在第一行输出两个数字 #cf_span[t], #cf_span[e]，其中 #cf_span[t] 是形成的配对的最大数量，#cf_span[e] 是其中异性配对（男孩-女孩）的最大数量。然后输出 #cf_span[t] 行，每行包含一对 #cf_span[ai, bi]（#cf_span[1 ≤ ai, bi ≤ n]），表示第 #cf_span[i] 对中的两名学生编号。配对的输出顺序任意，每对中的两个编号顺序也任意。如果有多个解，输出任意一个即可。\"},{\"iden\":\"examples\",\"content\":\"输入55 23 25 12 14 2输出2 25 34 2输入65 23 25 12 14 23 1输出3 14 25 13 6输入82 23 25 13 16 15 18 27 1输出4 15 63 42 17 8\"},{\"iden\":\"note\",\"content\":\"下图对应第一个样例。图中菱形代表男孩，正方形代表女孩，箭头从学生指向其最好的朋友。粗体非虚线箭头表示答案中的配对。   \"}]}","sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 2 \\leq n \\leq 10^5 $, be the number of students.  \nFor each student $ i \\in \\{1, \\dots, n\\} $:  \n- Let $ f_i \\in \\{1, \\dots, n\\} \\setminus \\{i\\} $ denote the best friend of student $ i $.  \n- Let $ s_i \\in \\{1, 2\\} $ denote the sex of student $ i $, where $ s_i = 1 $ for a boy and $ s_i = 2 $ for a girl.  \n\nLet $ G = (V, E) $ be a directed graph with $ V = \\{1, \\dots, n\\} $ and edge set $ E = \\{(i, f_i) \\mid i \\in V\\} $.  \n\nA *valid pair* is an unordered pair $ \\{i, j\\} $ such that $ f_i = j $ and $ f_j = i $ (i.e., mutual best friends).  \nA *boy-girl pair* is a valid pair $ \\{i, j\\} $ where $ s_i \\ne s_j $.  \n\n**Constraints**  \n1. Each student appears in at most one pair.  \n2. Only mutual best friend pairs may be selected.  \n\n**Objective**  \nFind a set $ P \\subseteq \\{ \\{i, j\\} \\mid f_i = j \\text{ and } f_j = i \\} $ such that:  \n- $ |P| $ is maximized (maximum number of valid pairs).  \n- Among all such maximum-size sets, $ |P_{\\text{bg}}| $ is maximized, where $ P_{\\text{bg}} = \\{ \\{i,j\\} \\in P \\mid s_i \\ne s_j \\} $ (maximum number of boy-girl pairs).  \n\nOutput:  \n- $ t = |P| $, the maximum number of pairs.  \n- $ e = |P_{\\text{bg}}| $, the maximum number of boy-girl pairs in such a set.  \n- The set $ P $, as unordered pairs $ (a_i, b_i) $, for each pair in $ P $.","simple_statement":null,"has_page_source":false}