#P4203. 同桌的你

    ID: 3418 传统题 4000ms 256MiB 尝试: 45 已通过: 5 难度: 7 上传者: 标签>难度分类提高+/省选-图论功能图一般图匹配基环树拆环动态规划树形 DP构造与建模多目标整数权值编码CF2300

同桌的你

同桌的你

题目描述

有 nn 位同学,每位同学指定一位理想同桌。要为他们安排若干对同桌,每人最多出现在一对中。若两人中至少一位将另一位选为理想同桌,则这对同桌是满意的。理想同桌的选择可以是单向的。

先使满意的同桌对数最大;在此基础上,使满意对中由一男一女组成的对数最大。求这两个最大值,并给出方案中所有满意的同桌对。

输入格式

第一行一个整数 tt(1≤t≤31\le t\le3),表示数据组数。

每组第一行一个整数 nn(1≤n≤1061\le n\le10^6)。接下来 nn 行,第 ii 行包含 ai,bia_i,b_i,其中 aia_i 是第 ii 位同学的理想同桌编号,bi=1b_i=1 表示男,bi=2b_i=2 表示女。

输出格式

每组先输出一行两个整数,依次表示满意对数的最大值 ss 和在达到 ss 时满意对中男女搭配对数的最大值。接下来 ss 行,每行两个同学的编号,表示一对满意的同桌。每位同学最多出现一次。

样例 #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