CF81E.Pairs

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.

And 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!

The 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.

Polycarp 的班级中共有 $n$ 名学生（包括他自己）。几天前，所有学生都写了一篇题为《我最好的朋友》的作文。每名学生的作文都献给了班上的一名学生——即他/她最好的朋友。注意：若学生 $a$ 的最好朋友是学生 $b$，学生 $b$ 的最好朋友却未必是学生 $a$。

现在，老师带领全班同学前往体育编程史博物馆。传奇英雄们的精彩故事正等待着学生们：tourist、Petr、tomek、SnapDragon——他们将听到这些人的事迹！

老师决定将学生两两分组，使得每组均由一名学生及其最好的朋友组成。她可能无法将所有学生都配成这样的对子，这没有关系——她希望选出尽可能多的此类对子。如果存在多种方案都能达到最大对数，则她希望在这些方案中，使男女配对的数量尽可能多。当然，每名学生至多只能出现在一个对子中。

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).

第一行包含一个整数 $n$（$2 \leq n \leq 10^5$），表示每班的学生人数。接下来的 $n$ 行描述学生的信息，每行一条记录。每行包含两个整数 $f_i$、$s_i$（$1 \leq f_i \leq n$，$f_i \neq i$，$1 \leq s_i \leq 2$），其中 $f_i$ 表示第 $i$ 位学生的最好朋友的编号，$s_i$ 表示第 $i$ 位学生的性别（$s_i = 1$ 表示男生，$s_i = 2$ 表示女生）。

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.

第一行输出两个数 $t$ 和 $e$，其中 $t$ 表示所能组成的最大配对数，$e$ 表示其中男-女类型配对的最大数量。随后输出 $t$ 行，每行包含一对数 $a_i,\,b_i$（$1 \le a_i,\,b_i \le n$），表示第 $i$ 个配对中两名学生的编号。配对的顺序可以任意；每对中两个数的顺序也可以任意。若存在多种解法，输出任意一种即可。

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.

该图片对应第一个样例。图中菱形代表男生，正方形代表女生，箭头从一名学生指向其最要好的朋友。加粗且非虚线的箭头表示答案中的配对。