远古文明的宝藏牵动着每个寻宝人的心。相传，遥远而神秘的 A 国国王建立了一座迷宫。迷宫里存放了许多绝世珍宝，这些珍宝将属于勇敢而智慧的寻宝人。

小 A 作为经验老到的寻宝人，他的足迹已经踏遍世界每个有着宝藏传说的角落。当他听说了 A 国的宝藏秘闻之后，四处搜寻宝藏的蛛丝马迹，搜集了很多有用的材料。

根据小 A 搜集的藏宝图。存放宝藏的迷宫是一个 N 行 M 列大小的矩阵。矩阵的每个点的位置上设有一个房间（房间的坐标从 1,1 \sim N,M）。其中有 C 个房间存放了宝物，这 C 个房间中，每个房间都存放了 1 件价值连城的珍宝。

迷宫的墙壁坚不可摧，没有任何门窗可以直接进入迷宫。要拿到这些宝物有 3 个难点：进入迷宫中有宝物的房间、从一个有宝物的房间移动到另一个有宝物的房间、从迷宫中带着宝物出来。

对于进出迷宫，小 A 已经有了办法，他设计了一个弹射装置，可以将自己从迷宫外弹射到迷宫内的任意房间中。

根据藏宝图的记载，迷宫内除了有宝物的房间，其余房间布满陷阱，如果误入没有宝物的房间，寻宝人必将有去无回。寻宝人在有宝物的房间之间移动的唯一方法，就是按照藏宝图的指示，在房间中找到机关，打开去往其他存放宝物房间的密道。（请注意：每个有宝物的房间内一定有一个机关通往其他有宝物的房间，没有宝物的房间内部只有陷阱，没有机关）

密道有 3 类：

第 1 类：可以通过密道，进入本行的任意其他的房间。

第 2 类：可以通过密道，进入本列的任意其他的房间。

第 3 类：可以通过密道，进入本房间相邻的周围 8 个房间中的任何其他的房间，当然如果当前房间在矩阵的边界上，可能没有 8 个相邻的房间。

每个房间只会有打开其中一类密道的机关，小 A 可以重复的进入同一个密道，也可以重复的进入同一个房间，没有次数限制。

当小 A 觉得自己不可能获得更多的宝物时，他会启动弹射装置，把自己弹射到迷宫外面。这个弹射装置只能用 2 次（一次用于进入迷宫，一次用于弹出迷宫），当小 A 把自己弹射到迷宫外面之后，就再也无法进入迷宫了。

请编程计算出，根据小 A 获得的藏宝图，他最多能获得多少件宝物？

第 1 行输入三个整数 C,N,M，数字之间用空格隔开。

接下来的 C 行，每行有 3 个整数 X_i,Y_i,Z_i ，代表在坐标为 X_i,Y_i 的房间中，有一件宝物，房间内的机关类型是第 Z_i 类的。

输出一个整数，代表小 A 最多获得宝物的件数，也就是他最多能进入的不同房间的数量。

样例 1 说明

样例 1 有多种不同的取法，此处列举其中 2 种取法。沿着绿色的线路或者蓝色的线路，都能获得 2 件宝物。因此，最多能获得 2 件宝物。

样例 2 说明

样例 2 从 4,4 点出发，沿着下图所示的线路，可以获得 5 件宝物。

数据范围

对于 10\% 的数据满足，1 \le N,M \le 20，1 \le C \le 16。

对于另外 10\% 的数据满足，1 \le N,M \le 1000，1 \le C \le 300。

对于另外 20\% 的数据满足，1 \le N,M \le 5000，1 \le C \le 50000。

对于另外 10\% 的数据满足，1 \le N,M \le 10^5，1 \le C \le 500。

对于另外 50\% 的数据满足，1 \le N,M \le 10^6，1 \le C \le 10^5。

对于 100\% 的数据，C \le N \times M，1 \le X_i \le N，1 \le Y_i \le M。

月赛Tarjan强连通分量2023