SP3644 WINSTRAT - Winning Strategy

有一个$n \times n$的表格，行号和列号都从$0$到$n-1$。表格中的每个单元格有一个值，可能是 $0$ 或 $1$。在这个表中，总共有$m$个单元格的值是$0$，剩下的单元格值为$1$。两名玩家轮流进行游戏，第一个玩家先动手。每名玩家在每次轮到自己时只能执行一步操作。若某玩家无法执行任何操作，则他输掉比赛，而对方胜利。 玩家的合法操作是翻转某个矩形的四个角上的值（$0$变$1$或$1$变$0$），并且该矩形需要满足以下条件： - 矩形包含超过1行和超过1列。 - 四个角中行和列的坐标都最大的那个单元格的值必须为$0$。 你的任务是分析表格中单元格的值，帮助第一个玩家找到一种必胜策略，也就是说，不管对手如何应对，第一个玩家总是能赢。

输入文件包含若干组数据。第一行是一个正整数，表示数据集的数量，不超过$20$。接下来的格式描述这些数据集。 对于每一组数据，第一行是一个整数$n$（$0 < n < 1000$），表示表格的大小。紧接着的一行是一个整数$m$（$0 < m < n^2$），表示值为 $0$ 的单元格数量。接下来的$m$行，每行包含两个整数$r_i$和$c_i$（$0 \leq r_i, c_i < n$），表示某个值为$0$的单元格的坐标。

对于每组数据，输出一行。若第一个玩家有必胜策略，输出$1$，否则输出$0$。

- $0 < n < 1000$ - $0 < m < n^2$ **本翻译由 AI 自动生成**