Swimming Pools Delivery Company Quandaries

Swimming Pools Delivery Company plans to build its depot at one of the street crossings in the town. All swimming pools the company sells will be stored in the depot. There, each pool will be loaded on a truck and delivered to the customer. A company truck can carry only one pool and it typically returns empty from the customer. The transport of the pools on a sizeable truck through narrow and steep streets is often tricky. Some streets have to be treated as strictly one-way streets.
To simplify their analysis of the transport conditions, the company analysts have finally decided to think only in the terms of one-way streets and to consider any two-way street as a pair of two separate one-way streets in opposite directions.
Current company analysis of transport conditions in the city is presented below. It introduces a few more specific terms. It is hoped that these terms will help company to describe and to solve transport problems in an effective way.

A street, for a company analyst, is any stretch of road which begins at one crossing, ends at another crossing (the order of crossings defines the direction of the street) and which does not pas through any other crossing.
The existence of many one-way streets has another limiting effect, due to which some streets are identified as so-called weak streets.
When a truck enters a weak street, it cannot drive back to the depot, following only the accepted directions of the streets. To return to the depot, the truck would need to pass through at least one street in the direction oposite to its accepted direction and such drive is not deemed safe.
A crossing is a weak crossing if at least one weak street begins at that crossing. All other crossings in the city are called strong crossings.
A connection from crossing A to crossing B is a sequence of consecutive streets a truck passes on its journey from crossing A to crossing B.
The length of a connection is the number of streets the truck passes on its way from the start of the connection to its end.
A strong connection from one strong crossing to another is a connection which passes only through strong crossings and which passes through minimum possible number of streets. Strong connections are preferred by the company. They are reasonably short and eliminate the risk of entering a weak road by an accidental wrong turn at some crossing.
Consider any strong crossing X. Another strong crossing Y is called a target for X if there exists a strong connection from X to Y and also a strong connection from Y to X.
The term variability of a strong crossing X denotes the number of targets of X.
Let crossing Y be a target for X. The cost of Y is a number which is equal to twice the length of the strong connection from X to Y plus the length of the strong connection from Y to X. The cost reflects the situation when a loaded truck drives from X to Y, unloads at Y and returns empty to X. In particular, a journey with a pool to a customer is more demanding than the journey back with an empty truck.
The cost of a strong crossing X is equal to the sum of the costs of all targets for X.
When there is no target for a particular strong crossing X then both the variability and the cost of X are zeros.
A prospective crossing is a strong crossing which variability is maximum and its cost is minimum among all strong crossings with maximum variability.

The company wants to choose one of the prospective crossings in the city to build its depot there.

Figure 1. A scheme of streets. Crossings are represented as nodes, streets as directed edges. There are 17 crossings and 27 streets. There are two prospective crossings, namely 4 and 11. Their variability is 3 and their cost is 13. The variability of crossings 3, 5, 6, 12, 14, 15 is also 3, however, their costs are higher than 13. Namely, the costs are 18, 18, 14, 18, 14, 18 (in the same order). Apart from crossings mentioned so far, there are three other strong crossings 8, 9 and 16, in the scheme. The variability of crossings 8 and 9 is only 1 (and cost is 3 in both cases). The variability and the cost of crossing 16 are both 0. The scheme illustrates Example 1 below.

The task

You are given the list of all streets in the town. Calculate the total number of prospective crossings and the variability and the cost of each of them.

Input

The first input line contains two positive integers N, M, where N is the number of crossings, M is the number of streets. The crossings are labeled by integers 0, 1, ..., N−1. The list of all streets 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 crossing and the second integer denotes the label of the end crossing of the street. The order of the streets in the list is arbitrary.
The value of N does not exceed 3×10³, the value of M does not exceed 10⁶.

Output

The output contains one text line with three integers separated by space and representing the number of prospective crossings in the town and the variability and the cost of each of them.

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

2 3 13

8 12
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 0
1 3
3 5
5 7
7 1

4 7 48

9 11
0 2
1 2
2 3
3 4
4 2
4 5
4 6
5 7
5 6
6 7
7 8

3 0 0

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