LASTSHOT - THE LAST SHOT


Tony Stark is on the mission to save the world from Loki's army so he spread N bombs in the enemy region. He spread the bombs in such a way that a bomb can be in range of another bomb i.e. say bomb B1 is in range of bomb B2 , when bomb B2 explodes it will trigger bomb B1 and it also get explode but vice-versa might not be true because the bombs are of different of range. As he is running out of energy so he left with one shot to trigger the bomb .Now he ask Jarvis to find most appropriate bomb which he can trigger to make maximum impact.

Impact is basically number of bombs get explode.

Can you help Jarvis to do so?

Input

First line contains two integer N and M denoting number of bombs and number of relation between the bombs.

1 ≤ n ≤ 10000

1 ≤ m ≤ 10000

Next M lines contain two integer A and B denoting bomb B is in range of bomb A.

1 ≤ A ≤ N

1 ≤ B ≤ N

Output

A single line containing MAXIMUM IMPACT.

Example 1

Input:
4 3
1 2
2 4
1 3

Output:
4

Example 2

Input:
4 3
1 2
2 1
2 3

Output:
3

hide comments
pandey101299: 2019-12-01 18:19:02

if 1 is in the range of 2 but it is not necessary 2 is in the range of 1 means directed .so every element of visited array to false after each dfs traversal .

ankur314: 2019-05-13 04:59:42

Anyone used DP for this? Please tell your approach.

aaaaeeee: 2018-06-18 09:21:01

od Cajkanovica panadalje!

stralz: 2018-06-18 09:20:04

uuuuvek biiiiiiio hroooomi vuuuuk

codefield: 2018-01-22 09:24:58

AC in 1st go :)

nadstratosfer: 2018-01-20 10:46:28

Out of todo list after 3 months, thanks Dương Bảo. Didn't bother with defensive input here before as I was getting TLE and RE on the same code. Ignoring blank lines is not enough, you have to read integer by integer as there seem to be newlines between n and m or a and b.

Dương Bảo: 2018-01-20 09:30:20

Have to write a generator to read ints separately in python3 to get rid of NZECs. I think the input data may contain excess spaces or blank lines.

noobsaibot: 2018-01-18 07:33:16

Can anyone help me understand why BFS would fail even though resetting visited array. dfs passes

codeking123: 2018-01-02 00:05:48

sill mistake easy one dfs

entcat: 2017-10-05 16:29:13

Use idea of Scc's to solve it in O(N).


Added by:Shivam
Date:2017-02-14
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All