#P4203. 同桌的你
同桌的你
同桌的你
题目描述
有 位同学,每位同学指定一位理想同桌。要为他们安排若干对同桌,每人最多出现在一对中。若两人中至少一位将另一位选为理想同桌,则这对同桌是满意的。理想同桌的选择可以是单向的。
先使满意的同桌对数最大;在此基础上,使满意对中由一男一女组成的对数最大。求这两个最大值,并给出方案中所有满意的同桌对。
输入格式
第一行一个整数 (),表示数据组数。
每组第一行一个整数 ()。接下来 行,第 行包含 ,其中 是第 位同学的理想同桌编号, 表示男, 表示女。
输出格式
每组先输出一行两个整数,依次表示满意对数的最大值 和在达到 时满意对中男女搭配对数的最大值。接下来 行,每行两个同学的编号,表示一对满意的同桌。每位同学最多出现一次。
样例 #1
样例输入 #1
1
6
5 2
3 2
5 1
2 1
4 2
3 1
样例输出 #1
3 1
4 2
5 1
3 6