Connection-Safe Minibus Trips

The Lake District Travel Agency operates in the Lake District which is famous for its natural wonders and strict environmental rules limiting access to the area.
Any motorized access to places in Lake District is possible only by licensed minibusses. There is a number of minibus stops. Typically, a stop is built in a vicinity of some natural point of interest. The roads are extremely narrow, thus each route is only one-directional. The transport is organized by so-called minibus connections.
A minibus connection always connects just two different minibus stops - the start stop and the end stop of that connection.

Due to the weather and wildlife conditions, varying in time, the minibus traffic on the connections in the area might be a bit erratic sometimes. Thus, an additional property of minibus stops is defined.
A minibus connection C from stop a to stop b is considered to be an unsafe connection if and only if a traveller who leaves a via C cannot return to a by any sequence of minibus connections.
All minibus stops in which no unsafe connection starts or ends are considered to be connection-safe stops.
No other minibus stops are considered to be connection-safe.

A minibus trip is a sequence of minibus connections in which the start stop of a minibus connection is also the end stop of the previous minibus connection in the sequence. Any minibus stop and any minibus connection may appear more times in a minibus trip, the number of times a particular minibus stop or a particular minibus connection appears in a minibus trip is not limited.

The agency plans to offer minibus trips that visit the maximum possible number of connection-safe stops. Each visited connection-safe stop is counted only once in a trip, regardless of the number of visits to the stop.

Figure 1. A scheme of minibus stops and connections. There are 17 stops and 24 connections. The connection-safe stops are highlighted in blue. There is a minibus trip that visits connection-safe stops 3, 4, 9, 10, 11, 8, 16. There is no minibus trip which visits more than 7 connection-safe stops. The scheme illustrates Example 1 below.

The task

You are given the list of all minibus connections in the Lake District. Calculate the maximum number of connection-safe stops that can be visited in one minibus trip.

Input

The first input line contains two positive integers N, M, where N is the number of minibus stops, M is the number of minibus connections. The minibus stops are labeled by integers 0, 1, ..., N−1. The list of all minibus connections is on the next M lines. Each of those lines contains two integers separated by space, the first integer denotes the label of the start stop of a minibus connection and the second integer denotes the label of the end stop of the same minibus connection. The order of the minibus connections in the list is arbitrary.
The value of N does not exceed 10⁶, the value of M does not exceed 2×10⁶.

Output

The output contains one text line with one integer representing the maximum number of connection-safe stops in a minibus trip.

17 24
0 1
1 2
2 1
0 5
5 1
1 6
3 0
3 4
4 5
6 7
7 8
12 3
5 12
15 7
8 16
9 11
10 11
14 9
14 10
11 14
12 13
13 14
14 15
16 15

7

5 8
0 1
1 2
2 3
3 2
4 0
4 2
4 3
1 4

1

12 16
0 1
1 2
1 3
3 2
1 6
6 7
7 1
2 8
8 9
9 2
3 10
10 11
11 3
0 4
4 5
6 0

6

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to the public data set