对于一张 $N\times M$ 的网格图 $G$，我们定义路径 $P$ 是 $G$ 的欧拉路当且仅当 $P$ 经过任意相邻网格对各一次，且 $P$ 中相邻两个格子 $P_i, P_{i+1}$ 在 $G$ 中也一定有公共边。

现在从 $G$ 中删去 $K$ 个格子（这意味着与这些格子相邻的边也被一并删去），使得剩余的图 $G'$ 中有欧拉路，求 $K$ 的最小值。