UOJ Logo

NOI.AC

#94. travel

统计

城际旅行

时间限制:1秒,内存限制:128MB 读入文件名:travel.in 输出文件名:travel.out

【题目描述】

为了放松身心,城际旅行果然还是一个糟糕的选择Orz,不过为了考察各地的风土人情,你还是决定开始这场旅行!

在此次旅行中,你已经准备好了$n$个想要去看看的城市了,它们编号从$1$到$n$,它们之间有$m$条单向铁路相连,并且并没有环,虽然城市之间都可以坐飞机来往,但是为了节省开销,你决定只坐火车。

为了尽量多实地考察,你需要制定一个火车旅行路线,以访问最多的城市。

那么最多可以在一次旅行中访问多少城市呢?

【输入格式】

输入共$m+1$行。

第一行包含两个正整数$n$、$m$,分别表示城市和铁路的数目,输入用一个空格分隔。

接下来共有$m$行,每行输入两个正整数,表示该条铁路的起点城市编号和终点城市编号。

输入保证图中没有重边和环。

【输出格式】

输出共一行,包含一个正整数,表示最多能够访问多少城市。

【输入输出样例1】

travel.in

3 3

1 2

1 3

2 3

travel.out

3

【输入输出样例2】

travel.in

4 5

1 2

1 3

1 4

2 4

4 3

travel.out

4

【数据规模与约定】

对于前20%的数据,$1≤n≤10$;

对于前50%的数据,$1≤n≤100$;

对于100%的数据,$1≤n≤1000$,$1≤m≤n*(n-1)/2$;