# 地牢房间的行为等价

参考时间限制：0.5 秒；内存限制：128 MiB。实际时限取目标环境中最慢正式文件的标程中位耗时乘2，再按0.5秒向上取整。见[评测环境](../../../docs/评测环境与性能.md)。

## 背景故事

探险机器人看不到房间的编号，只能发出方向指令，并观察是否撞上障碍。它希望把无论怎样试探都无法区分的房间归为一类。

(本故事由GPT-6重写)

## 形式化问题描述

地牢有 $n$ 个房间，编号为 $1,\ldots,n$ ，方向指令编号为 $1,\ldots,k$ .给定转移 $a_{u,j}\in[0,n]$ .站在房间 $u$ 发出指令 $j$ 时，若 $a_{u,j}>0$ ，便进入该房间；若 $a_{u,j}=0$ ，便遇到障碍，本次指令序列立即结束。

一次试验从指定房间出发，执行任意有限指令序列，结果只记录“是否遇到过障碍”。空指令序列的结果为否。若对每个有限指令序列，从两个房间出发的结果都相同，称这两个房间行为等价。每次试验都重新从指定房间开始。

求这 $n$ 个房间的等价类数量。障碍编号零不是房间，不计入答案。

![三间房间依次通向障碍](assets/example.svg)

图对应样例3：从房间1、2、3出发，分别在第3、2、1条指令遇到障碍，因此是三种类型。

## 输入格式

第一行两个整数 `n k` .接下来 $n$ 行，第 $u$ 行包含 $k$ 个整数 $a_{u,1},\ldots,a_{u,k}$ .

## 输出格式

输出一个整数，表示房间的行为等价类数量。

## 样例 1

### 输入

```text
4 2
2 0
2 0
4 0
0 0
```

### 输出

```text
3
```


## 样例 2

### 输入

```text
3 1
2
3
1
```

### 输出

```text
1
```


## 样例 3

### 输入

```text
3 1
2
3
0
```

### 输出

```text
3
```

## 数据范围与保证

$1\le n\le200000$ ，$1\le k\le26$ ，$nk\le2000000$ ，$0\le a_{u,j}\le n$ .

由 Codex（GPT-6）补齐并记录为重新设计：以任意指令序列的障碍行为定义等价关系，补齐输出目标、输入格式及完整数据范围。

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |

共有10个正式文件，每个10%。

[生成说明](tests/README.md)。