集训拉的题单，随自己听课进度和思考进度更新（
T1
\(2n\) 个点的完全图，要把这些边分成 \(2n-1\) 组，每组 \(n\) 条边，且每条都是一个匹配（任意两条边没有公共点），\(n \leq 1000\)。
motivation: 从要求答案的构造特点入手，寻找直观情况
solution:
My Solution
题目要求的是匹配，匹配最常见的是二分图匹配，那么构造就先考虑变成二分图，左边 $n$ 个点，右边 $n$ 个点。这左右两边部分点之间的连边中，每个点都会连出去 \(n\) 条，那么可以简单的构造出 \(n\) 组。
接下来，就只用考虑左边内部和右边内部的连边如何构造出 \(n-1\) 组。
这个时候就需要对 \(n\) 进行奇偶讨论，因为左边每次选 \(2\) 个不重复的，如果是奇数，就会单出一个点来。
考虑简单的偶数情况，那么左边点和右边点都可以选出 \(\dfrac{n}{2}\) 条边，合在一起就是 \(n\) 条边的一个集合了，那就简单了。
左边的每个点都会向左边的其他点连出去 \(n-1\) 条边，于是一定也可以构造出 \(n-1\) 条边，如何构造，可以每次直接从第一个点进行 \(dfs\)，然后每次加入一条边，加入的边如果选中了两个没有被选中过的点，然后就把他存下来，并且标记用过这条边了。
然后选中 \(n\) 个点了之后就可以推出，把选了的边加入答案，同时，将他们从图中删除，所以存边用 \(set\) 存。
这样的话，复杂度是 \(O(m\log n)\) 的，没啥问题，右边同理，于是 \(n\) 为偶数的情况解决。
现在转过来考虑 \(n\) 为奇数的情况，那么左右边都只能选出 \(\lfloor \dfrac{n}{2} \rfloor\) 条，这样还差一条边，但是左右都剩了一个点，我们考虑用这两个点补全一下，可能很舒服，嗯？
那么在左边和右边的匹配中，每个点都留一条边到对面的点，这样中间就只会构造出 \(n-1\) 个匹配，接下来就要用左边和右边的 点构造出 \(n\) 个匹配。
每次先让左边保留一个点，让他和右边的进行匹配，那么对于剩下的 \(n-1\) 个点，这时候是偶数，随便选一个内部的匹配出来，这样完成了一组构造。
那么总共有 \(n\) 个点可以保留，做 \(n\) 次就可以获得合法的 \(n\) 个组合。
然后这题就做完了，复杂度实现应该是 \(m \log n\) 的。
Offcial Solution
先把点按 \(0 \sim 2n - 1\) 标号，考虑如下构造，对于一组边 \((x,y)\) 满足 \(0 \leq x < y < 2n - 1\)，我们把它们扔到 \((x + y) \bmod (2n - 1)\) 这一组，注意到 \(2n - 1\) 是个奇数，因此对于每个 \(i\) 存在唯一的 \(k\) 使得 \(2k = i (\bmod 2n - 1)\)。
把 \(k\) 和 \(2n - 1\) 的连边扔到 \(i\) 这一组就好了。
不难发现这样的构造所有边都被使用了至少一次，因此是个合法的构造。