题意简述
一张无向图有 $n$ 个点，还没有边。给出 $n - 1$ 个大小至少为 $2$ 的点集 $E_i$ ，问是否能从每个点集中选出两个点连边，使得图连边后为一棵树。若能，输出一种方案；若否，输出 -1 。$2\le n\le 10^5, \sum|E_i|\le 2\times 10^5$ 。
主要思路
任意钦定一个点为这棵树的根，之后每条边都可看作某个点连向其父亲的边。建立一个二分图去匹配每个点和其连向父亲的边。二分图的左边为除了根以外的点，右边为 $n - 1$ 个点集。若 $u$ 不是根节点且 $u\in E_i$ ，连边 $(u, E_i)$ 。
可以看出，有解的必要条件就是这个二分图存在一组完美匹配。而另一个必要条件即二分图（左边加入根节点并用上面的方式连边后）应当联通。
任取一组该二分图的完美匹配，之后考虑从根出发 bfs。一开始，我们将根所在的所有点集的匹配点的父亲均设为根，然后再从这些点递归进行下去。如果最后有的点没被访问，说明二分图不连通，与假设矛盾。于是我们构造出了一组合法解，也说明上面的必要条件便是充要条件。
用 Dinic 等算法求二分图完美匹配，时间复杂度 $O(\sum |E_i|\sqrt{n})$ 。
参考代码
咕咕咕