P10163 [DTCPC 2024] Square-Degree Tree.

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.

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.

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$.

Translated by ChatGPT 5