送 (A)

题目描述

给出一张 $n\times m$ 的网格图，两个格子之间有一条双向边，当且仅当它们相邻，即在网格图中有一条公共边。

特殊地，对于 $1\le x\le n$ ，$(x,1)$ 和 $(x,m)$ 也视为相邻。但对于 $1\le y\le m$ ，$(1,y)$ 和 $(n,y)$ 不视为相邻。

现在这张网格图有 $k$ 个格子坏掉了，你需要判断剩下的部分是否形成一张无向无环连通图。

输入

第一行：一个整数 $T$ ，表示数据组数。

对于每组数据：

第一行：三个整数 $n$ 、$m$ 、$k$ ，含义如题目所述；
接下来的 $k$ 行，每行两个整数 $x_i$ 、$y_i$ ，表示第 $i$ 个坏掉的格子为 $(x_i,y_i)$ 。

输出

对于每组数据输出一行，如果剩余部分形成一张无向无环连通图则输出 "Yes" ，否则输出 "No" 。

样例

样例输入

2
3 3 4
2 1
2 3
3 1
3 3
3 3 5
1 1
1 2
2 1
3 1
3 2

样例输出

No
Yes

数据范围与提示

对于 $20\%$ 的数据，$n,m\le 100$ ；
对于 $50\%$ 的数据，$n,m\le 1000$ ；
对于另外 $20\%$ 的数据，$k\le 1000$ ；
对于 $100\%$ 的数据，$1\le T\le 10$ ，$3\le n,m\le 10^9$ ，$0\le k\le\text{min}(nm-1,10^5)$ ，保证给出的格子互不相同。