UVA13256 Hip-$n$

Hip-n 是一种两名玩家轮流在非空的 $n\times n$ 棋盘的自由格上放置代币的游戏。 游戏输给了第一个玩家放置四个标记来识别正方形的顶点：它们可以是任何大小，也可以倾斜任何角度。 当棋盘上满是代币并且没有玩家输时，游戏以平局结束。 下图描绘了一个 $6\times6$ 的棋盘和三个正方形的例子：第一个在这些正方形的顶点上放置四个代币的玩家输掉了游戏(就是上面那一张) 。 当然，在 $6\times6$ 的棋盘中输掉一场比赛还有更多的方式。 你的任务是创建一个程序，通过识别输了的玩家或识别平局，来决定一个被描述为一系列游戏的 Hip-n 游戏的结果。

输入由几个测试用例组成。当没有更多的案例需要测试时，它就结束了。 每个测试用例的第一行包含一个整数 $n$，表示棋盘的行数和列数。 下一行在棋盘中包含 $n^2$ 对不同的空分隔整数 $r$ 和 $c$ ：每一个这样的对标识对应玩家在 $(r,c)$ 处放置的代币。 你可以假设玩家1做出第一步，玩家2做出第二步，玩家1做出第三步，以此类推。

对于每个测试用例，如果游戏以平局结束，则输出'0'；如果玩家 1 输了，则输出'1'；如果玩家 2 输了，输出'2'。

$1 \le n \le 200，0 \le r＜n，0 \le c＜n$