Problem Description

You are given a forest, and each edge has a direction.

You can perform two types of operations:

• Add a new node.

• Add a directed edge between two nodes.

You need to make it so that in the end, if you treat all directed edges as undirected edges, the graph becomes a tree, and the out-degree of every node is a perfect square.

Provide a plan that uses the minimum number of added nodes.

Input Format

The first line contains two integers $n,m$ ($1\le m \lt n \le 10^5$), representing the number of nodes and edges in the forest.

The next $m$ lines each contain two integers $u,v$ ($1\le u,v\le n$), indicating a directed edge from $u$ to $v$.

It is guaranteed that if you treat each edge as an undirected edge, the graph is a forest.

Output Format

The first line contains two integers $x,y$, representing the number of nodes you add and the number of edges you add.

The next $y$ lines each contain two integers $u,v$, indicating that you add a directed edge from $u$ to $v$. You must ensure that $1\le u,v\le n+x$.

3 2
1 2
1 3

2 2
1 4
1 5

Hint

Translated by ChatGPT 5