#P18677. Classical Minimization Problem

    ID: 18013 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2300提高极端元素优先处理不变量分析有序集合离散化

Classical Minimization Problem

Classical Minimization Problem

给定平面上 2n2n 个互不相同的点。第 ii 个点的整数坐标为 (xi,yi)(x_i,y_i)。

如果两个点 i,ji,j 满足 xi=xjx_i=x_j 或者 yi=yjy_i=y_j,则称它们为一对友好点。

请把这些点分成 nn 对,每个点恰好属于一对,并使这些配对中友好点对的数量最少。

输入格式

每份输入包含多组测试。第一行给出测试组数 tt(1≤t≤1041\le t\le10^4)。随后依次给出各组。

每组第一行包含一个整数 nn(1≤n≤1051\le n\le10^5)。

接下来 2n2n 行,第 ii 行给出两个整数 xi,yix_i,y_i(−109≤xi,yi≤109-10^9\le x_i,y_i\le10^9),表示第 ii 个点的坐标。保证同一组内所有点互不相同。

保证所有测试组的 nn 之和不超过 10510^5。

输出格式

对每组测试,先输出一个非负整数 kk,表示能够达到的最少友好点对数。

接下来输出 nn 行,第 ii 行包含两个整数 ai,bia_i,b_i,表示将第 aia_i 个点和第 bib_i 个点配成一对(1≤ai,bi≤2n1\le a_i,b_i\le2n,ai≠bia_i\ne b_i)。

从 11 到 2n2n 的每个编号必须在全部 ai,bia_i,b_i 中恰好出现一次。满足两点横坐标相等或纵坐标相等的配对数量,必须恰好等于你输出的 kk,且 kk 必须最小。

有多个最优配对方案时,可以输出任意一种。

样例输入 1

3
2
0 0
0 1
1 0
1 1
2
0 0
0 1
0 2
0 3
2
0 0
1 1
2 2
3 3

样例输出 1

0
3 2
4 1
2
2 1
4 3
0
4 3
2 1