诡异的激光
题号:NC301149
时间限制:C/C++/Rust/Pascal 4秒,其他语言8秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

\hspace{15pt}天才同学正在地牢探险,突然触发了机关。幸运的是,她还有一些时间选择藏身点。
\hspace{15pt}地牢是一个 n\times m 的方格图,部分格子放置了激光发射器。对于一次激光生成的规则如下:
\hspace{23pt}\bullet\,存在偶数个发射器 k ,四个角 (1,1)(1,m)(n,1)(n,m) 一定放置发射器;藏身点不能与发射器位置相同;
\hspace{23pt}\bullet\,将所有发射器等概率随机地两两配对;对于每一对发射器,从所有满足曼哈顿距离最短的路径中等概率随机的选择一条作为激光。不同激光之间可以相交。
\hspace{15pt}我们会对同一张地图独立重复上述“随机配对 + 随机发射激光”共 10 次。你需要选择一个藏身格子;若在这 10 次中,至少有一次所有激光路径均不经过该格子,则视为这张地图通过。

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T=1000,代表数据组数。每组测试数据如下:
\hspace{15pt}一行输入三个整数 n,m,k\left(10\leqq n,m\leqq 30;\ 4\leqq k\leqq \left\lfloor\dfrac{n\times m}{5}\right\rfloor;\ k\text{ 为偶数}\right)
\hspace{15pt}此后 k 行,每行输入两个整数 r_i,c_i\left(1\leqq r_i\leqq n;\ 1\leqq c_i\leqq m\right),表示第 i 个发射器的位置。保证四个角一定是发射器,且所有发射器的位置两两不同。

输出描述:

\hspace{15pt}对于每组测试数据,输出两个整数 x\ y 表示你选择的藏身格子坐标,要求 1\leqq x\leqq n,\ 1\leqq y\leqq m,且 (x,y) 不是任何发射器位置。若有多个答案,你可以输出任意一个。
\hspace{15pt}系统对每组测试数据随机生成 10 次激光。若至少一次所有激光均不经过你输出的格子,则该组通过。一个测试文件内共有 T=1000 组数据;若通过的组数不少于 0.8\,T,则判为该测试文件通过。
\hspace{15pt}如果存在多个解决方案,您可以输出任意一个,系统会自动判定是否正确。注意,自测运行功能可能因此返回错误结果,请自行检查答案正确性。
示例1

输入

复制
3
10 10 10
1 1
1 10
10 1
10 10
2 5
3 3
4 8
7 2
6 9
9 4
10 12 20
1 1
1 12
10 1
10 12
2 2
2 11
5 3
5 10
3 6
4 7
6 6
7 7
8 5
9 2
9 9
3 10
2 8
7 11
4 2
8 9
12 10 12
1 1
1 10
12 1
12 10
2 2
2 9
6 3
6 8
3 5
4 6
9 4
8 7

输出

复制
5 5
6 5
6 4

说明

除样例外,所有数据均满足输入格式。这里的样例不满足输入格式,样例不在数据中。