糖糖王国的道路修建
题号:NC201892
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

质量和辉辉是一对姐妹,他们统治着糖糖王国。糖糖王国有  个城镇,可以看作是平面上的  个整点,其中  个属于质量,另外  个属于辉辉。
现在质量和辉辉要在各自的城镇之间修建道路,道路必须是笔直的线段。学过简单图论的小盆友都知道,只需要  条线段就可以让质量和辉辉的城镇各自两两相连。
现在就希望你能给出方案,要求在满足连通性的同时,任意两条线段都不能在城镇点以外的地方相交。如果不存在这样的方案也请判断。

输入描述:

第一行读入两个整数 ,保证 
接下来 行读入 个二维平面上的整点坐标 ,代表质量的 个城市,编号为
接下来 行读入 个二维平面上的整点坐标 ,代表辉辉的 个城市,编号为
保证在这 个点中不存在重叠和三点共线,且横纵坐标为不超过 的非负整数。

输出描述:

如果无解,请输出’Poor Quailty’,否则输出  行,前  行代表质量城镇的连接方式,之后  行代表辉辉城镇的连接方式。对于连接方式的每行请输出  个整数  代表把x和y号城镇相连。
示例1

输入

复制
2 3
0 0
1 1
1 0
0 1
2 3

输出

复制
2 1
1 3
3 2