N. Portal Investigation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Misaka has recently discovered the existence of one-way magical portals that allow quick travel between cities in Japan. She wants to investigate these portals, but she is too busy fighting the Russian military, the Russian Orthodox Church, and the Roman Catholic Church. Thankfully, she can command a network of clones of herself who can investigate the portals in her stead.

In order to properly analyze a portal, one of her clones must travel through the portal twice. Because portals only go in one direction, some portals may be impossible to properly investigate. Additionally, her clones cannot travel to a city that a separate clone has already visited or is visiting in order to avoid the possibility that the network of clones is discovered by the general populace. Misaka is planning to charter a number of military helicopters to travel across Japan and airdrop her clones into Japanese cities to investigate the portals. Once again, two clones cannot be airdropped into the same city to prevent anyone from discovering the clone network. Because chartering military helicopters is expensive, Misaka wants to know the maximum number of portals that can be investigated and the minimum number of clones necessary to do so.
Input

The first line contains $$$n$$$ ($$$2\leq n \leq 5\times 10^4$$$), the number of cities, and $$$m$$$ ($$$1\leq m \leq 5\times 10^4$$$), the number of portals. The next $$$m$$$ lines contain two numbers, $$$a$$$ and $$$b$$$ ($$$1\leq a,b \leq n$$$), representing a one-way portal from city $$$a$$$ to city $$$b$$$. Note that there can be multiple portals between two cities, but a portal must be between two different cities ($$$a \neq b$$$).

Output

On the first line, print out the maximum number of portals that can be investigated. On the second line, print out the minimum number of clones required to investigate the maximum number of portals that can be investigated.

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