#4651. [Noi2016]网格

内存限制:512 MiB 时间限制:50 Sec

题目描述

跳蚤国王和蛐蛐国王在玩一个游戏。
他们在一个 n 行 m 列的网格上排兵布阵。其中的 c 个格子中 (0≤c≤nm),每个格子有一只蛐蛐,其余的格子中,每个格子有一只跳蚤。
我们称占据的格子有公共边的两只跳蚤是相邻的。
我们称两只跳蚤是连通的,当且仅当这两只跳蚤相邻,或存在另一只跳蚤与这两只跳蚤都连通。
现在,蛐蛐国王希望,将某些(0 个,1 个或多个)跳蚤替换成蛐蛐,使得在此之后存在至少两只跳蚤不连通。
例如:我们用图表示一只跳蚤,用图表示一只蛐蛐,那么图 1 描述了一个 n=4,m=4,c=2的情况。
这种情况下蛐蛐国王可以通过将第 2 行第 2 列,和第 3 行第 3 列的两只跳蚤替换为蛐蛐,从而达成他的希望,如图 2 所示。并且,不存在更优的方案,但是可能存在其他替换 2 只跳蚤的方案。
你需要首先判断蛐蛐国王的希望能否被达成。如果能够达成,你还需要最小化被替换的跳蚤的个数。
 

输入格式

每个输入文件包含多组数据。
输入文件的第一行只有一个整数 TT,表示数据的组数。保证 1≤T≤20。
接下来依次输入 TT 组数据,每组数据的第一行包含三个整数 n, m, c。
保证1≤n,m≤10^9,0≤c≤min(nm,105)
接下来 c行,每行包含两个整数 x, y表示第 x 行,第 y 列的格子被一个蛐蛐占据(1≤x≤n,1≤y≤m)每一组数据当中,同一个蛐蛐不会被多次描述。
同一行相邻的整数之间由一个空格隔开。
1≤n,m≤10^9, 0≤c≤nm, 1≤x≤n, 1≤y≤m
1≤T≤20。我们记 ∑c为某个测试点中,其 T 组输入数据的所有 c 的总和,∑c≤10^5

输出格式

对于每一组数据依次输出一行答案。
如果这组数据中,蛐蛐国王的希望不能被达成,输出-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
explanation
第一组数据就是问题描述中的例子。
对于第二组数据,可以将第 2 行第 2 列的一只跳蚤替换为蛐蛐,从而使得存在两只跳蚤不连通
并且不存在更优的方案。
对于第三组数据,最初已经存在两只跳蚤不连通,故不需要再进行替换。
对于第四组数据,由于最多只有一只跳蚤,所以无论如何替换都不能存在两只跳蚤不连通

数据范围与提示