Express Paths in Directed Graphs

Two vertices x and y in a directed graph G are equivalent if there is a directed path from x to y and also there is a directed path from y to x in G. Each vertex is equivalent to itself.
The equivalence relation between vertices divides the vertex set of G into disjoint equivalence classes: Two nodes belong to the same equivalence class iff they are equivalent.
Each equivalence class C is assigned a cost, which is equal to the number of vertices in C.
Each vertex x in G is assigned a cost, which is equal to the cost of the equivalence class containing x.

A path in G is an unempty sequence of vertices (v1, v2, ..., vk), k > 0, such that (vj, vj+1) is an edge in G for j = 1, 2, ..., k−1. The path length is k−1.
The cost of a path is the sum of costs of all its vertices.
Path P in G is an express path if all three conditions hold:
    1. The length of P is at least 1.
    2. No two vertices in P are elements of the same equivalence class.
    3. The costs c1, c2, ..., ck of vertices v1, v2, ..., vk in P form a non-decreasing sequence.



Figure 1. An example of a directed graph. The cost of each vertex is written at the vertex in the yellow box. The equivalence classes are highlighted in pink. Four express paths which cost is 9 are marked by dotted lines. There is no express path which cost is higher than 9. The length of the express path (3, 4, 6, 8) is 3, the length of any other express path in the graph is either 2 or 1. The image illustrates Example 3 below.

The task

You are given a directed graph. Determine the length of an express path which cost is maximum possible. When there are more paths which cost is maximum possible determine the length of the longest one(s).

Input

The first input line contains two integers N, M separated by space. N is the number of vertices, M is the number of edges in the graph. Next, there are M lines, each contains two integers A, B separated by space and representing an edge from A to B. The edges are listed in random order.
It holds 4 ≤ N ≤ 105, N ≤ M ≤ 106.

Output

The output contains one line with two integers C and L separated by space, where C is the maximum possible cost of an express path, L is the maximum possible length of an express path with cost C.
It is guaranteed that there always exists at least one express path in the given data.

Example 1

Input
10 12
0 1
5 6
7 6
7 8
9 7
3 0
1 3
2 5
6 2
8 4
4 9
1 7
Output
7 1

Example 2

Input
10 13
0 1
1 2
2 3
3 4
5 6
6 7
7 8
8 9
0 5
6 1
2 7
8 3
4 9
Output
10 9

Example 3

Input
17 29
2 0
0 1
1 2
5 6
6 7
7 5
12 13
13 12
9 8
9 10
10 11
11 9
8 11
14 15
15 16
16 14
2 3
3 4
4 6
1 12
12 7
12 14
13 16
7 14
6 8
7 8
7 9
15 10
16 11
Output
9 3
The data of Example 3 is depicted in Figure 1.

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 public data set