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

Description

One day Mr. K gives you a recipe:

```
Section I   Ingredients
   - A weighted connected undirected graph G with n vertices and m edges
   - Another graph T using same vertices with G but having no edge

Section II  Procedure
   1. Pick an edge e with smallest weight among unprocessed edges in graph G.
      (If there are more than one such edges, pick any.)
   2. If edge e forms an cycle along with the edges in graph T, throw edge e away.
      Otherwise, add edge e into graph T.
   3. Repeat step 1 and 2 until all edges in graph G are processed.
   4. Finally, you construct a cool graph T!
```

You are so curious what this recipe is about.  Luckily, you always bring a weighted connected undirected graph with you so you can start following the recipe right away.  Please follow the instruction in the recipe to construct a cool graph (the T mentioned in the recipe) and output its total edge weight.

Input

The first line contains two integers n and m, being the number of vertex and the number of edges in your weighted undirected graph.

The following m lines describes the edges.  Each line contains three integers u, v, w, denoting an undirected edge uv with weight w.

**Constraints**

- 1 <= n <= 2 * 10⁵
- 1 <= m <= 10⁶
- 1 <= w <= 10⁹ for each edge

Output

Please print the answer in one line.

Sample Input  Download

Sample Output  Download

Tags

Discuss