气球派对
题目描述
期待已久的气球派对马上就要开始了。组织者准备的活动场地是椭圆的，为了方便表示，我们以椭圆的中心为原点，用方程 $$\frac{x^2}{a^2}+\frac{y^2}{b^2}=1$$ 表示这个椭圆，其中 $a, b$ 均为正整数。
这一次的气球派对中，在椭圆的场地内和椭圆上的所有距离为 $1$ 的整点间（不包括整点），都有可能会出现气球（即连接每个距离为 $1$ 的整点的线段上，都会出现气球）。每个人也必须站在椭圆内和椭圆上的整点上，使用飞镖扎破气球。但是场地太小了，每个整点最多只能站一个人；而且大家为了不扎到其他人，记某一参加者在坐标 $(x, y)$ 上，他只会攻击距离他严格小于 $1$ 的气球。
比如上图，其中 $a = 5, b = 3$，气球会出现在蓝色的线段上（不包括橙色的整点），而参赛者只能站在某一个橙色的整点上，并且他们只会攻击和他距离严格小于 $1$ 的气球（即相邻的长度为 $1$ 的蓝色线段）。
但是有的整点间机器坏掉了，无法产生气球。检查后发现，这样的整点对共有 $m$ 个，用 $(x_1, y_1, x_2, y_2)$ 这样的四元组记录了下来，表示$(x_1,\, y_1)$, $(x_2,\, y_2)$ 两整点间的机器坏掉了，保证每个记录中这两个点距离为 $1$。
现在，组织者想要知道，为了能够扎到所有的气球，最少需要多少个人参加派对。他希望你能给出答案，并给出参加者最少时的一个参加者位置的方案。如果有多个方案，就给出任意一个，顺序也任意。
输入
第一行包含一个正整数 $T$，表示有 $T$ 组测试数据。
接下来共 $T$ 组数据，第一行包含两个空格分隔的正整数 $a$ 和 $b$，第二行包含一个整数 $m$，接下来 $m$ 行，每行4个整数 $x_1, y_1, x_2, y_2$。
保证所有的数据满足 $1 \leq T \leq 10,$ $1 \le a b \leq {10}^{4}$, $0 \le m \le 5ab$，并且保证给出的四元组表示的两个点均在椭圆内或椭圆上、距离均为 $1$，不会有重复的记录（也不会有交换两个点的顺序之类的重复记录），但数据不保证删边之后整点间依然联通。
输出
对于每组数据，输出多行。
第一行，包含一个整数，表示至少需要的参加者的数量 $m$。
接下来的 $m$ 行，每行两个整数 $x$ 和 $y$，用一个空格隔开，表示你的方案中参加者的坐标 $(x, y)$，整点的顺序任意。
输入样例
4
2 1
0
2 1
0
3 4
2
-2 1 -2 2
-2 1 -1 1
1 1
4
0 0 0 1
1 0 0 0
0 -1 0 0
0 0 -1 0输出样例
3
0 0
-2 0
2 0
3
2 0
0 0
-1 0
15
-2 -1
-2 0
-1 -2
-1 0
-1 2
0 -3
0 -1
0 1
0 3
1 -2
1 0
1 2
2 -1
2 0
2 1
0样例解释
前两组数据的椭圆内及椭圆上有 $7$ 个整点，为了能让这 $7$ 个整点间的气球都能被攻击到，至少需要 $3$ 个人，但是方案很多，如输出所示。只要保证你的方案中，椭圆内和椭圆上的所有整点间的气球都能被至少一个参赛者攻击到，输出任意一个就可以。第三组数据删掉了两条边；第四组机器全坏了。