Description

Given an undirected graph with n vertices. The graph doesn't have any edge initially.

Then you will be given m undirected edges. Add the edges to the graph sequentially.

After each addition of edge, calculate the number of connected components in the graph and the size of the largest connected component.

It is guaranteed that the graph remains simple (no multiple edge, no self-loop) after each addition of edge.

Note that:
- A *connected component* of an undirected graph is a *connected* subgraph that is not part of any larger *connected* subgraph.
- An isolated vertex which can not reached by any other vertices should be considered as one *connected component*.

Input

The first line of the input contains two integers n and m — the number of vertices and the number of edges. The vertices are denoted by 1, 2, ..., n.

Then m lines follow, each line contains two integers u and v, being an edge to add.

**Constraints**

- 2 <= n <= 10⁵
- 1 <= m <= min(n(n - 1) / 2, 2 * 10⁵)
- 1 <= u, v <= n ; u != v

Output

For each addition of edge, output one line: the number of connected components in the graph and the size of the largest connected component.

Sample Input  Download

Sample Output  Download

Tags

Discuss