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
jaideeppyne: 2017-09-24 05:19:45

O(n^2) algo is getting passed strangely ! Did DFS from every vertex in the di-graph which should ideally not pass , but AC. Dont forget to reset every element of visited array to false after each DFS traversal.
HAPPY CODING ! :)

imperfectboy: 2017-09-10 07:02:24

easy one !! silly mistake costed WA !!

hodobox: 2017-07-12 05:20:50

Yeah, assert(n<=100) passed...

ag7775: 2017-07-10 12:48:23

Someone please help me to understand examples?

pvsmpraveen: 2017-04-06 11:52:38

I got AC using Normal BFS...
I wonder if DP on such graph is possible, i tried but din't get that work, anyone did with DP?

Last edit: 2017-04-06 11:52:57
vengatesh15: 2017-03-24 09:35:36

easy one silly mistake cost me 1 WA..

saikat777: 2017-03-22 18:27:19

AC on first go.That was unexpected. :p
Size of biggest island is what it effectively boils down to.

abhi_upadhyay: 2017-03-07 19:23:14

Tired of getting consistently WA.....
Finally AC

Last edit: 2017-04-02 22:08:30
mehmetin: 2017-03-04 07:23:53

N is actually less than 100, which makes the problem too easy, for tutorial. N=10000 as stated would make the problem tough.

sultania23: 2017-02-27 20:42:25

beware of silly mistakes. easy one!!!!!!!


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