#P4982. [2017年湖南省队集训]第三题
[2017年湖南省队集训]第三题
不相交的双色树
题目描述
sl 在机房里玩一个平面连线游戏。平面上有 个 A 类点和 个 B 类点,两类点分别从 开始编号。
用 条直线段把 A 类点连成一棵树,用 条直线段把 B 类点连成一棵树。两棵树中任意两条边只能在它们共同的顶点相交。请给出一种合法连边方案,或报告无解。
输入格式
第一行两个整数 ,分别表示两类点的数量。随后 行每行两个整数,依次给出 A 类点的坐标。再随后 行每行两个整数,依次给出 B 类点的坐标。
,坐标的绝对值不超过 。没有三点共线。
输出格式
如果无解,输出 GG!。
否则输出 行。前 行每行两个整数 ,表示连接编号为 的两个 A 类点。随后的 行按相同格式输出 B 类树的边。
样例
3 2
1 0
0 1
2 3
0 0
1 1
1 3
2 3
1 2