GitHub 源文件 Markdown 中文

Timber

• Indicative time limit: 0.5 s (reference environment: environment and measurements; for estimation only)
• Actual time limit: twice the reference program's benchmark time on its slowest official test file in the target environment, rounded up to a multiple of 0.5 seconds, then to the platform's supported granularity if coarser.
• Memory limit: 128 MB

Story

Steve has installed a tree-cutting mod. Selecting a branch cuts every node on its path to the root, and each selected node costs one fee. For each budget, maximize the number of cut nodes; among equally productive choices, disturb as few trees as possible.

Formal Problem Statement

You are given an undirected forest with \(n\) nodes and \(m\) edges. Nodes are numbered \(1\) through \(n\) . Each connected component is a tree rooted at its smallest-numbered node.

After selecting distinct nodes, every node on the path from a selected node to its tree root, including both endpoints, is cut. A node appearing on multiple paths counts only once.

Let \(Need\) be the minimum number of selections required to cut the whole forest. For each \(k=1,\ldots,Need\) , among choices of exactly \(k\) nodes, find:

1. The maximum number of nodes that can be cut.
2. Among choices attaining that maximum, the minimum number of trees containing a selected node.

Input Format

The first line contains \(n,m\) . Each of the next \(m\) lines contains the endpoints \(u,v\) of an undirected edge.

Output Format

Print \(Need\) on the first line. On each of the next \(Need\) lines, print the two optimal values for the corresponding \(k\) , separated by a space.

Example 1

Input

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

Output

3
5 1
9 2
11 2

Example 2

Input

6 4
1 2
2 3
1 4
5 6

Output

3
3 1
5 2
6 2

Example 3

Input

1 0

Output

1
1 1

Example Explanation

In example 1, select nodes \(5,11,7\) in that order. The new contributions are \(5,4,2\) , giving totals \(5,9,11\) across \(1,2,2\) trees.

Double circles mark selected nodes. Labels 1, 2, and 3 beside edges indicate the first selection that covers that path segment. The isolated node in example 3 is itself a tree.

Constraints and Guarantees

All inputs satisfy \(1\le n\le500000\) , \(0\le m\le n-1\) , and \(1\le u,v\le n\) . The input is a forest and may contain isolated nodes.

Score share	Additional conditions
100%	No additional conditions