Daisy 喜欢在迷宫中行走，以缓解一天工作后的压力。她喜欢的迷宫由一组房间组成，其中有一个入口房间和一个出口房间，每个房间都有几扇通往其他房间的单向门。Daisy 的目标是找到一条从入口到出口的路径。
Daisy 有一种解决迷宫的技巧。她注意到任何房间的不同门都有不同的颜色，因此她可以通过记录路径上门的颜色来记住她的路径。为此，她在进入迷宫前查看平面图，并根据她需要经过的门的颜色构建一副彩色卡片。每当她进入一个房间时，她都会穿过与她牌堆顶端卡片颜色相同的门，然后丢弃这张卡片。
有时 Daisy 的牌堆是“不完整”的，她到达一个房间时，牌堆是空的，或者牌堆顶端的卡片颜色与房间内任何门的颜色都不匹配。在这种情况下，Daisy 会穿过房间里的一扇门，并且不是丢弃顶端的卡片，而是在牌堆顶部增加一张与她所选门颜色相同的卡片。
让我们考虑以下包含三个房间和三扇门的迷宫示例：一扇从入口到房间 1 的红色门，一扇从房间 1 回到入口的红色门，以及一扇在房间 1 和出口之间的蓝色门。在这个示例迷宫中（如下图所示）：
- 如果 Daisy 开始时牌堆顶端是一张红卡，下面是一张蓝卡，她会去房间 1 并丢弃红卡，然后去出口并丢弃蓝卡；
- 如果 Daisy 开始时牌堆只有一张红卡，那么她第一步必然会去房间 1，丢弃红卡，从那里她可以选择走蓝色门并离开（最后牌堆是否为空无关紧要），或者她可以选择走红色门并回到初始状态：在入口房间，手里只有一张红卡；
- 如果她开始时或到达入口房间时牌堆为空，她必然会无限循环。事实上，入口只有一扇通往房间 1 的门。一旦她到达房间 1，她的牌堆顶端有一张红卡，因此她必须走红色门并丢弃这张卡，这又把她带回了牌堆为空的入口房间。
入口 房间 1 出口
Daisy 知道，在所有的迷宫中，只要有合适的牌堆，她总能从入口房间走到出口房间。然而，有些牌堆不允许她逃脱，无论她做出什么选择。她想知道：允许她逃脱的牌堆的最小尺寸是多少？Daisy 给了你迷宫的平面图，并请你帮她确定如果她做出正确的选择，能够让她从入口房间走到出口的牌堆的最小尺寸。
输入格式
第一行包含三个整数 $R$、$D$ 和 $C$，用空格分隔。$R$ 是房间数量，$D$ 是门的数量，$C$ 是颜色数量。房间编号从 $0$ 到 $R - 1$，颜色编号从 $0$ 到 $C - 1$。
接下来的 $D$ 行，每行描述一扇门，包含三个整数 $f$、$t$ 和 $c$，用空格分隔，满足 $0 \le f \le R - 1$，$0 \le t \le R - 1$，$f \neq t$，且 $0 \le c \le C - 1$。这表示有一扇从房间 $f$ 到房间 $t$ 的门，且该门的颜色为 $c$。
输出格式
输出应包含一行，仅含一个整数：使得 Daisy 在做出正确选择的情况下，能够从入口（编号为 $0$ 的房间）走到出口（编号为 $R - 1$ 的房间）的牌堆的最小整数尺寸 $S$。
数据范围
- $2 \le R \le 50$
- $2 \le D \le 100$
- $2 \le C \le 20$
样例
样例输入 1
4 4 2 0 1 0 1 2 0 2 0 0 1 3 1
样例输出 1
0
说明 1
- Daisy 从房间 0 开始，牌堆为空
- 她带着牌堆中的卡片 0 前往房间 1
- 她带着空牌堆前往房间 2
- 她带着牌堆中的卡片 0 前往房间 0
- 她带着空牌堆前往房间 1
- 她现在可以选择前往出口。
样例输入 2
3 3 2 0 1 1 1 0 1 1 2 0
样例输出 2
1
说明 2
此示例对应于文中给出的示例，其中红色表示为 1，蓝色表示为 0。