题目描述

每学期最让人激动的时候莫过于换同桌了，没有一位学生不愿意和自己喜欢的同学坐在一起，度过一个愉快充实的学期。

作为一位民主的教师，小 A 会收集每个学生的同桌意向作为参考，每个学生会向小 A 提交一个他（或她）理想中的同桌。小 A 希望他能够满足尽可能多的同学的要求，当然，每位同学只能有一个同桌。换句话说，小 A 希望能够出现尽可能多的同桌，满足同桌两人中存在着一个人，喜欢和另一个人为同桌，我们不妨把这样的同桌成为「满意」同桌。注意，同学 a 喜欢和同学 b 为同桌，同学 b 不一定喜欢和同学 a 为同桌。

小 A 同时还是一个异性恋主义者，他信奉：男女搭配，干活不累。所以， 在满足出现尽可能多「满意」同桌的前提下，他同时还希望「满意」的同桌中，男女为同桌的组数最大化。他希望你能帮他解决这个问题，他想知道：最大的“满意”组数，以及该条件下最大的男女组数，并且给出方案。注意到可能存在不只一个这样的最优配对，你可以给出任意一个合法的方案。

输入格式

本题有多组数据。

第一行包含一个数字 $t$，表示问题的组数。

接下来 $t$ 组数据，每组数组格式如下：

第一行包含一个数字 $n$，表示同学的数量。

接下来 $n$ 行第 $i+1$ 行有两个数字 $a_i$ 和 $b_i$。其中 $a_i$ 表示 $i$ 号同学理想中的同桌编号，$b_i$ 表示他的性别， $1$ 为男， $2$ 为女。

输出格式

对于每一个询问，第一行包含两个数字 $ans1$ 和 $ans2$，分别表示最大的“满意”组数和该条件下最大的男女组数。接下来的 $ans1$ 行，每行两个数字，给出两个编号，他们互为同桌。

样例

1
6
5 2
3 2
5 1
2 1
4 2
3 1

3 1
4 2
5 1
3 6

数据规模与约定

对于 $100\%$ 的数据：$N\le 10^6$，$T\le 3$。