题目描述(ID:12369)
标题: 拯救实验体-简化版
标签:
详情:
邪恶大魔头林克有n个秘密实验室,编号1到n。每个实验室内都关押了一名实验体。这些实验室由若干条单行道相连。啊哈沃德是编程星球的拯救者,他想到尽可能多的实验室去解救实验体。
啊哈沃德成功占领了1号实验室。他将从1号实验室出发,最后回到1号实验室。他想经过尽可能多的实验室,而且一个实验室可以经过多次。因为实验室是单行道连接,这给啊哈沃德的解救工作带来了很大的不便。啊哈沃德可以偷偷逆向行走一次,但最多只能有一次逆行,否则会触发监控系统警报从而被星球上的交警带走。请求解啊哈沃德最多能解救多少个实验室的实验体。
【保证给出数据为有向无环图】
输入格式:
第一行给出实验室个数数n和道路数m。
接下来n行,第i+1行给出第i个实验室的实验体个数
接下来m行,每行x和y表明有x到y的单向边,不会有重复的道路出现。
输出格式:
一个数,逆行一次最多可以解救几个实验体。
限制: 1 <= N, M <= 100,000
样例:

输入

5 7
1
3
1
1
1
3 2
2 1
5 3
5 2
5 1
5 4
4 1

输出

6
登录并解答