CF1559D2 Mocha and Diana (Hard Version)

给你两棵森林，节点数均为 $n$。 允许你进行加边操作，但是有两个要求： - 如果在第一个森林加一条 $(u,v)$ 的边，第二个森林也要进行同样的操作。反之同理。 - 加边后两个森林依旧是森林。（一棵树也是森林） 求最多能加几条边，并输出加边方案。

第一行三个整数 $n,m_1,m_2$（ $1 \le n \le 10^5,0 \le m_1,m_2 < n$ ），分别表示结点数，第一个森林的边数，第二个森林的边数。 接下来 $m_1$ 行，每行两个整数 $u,v$ ( $1 \le u,v \le n, u \ne v$ )，用来描述第一个森林。 接下来 $m_2$ 行，每行两个整数 $u,v$ ( $1 \le u,v \le n, u \ne v$ )，用来描述第二个森林。

第一行一个整数表示最多加边数。 接下来每行两个整数 $u,v$ 表示所加的边。

In the first example, we cannot add any edge. In the second example, the initial forests are as follows.  We can add an edge $ (2, 4) $ .