Polycarp 的班级有 n 个学生(包括他自己)。前几天,全体学生写了一篇作文《我最好的朋友》。每个学生的论文都献给班上的一位学生,献给他/她最好的朋友。请注意,如果 a 最好的朋友是 b,则学生 b 最好的朋友不一定是学生 a。
现在老师带领全班同学来到体育编程历史博物馆。传奇英雄的激动人心的故事等待着学生:游客、彼得、托梅克、金鱼龙——他们将听到关于这些人的故事!
老师决定将学生分成两组,每组由一名学生和他最好的朋友组成。她可能无法将所有学生分成两对,这不是问题——她想选出最大数量的这样的对。如果这样做的变体不止一种,她想挑选出一对,以便有尽可能多的男孩女孩对。当然,每个学生不得包含在超过一对中。
输入
第一行包含一个整数n(2≤n≤105),n是每个班级的学生人数。接下来,n 行包含有关学生的信息,每行一个。每行包含两个整数 fi, si (1 ≤ fi ≤ n, fi ≠ i, 1 ≤ si ≤ 2),其中 fi 是第 i 个学生最好的朋友的数量,si 表示第 i 个学生的性别(对于男孩,si = 1;对于女孩,si = 2)。
输出
在第一行打印两个数字 t, e,其中 t 是形成的对的最大数量,e 是其中男孩女孩型对的最大数量。然后打印t行,每行必须包含一对ai,bi(1≤ai,bi≤n),它们是第i对中的学生数。以任意顺序打印这些对。以任意顺序成对打印数字。如果有多个解,输出任意一个。
示例
输入 #1
5 5 2 3 2 5 1 2 1 4 2
输出 #1
2 2 5 3 4 2
输入 #2
6 5 2 3 2 5 1 2 1 4 2 3 1
输出 #2
3 1 4 2 5 1 3 6
输入 #3
8 2 2 3 2 5 1 3 1 6 1 5 1 8 2 7 1
输出 #3
4 1 5 6 3 4 2 1 7 8
注意
该图片对应于第一个样本。在图片上,菱形代表男孩,正方形代表女孩,箭头从学生通向他/她最好的朋友。粗体非虚线箭头代表答案中的成对箭头。