2944 - 美食之旅

题目描述

A 是一位热衷于品尝各类美食的城市旅行者,他计划在 N 个不同城市(城市编号为 1 \sim N)之间进行一次巡回旅行。这些城市由若干条单向飞行航线相连,任意两个城市之间都可以坐大巴到达。为了品尝更多城市的特色美食,罗杰希望尽可能多地访问不同城市。

A 的旅行1 号城市出发,最终要求返回到 1 号城市。由于航线是单向的,这给小 A 的行程安排带来了挑战,他可能无论如何也无法访问完所有的城市。

A 的目标是:尽可能访问更多的城市,他可以重复访问同一个城市。

为了实现这一目标,小 A 决定在旅行过程中,如果编号为 U 的城市有单向航班到编号为 V 的城市,但编号为 V 的城市没有单向航班到编号为 U 的城市。那么在这种情况下,他可以从编号为 V 的城市坐大巴回到编号为 U 的城市。但是,上述乘坐大巴的行为,他最多只会进行一次

请编程计算出,小 A 最多能访问到多少个不同的城市

输入

第一行读入两个整数 NM,分别代表城市的数量和单向航班的数量。

接下来 M 行,每行包含两个整数 U_iV_i,表示存在一条从城市 U_i 到城市 V_i 的单向航线,且不会有重复的航线出现。

输出

输出一个整数,表示利用一次乘坐大巴的机会,小 A 最多可以访问多少个不同的城市。

样例

输入

7 10 
1 2 
3 1 
2 5 
2 4 
3 7 
3 5 
3 6 
6 5 
7 2 
4 7

输出

6

输入

20 48
8 16
7 4
6 19
14 9
17 13
17 3
14 18
20 17
20 10
5 9
5 18
5 4
7 1
7 19
17 8
6 13
8 3
11 14
12 15
17 16
6 7
17 10
1 3
1 13
6 2
10 13
2 7
19 1
14 12
6 20
2 9
1 8
2 1
18 15
5 11
18 12
1 17
20 8
1 10
6 16
6 1
14 15
1 20
1 16
11 5
2 19
1 5
20 3

输出

9
说明

样例 1 解释

A 可以沿着如下的路线旅行:1,2,4,7,2,5,3,1,共能访问 7 个不同的城市。

其中 5->3 的路线,小 A 乘坐了一次大巴。

数据范围

对于 10\% 的数据,满足 1 \le N \le 1001 \le M \le 300

对于 100\% 的数据,满足 1 \le N,M \le 10^51 \le U_i,V_i \le N

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 基础


上一题 下一题