这是官方题解的 AI 中文翻译。

我们将需要连通的图称为第一张图，将连通性不能被破坏的图称为第二张图。

假设在第二张图中存在一条边 $(v, u)$，且顶点 $v$ 与 $u$ 在第一张图中属于同一个连通块。那么，考虑第一张图中另一个不同连通块内的任意顶点 $a$。此时，可以注意到，操作 $(v, a)$ 或 $(u, a)$ 中至少有一个不会破坏第二张图的连通性。因此，可以通过一次操作将顶点 $a$ 所在连通块与 $v$、$u$ 所在连通块合并，从而解决问题。

接下来注意到，如果存在一对顶点 $v$ 和 $u$，使得这两个顶点在两张图中都没有边 $(v, u)$，那么可以直接对这对顶点执行一次操作，之后问题就转化成了前面的情形。

如果找不到这样的边，则第一张图的所有连通块都是完全图，并且第二张图包含了所有第一张图中没有的边。

现在，任选第一张图中一个大小至少为 $2$ 的连通块（如果不存在这样的连通块，可以任意选择一对顶点执行一次操作，此后必然会出现这样的连通块）。在该连通块中任选两个顶点 $a$ 和 $b$。再从第一张图的所有其他连通块中各选出一个顶点，记为 $v_1,\ v_2,\ \ldots,\ v_k$。

注意，如果第一张图中连通块数量至少为 $3$，或每个连通块的大小都至少为 $2$，那么可以依次执行如下操作序列：$(a, v_1),\ (b, v_2),\ (b, v_3),\ \ldots,\ (b, v_k)$。

如果不是上述情况，则第一张图中存在一个孤立顶点 $c$，其余所有顶点构成一个完全图。此时，第二张图是一棵星型结构。如果 $n = 3$，则无解；否则，任选两个与 $c$ 不同的顶点 $a$ 和 $b$，依次执行 $(a, b)$ 和 $(a, c)$ 两次操作即可。

综上，可以在 $\mathcal{O}(n + m_1 + m_2)$ 或 $\mathcal{O}\left((n + m_1 + m_2) \log(m_1 + m_2)\right)$ 的时间内解决本题，具体取决于实现方式。