UOJ Logo Universal Online Judge

UOJ

#220. 【NOI2016】网格

统计

跳蚤国王和蛐蛐国王在玩一个游戏。

他们在一个 $n$ 行 $m$ 列的网格上排兵布阵。其中的 $c$ 个格子中 $(0 \le c \le nm)$,每个格子有一只蛐蛐,其余的格子中,每个格子有一只跳蚤。

我们称占据的格子有公共边的两只跳蚤是相邻的。

我们称两只跳蚤是连通的,当且仅当这两只跳蚤相邻,或存在另一只跳蚤与这两只跳蚤都连通

现在,蛐蛐国王希望,将某些(0 个,1 个或多个)跳蚤替换成蛐蛐,使得在此之后存在至少两只跳蚤不连通

例如:我们用图flea表示一只跳蚤,用图cricket表示一只蛐蛐,那么图 1 描述了一个 $n=4, m=4, c=2$ 的情况。

这种情况下蛐蛐国王可以通过将第 2 行第 2 列,和第 3 行第 3 列的两只跳蚤替换为蛐蛐,从而达成他的希望,如图 2 所示。并且,不存在更优的方案,但是可能存在其他替换 2 只跳蚤的方案。

图1
图1
图2
图2

你需要首先判断蛐蛐国王的希望能否被达成。如果能够达成,你还需要最小化被替换的跳蚤的个数。

输入格式

每个输入文件包含多组数据。

输入文件的第一行只有一个整数 $T$,表示数据的组数。保证 $1 \le T \le 20$。

接下来依次输入 $T$ 组数据,每组数据的第一行包含三个整数 $n,~m,~c$。保证$1 \le n,m \le 10^9, 0 \le c \le \min(nm,10^5)$。

接下来 $c$ 行,每行包含两个整数 $x,~y$,表示第 $x$ 行,第 $y$ 列的格子被一个蛐蛐占据($1 \le x \le n, 1 \le y \le m$)。每一组数据当中,同一个蛐蛐不会被多次描述。

同一行相邻的整数之间由一个空格隔开。

输出格式

对于每一组数据依次输出一行答案。

如果这组数据中,蛐蛐国王的希望不能被达成,输出 $−1$。否则,输出被替换的跳蚤的个数的最小值。

样例一

input

4
4 4 2
1 1
4 4
2 3 1
1 2
2 2 2
1 1
2 2
1 1 0

output

2
1
0
-1

explanation

第一组数据就是问题描述中的例子。

对于第二组数据,可以将第 2 行第 2 列的一只跳蚤替换为蛐蛐,从而使得存在两只跳蚤不连通,并且不存在更优的方案。

对于第三组数据,最初已经存在两只跳蚤不连通,故不需要再进行替换。

对于第四组数据,由于最多只有一只跳蚤,所以无论如何替换都不能存在两只跳蚤不连通

样例二

见样例数据下载。

限制与约定

对于全部的测试点,保证 $1 \le T \le 20$。我们记 $\sum c$ 为某个测试点中,其 $T$ 组输入数据的所有 $c$ 的总和。对于所有的测试点,$\sum c \le 10^5$。

对于全部的数据,满足 $1 \le n,m \le 10^9,~0 \le c \le nm,~1 \le x \le n,~1 \le y \le m$。

每个测试点的详细数据范围见下表。表中的 $n,m,c$ 均是对于单个输入数据(而非测试点)而言的,也就是说同一个测试点下的 $T$ 组数据均满足限制条件;而 $\sum c$ 是对于单个测试点而言的。为了方便阅读,“测试点”一列被放到了表格的中间而不是左边。

$n,m$ 测试点编号 $c$
$nm \le 4$ 1 $c \le nm$
$nm \le 8$ 2
$nm \le 15$ 3
$nm \le 30$ 4
$nm \le 100$ 5
$nm \le 300$ 6
$nm \le 1000$ 7
$nm \le 20000$ 8 $c \le 5$
9 $c \le 15$
10 $c \le 30$
$n,m \le 20000$ $nm \le 20000$ 11 $\sum c \le 20000$
$nm \le 10^5$ 12
$nm \le 3 \times 10^5$ 13
$nm \le 10^6$ 14
$nm \le 10^9$ 15
$n,m \le 10^5$ 16 $\sum c \le 10^5$
$n,m \le 10^9$ 17 $c=0$
18 $c \le 1$
19 $c \le 2$
20 $c \le 3$
21 $c \le 10$
22 $c \le 30$
23 $c \le 300$
24 $\sum c \le 20000$
25 $\sum c \le 10^5$

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

空间限制:$1\texttt{GB}$

下载

样例数据下载