UOJ Logo Universal Online Judge

UOJ

#142. 【UER #5】万圣节的南瓜灯

统计

红包是一个心灵手巧的男孩子。今天是万圣节,红包正在家里制作南瓜灯。

这时候一群熊孩子们敲开了红包家的门,他们高呼着“不用给糖,只要捣蛋”的口号把红包的南瓜灯弄坏了。这让红包很难过,于是他打算把这些被弄坏的南瓜灯做成其他的工艺品。

红包把它的南瓜灯划分成了 $n \times m$ 的网格,并用 $(x,y)$ 表示第 $x$ 行,第 $y$ 列的格子。两个格子是相邻的当且仅当它们有一条公共边,特殊地, $(x,1)$ 和 $(x,m)$ 红包也视为是相邻的,但是他不把 $(1,x)$ 和 $(n,x)$ 当做是相邻的。

对于一个有 $K$ 个格子被弄坏的南瓜灯,如果它能被制作成工艺品,当且仅当对于任意两个没有被弄坏的格子,都存在且仅存在一条连接它们的简单路径。一条简单路径定义为一个只包含没有被弄坏的格子的序列 $A_1$ 至 $A_n$ ,其中对于任意的 $1 \leq i < n$ 都有 $A_i$ 和 $A_{i+1}$ 是相邻的,且每一个格子在序列中至多出现了一次。

现在红包有 $T$ 个南瓜灯,他想让你帮他分别判断每一个南瓜灯能不能被做成工艺品。

输入格式

第一行一个正整数 $T$,表示南瓜灯数目。

对于每一个南瓜灯,第一行是三个整数 $n,m,K$,表示南瓜灯的大小和被弄坏的格子数。

接下来 $K$ 行每行包含两个整数 $x,y$($1 \leq x \leq n,1 \leq y \leq m$),表示第 $x$ 行第 $y$ 列的格子被弄坏了。

数据保证 $n,m \geq 3$,$0 \leq K < nm$ 且不会重复描述一个被弄坏的格子。

输出格式

对于每一个南瓜灯,输出一行,如果这个南瓜灯能被做成工艺品,那么输出 "Yes",否则输出 "No"。

样例一

input

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

output

No
Yes
No

explanation

对于第一组数据,$(1,1)$ 到 $(1,2)$ 有两条简单路径,分别是 $(1,1),(1,2)$ 和 $(1,1),(1,3),(1,2)$。

对于第三组数据,$(1,2)$ 到 $(2,1)$ 不存在简单路径。

样例二

见样例数据下载。

限制与约定

对于所有数据,$T \leq 10$。

测试点编号$n, m$ 的规模$K$ 的规模
1$n,m \leq 4$$K \leq 10^5$
2$n,m \leq 100$
3
4$n,m \leq 1000$
5
6$n,m \leq 10^9$$K \leq 1000$
7
8$K \leq 10^5$
9
10

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载