题目描述

:::align{center}

:::

Daisy 喜欢在迷宫中散步，以缓解漫长工作日带来的压力。她喜欢的迷宫都由一组房间组成，有一个入口房间和一个出口房间，每个房间中有若干扇单向门通往其他房间。Daisy 的目标是找到一条从入口到出口的路径。

Daisy 有一套解迷宫的方法。她注意到，每个房间中不同的门颜色不同，因此她可以通过记录路径上门的颜色来记住自己走过的路线。为此，她在进入迷宫之前查看平面图，并构建一副由彩色卡片组成的牌堆，牌堆中的卡片颜色对应她需要依次经过的门的颜色。每当她进入一个房间时，她就从牌堆顶部取出一张卡片，然后走颜色与这张卡片相同的门，之后丢弃这张卡片。

有时 Daisy 的牌堆是"不完整的"，她会到达一个房间时发现牌堆为空，或者顶部的卡片颜色对应不上房间中的任何一扇门。在这种情况下，Daisy 会选择房间中的一扇门通过，并且不是丢弃顶部的卡片，而是在牌堆顶部添加一张她所经过的门的颜色的卡片。

让我们考虑以下例子：一个有三个房间和三扇门的迷宫，一扇红色的门从入口通向房间 1，第二扇红色的门从房间 1 返回入口，以及一扇蓝色的门连接房间 1 和出口。在这个示例迷宫（如下图所示）中：

• 如果 Daisy 开始时牌堆顶部是一张红色卡片，下面是一张蓝色卡片，她会先走到房间 1 并丢弃红色卡片，然后走到出口并丢弃蓝色卡片；
• 如果 Daisy 开始时牌堆只有一张红色卡片，那么她第一步必然走到房间 1，丢弃红色卡片，然后她可以选择走蓝色门离开（最后牌堆是否为空无关紧要），或者她也可以选择走红色门，回到初始状态：在入口房间且牌堆中只有一张红色卡片；
• 如果她在入口房间时牌堆为空，无论是开始时还是后来到达时，她必然会无限循环。因为入口只有一扇门通往房间 1。一旦她到达房间 1，她的牌堆顶部有一张红色卡片，因此她必须走红色门并丢弃这张卡片，这会使她回到入口房间且牌堆为空。

:::align{center}

:::

Daisy 知道，在她所有的迷宫中，只要选择合适的牌堆，她总能从入口房间到达出口房间。然而，有些牌堆无论她如何选择都无法逃脱。她想知道：能让她逃脱的牌堆的最小大小是多少？Daisy 把迷宫平面图交给你，请你帮她确定，在做出正确选择的前提下，能使她从入口房间到达出口房间的牌堆的最小大小。

输入格式

第一行包含三个整数 $R$、$D$ 和 $C$，用空格分隔。$R$ 是房间数量，$D$ 是门的数量，$C$ 是颜色数量。房间编号为 $0$ 到 $R-1$，颜色编号为 $0$ 到 $C-1$。

接下来的 $D$ 行，每行描述一扇门，包含三个整数 $f$、$t$ 和 $c$，用空格分隔，满足 $0 \leq f \leq R-1$，$0 \leq t \leq R-1$，$f \neq t$，$0 \leq c \leq C-1$。这表示有一扇从房间 $f$ 到房间 $t$ 的门，该门的颜色为 $c$。

输出格式

输出应包含一行一个整数：最小的整数 $S$，使得存在一副由 $S$ 张卡片组成的牌堆，能够让 Daisy 在做出正确选择的前提下，从入口（编号为 $0$ 的房间）到达出口（编号为 $R-1$ 的房间）。

4 4 2
0 1 0
1 2 0
2 0 0
1 3 1

0

3 3 2
0 1 1
1 0 1
1 2 0

1

提示

限制条件

• $2 \leq R \leq 50$；
• $2 \leq D \leq 100$；
• $2 \leq C \leq 20$。

样例解释 1

• Daisy 从房间 0 开始，牌堆为空；
• 她走到房间 1，牌堆顶部多了一张颜色为 $\textbf{0}$ 的卡片；
• 她走到房间 2，牌堆为空；
• 她走到房间 0，牌堆顶部多了一张颜色为 $\textbf{0}$ 的卡片；
• 她走到房间 1，牌堆为空；
• 此时她可以选择去往出口。

样例解释 2

这个例子对应正文中描述的那个例子，其中红色表示为 1，蓝色表示为 0。

由 Deepseek V4 初步翻译，人工修缮。