#P1173. [NOI2016] 网格

    ID: 217 远端评测题 2000ms 1024MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>贪心高精度2016NOI 系列O2优化枚举暴力

[NOI2016] 网格

题目描述

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

他们在一个 nnmm 列的网格上排兵布阵。其中的 cc 个格子中 (0cnm)(0 \leq c \leq n\cdot m),每个格子有一只蛐蛐,其余的格子中,每个格子有一只跳蚤。

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

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

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

例如:图 11 描述了一个 n=4n=4m=4m=4c=2c=2 的情况。

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

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

输入格式

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

输入文件的第一行只有一个整数 TT,表示数据的组数。

接下来依次输入 TT 组数据,每组数据的第一行包含三个整数 n,m,cn, m, c

接下来 cc 行,每行包含两个整数 x,yx, y 表示第 xx 行,第 yy 列的格子被一个蛐蛐占据。每一组数据当中,同一个蛐蛐不会被多次描述。

输出格式

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

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

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

提示

样例解释

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

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

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

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

数据范围

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

对于全部的数据,满足 1n,m1091 \leq n,m \leq 10^90cn×m0 \leq c \leq n \times m1xn,1ym1 \leq x \leq n, 1 \leq y \leq m

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

n,mn,m 测试点 cc
nm4n*m\leq 4 11 cnmc\leq n*m
nm8n*m\leq 8 22
nm15n*m\leq 15 33
nm30n*m\leq 30 44
nm100n*m\leq 100 55
nm300n*m\leq 300 66
nm103n*m\leq 10^3 77
nm2×104n*m\leq 2\times 10^4 88 c5c\leq 5
99 c15c\leq 15
1010 c30c\leq 30
n,m2×104,nm2×104n,m\leq 2\times 10^4,n*m\leq2\times 10^4 1111 c2×104\sum c\leq 2\times 10^4
n,m2×104,nm105n,m\leq 2\times 10^4,n*m\leq10^5 1212
n,m2×104,nm3×105n,m\leq 2\times 10^4,n*m\leq3\times 10^5 1313
n,m2×104,nm106n,m\leq 2\times 10^4,n*m\leq10^6 1414
n,m2×104,nm109n,m\leq 2\times 10^4,n*m\leq 10^9 1515
n,m105n,m\leq 10^5 1616 c105\sum c\leq 10^5
n,m109n,m\leq 10^9 1717 c=0c=0
1818 c1c\leq 1
1919 c2c\leq 2
2020 c3c\leq 3
2121 c10c\leq 10
2222 c30c\leq 30
2323 c300c\leq 300
2424 c2×104\sum c\leq 2 \times 10^4
2525 c105\sum c\leq 10^5