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$ 。输入保证一定有解。

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=229&page=show_problem&problem=3067 [PDF](https://uva.onlinejudge.org/external/119/p11916.pdf) 



4
3 3 0 1728
4 4 2 186624
3 1
3 3
2 5 2 20
1 2
2 2
2 3 0 989323

Case 1: 3
Case 2: 3
Case 3: 2
Case 4: 20