Forest to Tree Transformation with Square Out‐Degree

You are given a forest of n vertices with m directed edges. The forest is given in the following format: the vertices are labeled 1 through n, and each directed edge is given as a pair of integers u v, meaning there is an edge from u to v. Note that the given graph is a forest (i.e. an acyclic graph which may be disconnected) when the edges are seen as undirected.

You are allowed to perform the following two operations arbitrarily many times:

• Add a new vertex.
• Add a new directed edge between any two vertices (both existing and newly added ones are allowed).

Your task is to add some edges (and possibly new vertices) so that the final graph, when all directed edges are considered undirected, becomes a tree, and moreover, the out‐degree of every vertex is a perfect square. (A number is a perfect square if it can be written in the form \(k^2\) for some integer \(k \ge 0\); note that \(0 = 0^2\) counts.)

Additional requirement: Among all valid solutions, you should choose one that minimizes the number of newly added vertices.

Construction idea (hint):

Suppose the input forest has n vertices and m directed edges. Since the input forest is acyclic, it is composed of several trees. You can add extra edges between these trees so that the n original vertices become connected and form a tree (which will have exactly \(n-1\) edges among them). However, some vertices may already have a nonzero out‐degree from the given edges. To achieve the required condition, for each vertex you can attach some new leaves (by adding new vertices and an edge from the vertex to the new vertex) so that its final out‐degree becomes \(d^2\) for some integer \(d\). More precisely, for each vertex let its current out–degree be \(x\) (after adding the connectivity edges among original vertices), then you attach extra \(r\) leaves so that \[ x + r = \lceil \sqrt{x} \rceil^2. \] The newly attached vertices (leaves) have out–degree 0, which is valid since \(0 = 0^2\).

The final graph consists of the original vertices (connected by the initial edges and the ones you add for connectivity) along with all the new vertices added as leaves. This graph is a tree because it has exactly (number of vertices in final graph) - 1 edges and is connected.

Input and Output Formats

The input starts with a line containing two integers n and m. Then there are m lines, each containing two integers u v indicating a directed edge from u to v.

The output should describe your solution plan as follows:

1. On the first line, print two integers: N and K, where N is the total number of vertices in the final tree (the original vertices plus all newly added vertices) and K is the total number of new edges you added.
2. Then, print K lines, each containing two integers u v denoting a new directed edge from vertex u to vertex v.

Note: The added edges include both the edges used to connect the different trees among the original vertices and the "leaf attaching" edges used to adjust the out–degree to a perfect square. It is guaranteed that a solution always exists.

---

Mathematical Formulation:

Let the original forest have vertices \(1, 2, \dots, n\) and let the initial out–degree of vertex \(i\) be \(d_i\). After adding connectivity edges and leaf edges, suppose the final out–degree of vertex \(i\) is \(D_i\). We require that for all vertices, \(D_i = k_i^2\) for some integer \(k_i \ge 0\), and that the overall undirected structure is a tree.

Your solution must satisfy these constraints while minimizing the number of newly added vertices.

inputFormat

The first line contains two integers n and m (\(1 \le n \le 10^5\), \(0 \le m < n\)), representing the number of vertices and the number of directed edges in the given forest, respectively.

Then follow m lines, each containing two integers u v (\(1 \le u,v \le n\), u != v), meaning there is a directed edge from u to v.

outputFormat

On the first line, output two integers N and K, where N is the total number of vertices in the final tree (original + new) and K is the total number of new directed edges you added.

Then output K lines, each with two integers u v, representing a newly added directed edge from vertex u to vertex v.

The output must describe a valid solution such that when the initial directed edges and your added edges are considered together (forgetting direction), the graph forms a tree, and the out–degree of every vertex is a perfect square.

sample

3 0

5 4
1 2
1 3
1 4
1 5

</p>