We Live Forgetting the Truth

Time limit1sMemory limit1024 MB

Summary

Given a fixed n-vertex graph, find min and max pairs revealed in a random pair order before an online decision rule can prove it connected or not.

Level: Hard8 of 10
Topics: Graph, Combinatorics, Greedy, Brute force
Solved: No attempts yet

Problem

We put an undirected simple graph $G$ into a program called WE11 no. N. Each vertex of $G$ is labeled with a number from $1, 2, \ldots, N$ . The program tells us, for each pair of vertices, whether an edge exists between them. Specifically,

It randomly shuffles the list of all natural-number pairs $(a, b)$ with $1 \le a < b \le N$ .
In list order, for each $(a, b)$ it tells us at a fixed time interval whether there is an edge connecting $a$ and $b$ . The user may terminate the program at any moment.

Unfortunately, since we live forgetting the truth, we no longer know at all what $G$ looks like. In that state we run WE11 no. N to find out whether $G$ is connected, that is, whether a path exists between any two vertices. We will terminate the program the moment the information gathered by this program alone lets us know whether $G$ is connected.

What are the minimum and maximum numbers of pieces of information we will have gathered by the time we terminate the program? Help poor Woori Kim.

Input

The first line gives the number of vertices $N$ and the number of edges $M$ of $G$ . ( $2 \le N \le 500$ , $0 \le M \le N(N-1)/2$ ) The next $M$ lines give, one per line, the labels of the two vertices that an edge connects.

Output

On the first line, output the minimum number of pieces of information we will gather. On the second line, output the maximum.

Examples2

Example 1
Input
```
3 3
1 2
2 3
3 1
```
Expected output
```
2
2
```
Example 2
Input
```
3 1
1 2
```
Expected output
```
2
3
```