UVA11916 Emoogle Grid

给一个 $M$ 行 $N$ 列的网格涂上 $K$ 种颜色，其中有 $B$ 个格子不用涂色，其他每个格子涂一种颜色，同一列中的上下两个相邻格子不能涂相同颜色。 给出涂色方案$\mod 100000007$ 的结果$R,N,K,B$ 个格子的位置，求出最小的 $M$ 。 $1\le M,N\le 10^8$ $0\le B\le500$ $2\le K\le10^8$

输入第一行为数据组数 $T(T\le150)$ 。每组数据第一行为 $4$ 个整数 $N,K,B,R(0\le R\le100000007)$ 。以下 $B$ 行每行为两个整数 $x$ 和 $y(1\le x\le M,1\le y\le N)$ ，即每个不需要涂色的格子的行列编号。这些格子的位置各不相同。

对于每组数据，输出最小的 $M$ 。输入保证一定有解。