logo AlgoBeat OnlineJudge
登录 注册

#10191. 转发

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: AlgoBeat 官方账号

题目描述

出题人:LZA

才华横溢的 Poi 同学会自己谱曲还能自己弹出来,有一天他想把自己的作品发到一个群里给大家康康,结果群主因为嫉妒把他禁言了...

于是他来到了 20 新生群。

Poi 知道新生群里潜伏着很多学长,而且这些学长会把这些曲子转发到自己常去的群里,然后那个群里又有人会转发到其他群里...这样他的作品就可以一直被转发到目标群里面。Poi 对每一个群里的学长构成了如指掌,所以他知道从 群到 群最多可以转发多少条曲子(学长们的品味都不一样,所以可以保证一个群里同一条曲子不会被同时转发到多个群里面)。

Poi 的计划就是在 20 新生群(编号 )发他的作品集。现在 Poi 想知道这个计划能让多少条曲子被转发到目标群(编号 )。

输入格式

输入共 行。

第一行:两个整数

接下来 行,每行三个整数 ,代表从编号 的群到编号 的群最多可以转发 条曲子。

输出格式

一个整数,代表目标群可以收到的最大曲子数量。

样例

输入样例 1

6 6
0 1 2
0 2 9
1 2 1
2 4 7
3 5 7
4 5 4

输出样例 1

4

输入样例 2

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

输出样例 1

3

数据范围与提示

  • 对所有测试点,都保证:对于任意群都可以向至少一个其他群转发(目标群不会有任何转发);一个群不会转发到自己。
  • , ,
  • 所有测试点保证中间计算不超过 signed int32 范围。