题目背景

想不到吧还有一个网格题。

你觉得这个题是 East ver. 还是 Ease ver. 呢？

你觉得这个题是 ∃asy ver. 还是 ∀asy ver. 还是 ∅asy ver. 呢？

你觉得这个题是 East vera 还是 East verb 还是 East vers 还是 East vert 呢？

你觉得这个题是 Easy vre. 还是 Easy evr. 还是 Easy erv. 还是 Easy rve. 还是 Easy rev. 呢？

题目描述

对于一张 $n\times m$ 的网格图，给出定义：行从 $1\sim n$ 编号，列从 $1\sim m$ 编号。

每个点可用它所在的行编号 $i$ 与所在的列编号 $j$ 表示为 $(i, j)$。

点 $(i,j)$ 与点 $(i,j+1)$ 间连有一条无向边，其中 $1\le i\le n, 1\le j<m$。

点 $(i, j)$ 与点 $(i+1,j)$ 间连有一条无向边，其中 $1\le i< n, 1\le j \le m$。

定义两个点相邻当且仅当它们之间有连边。

---

有一张 $n\times m$ 的网格图 $G=(V,E)$。

给定其中两两没有公共点的边集 $E_{1}$ 满足 $|E_{1}|=k$。

你需要求一个两两没有公共点的边集 $E_{2}$ 满足：

• $E_{1}\subseteq E_{2}\subseteq E$。

• $G$ 删除掉 $E_{2}$ 的边后不存在生成树。

你需要求 $|E_{2}|-k$ 的最小值，如果不存在 $E_{2}$ 则输出 $-1$。

输入格式

一行三个正整数 $n, m, k$。

接下来 $k$ 行，每行四个整数 $x_1,y_1,x_2,y_2$，表示 $E_1$ 中的边，其两端为 $(x_1,y_1)$ 和 $(x_2,y_2)$。

保证 $|x_1-x_2|+|y_1-y_2|=1$，即图上存在这条边。

保证给定的边满足任意两条边没有公共点。

输出格式

输出一行，如果存在 $E_2$ 输出 $|E_2|-k$ 的最小值，否则输出 $-1$。

2 2 1
1 1 1 2

1

2 2 2
1 1 1 2
2 1 2 2

0

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

-1

1 1 0

-1

提示

「样例解释 #1」

如下图，$E_2=E_1$ 时会存在一个生成树，$E_2=E_1\cup ((2,1),(2,2))$ 符合条件。

「样例解释 #2」

$E_2=E_1$ 符合条件。

「样例解释 #3」

如下图，不存在 $E_1\subsetneq E_2$ 的方案，而 $E_2=E_1$ 时有生成树，因而不存在 $E_1$。

「样例解释 #4」

孤立点是生成树。

「数据范围」

本题采用捆绑测试。

对于所有测试数据，保证 $1\le n,m\leq 3000$，$0\leq k\leq 2\times 10^5$。

子任务	$n$	$m$	$k$	分值
$0$	$\leq 3$		$=0$	$30$
$1$	$=1$	$\leq 3000$	$\leq 1500$	$10$
$2$	$\leq 3000$		$\leq 2\times 10^5$	$60$