「问题描述」

同桌的你 (deskmate.cpp/c/pas)

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

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

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

「输入格式」

输入文件 deskmate.in 第一行包含一个数字 t,表示问题的组数。
接下来 t 组数据,每组数组格式如下:
第一行包含一个数字 n,表示同学的数量。
接下来 n 行第 i+1 行有两个数字 ai 和 bi。其中 ai 表示 i 号同学理想中的

同桌编号, bi 表示他的性别, 1 为男, 2 为女。 「输出格式」

输出文件 deskmate.out 对于每一个询问,第一行包含两个数字 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

「数据规模与约定」

对于 20% 的数据, n ≤ 20。
对于另外 30% 的数据, n ≤ 100000。
对于 100% 的数据, n ≤ 1000000,t ≤ 3。
本题使用 Special Judge 进行评测,答对第一问将获得测试点 10% 的分数,

答对第二问将获得测试点 20% 的分数,答对第三问将获得测试点 70% 的分数。 本题的系统栈将改为 128M。

题解

懒得输出方案了QAQ

环套树，环上相邻的两条边不会同时存在，选择其中一条断开成树，做个简单树形dp