CF1186 F. Vus the Cossack and a Graph

题目传送门：https://codeforces.com/problemset/problem/1186/F

题目大意：
给一个\(n\)点\(m\)条边的无向简单图\(G\)，记\(d_i\)为点\(i\)的度数。你需要在其中找到一个子图\(Z\)，满足\(Z\)的边数\(m_Z\leqslant \lceil\frac{n+m}{2}\rceil\)，记\(f_i\)为\(Z\)中点\(i\)的度数，满足\(\forall i\in G,\lceil\frac{d_i}{2}\rceil\leqslant f_i\)

求子图\(Z\)

解法一（暴力+人品）：将所有边存下来后随机打乱，然后判断端点度数是否满足\(\lfloor\frac{d_i}{2}\rfloor\leqslant f_i\)，进行加边与否的操作即可

解法二（正解）：

• 所有点的度数都是偶数，说明该图存在欧拉回路，我们求出欧拉回路，然后间隔保留\(\frac{m}{2}\)条边，这样即可保证所有点的度数恰好为\(f_i=\frac{d_i}{2}\)

• 存在部分点的度数为奇数，我们可以新建0号节点，向所有度数为奇数的点连边（虚边）。显然，这些点的数量为偶数，故新图所有点的度数都为偶数

  给新图求欧拉回路后，虚边会将回路分割成若干部分。若该段边数为偶数，则按上一种情况处理；如果该段边数为奇数，则保留两端的边，中间再间隔保留。因为两端的点的度数为奇数，需要多保留一位

/*program from Wolfycz*/
#include