棋盘游戏

题目描述:

为了增强幼儿园小朋友的数数能力，小虎老师给了一个家庭游戏作业。让小虎那一块空的围棋盘，随机在一些方格中放些棋子（有黑白两种颜色），如果一个方格和它的上、下、左、右四个方格之一有相同颜色的棋子，则认为两个格子是相互连通的。这期间，要求小虎不断统计共有多少个连通块。

如下图是一个 \(5\times 9\) 的一块棋盘，其中 `.` 表示空格，`*` 表示黑棋子，`@`表示白棋子。

则有 \(4\) 块连通子块。

.  .  .  .  .  .  .  .  .
.  .  *  *  .  .  @  @  .
.  *  *  @  @  .  @  @  .
.  .  *  @  .  .  *  .  .
.  .  .  .  .  .  .  .  .

哥哥大虎在一边看一边想，如果棋盘是 \(N\times N\) 的，共放了 \(M\) 个棋子，如何使用计算机解决这个问题呢？

输入格式:

第一行两个整数：\(N,M\)。

接下来有 \(M\) 行，每行三个整数：\(c, x, y\)。分别表示依次放入棋子的颜色（\(0\) 表示白色，\(1\) 表示黑色）、要放入格子的横坐标和格子的纵坐标。

输出格式:

共 \(M\) 行。第 \(i\) 行一个整数，表示放入第 \(i\) 个棋子后，当前有多少个棋子连通块。

样例输入:

样例1
3 5    
1 1 1  
1 1 2  
0 2 2  
1 3 1  
1 2 1
样例2
3 5
1 1 2
1 2 1
1 3 2
1 2 3
1 2 2

样例输出:

样例1
1 
1 
2 
3 
2
样例2
1
2
3
4
1

提示:

对于 \(30\%\) 数据：\(1\le N \le 10\)。

对于 \(60\%\) 数据：\(1\le N\le 100\)。

对于 \(100\%\) 数据：\(1\le N\le 500\)，\(1\le M \le N \times N\)，\( 0 \le c \le 1\)，\( 1\le x, y \le N\)。

时间限制: 1000ms
空间限制: 128MB

---