Codeforces 1833E Round Dance
看到 shortest paths 来做的，但是好像没啥关系也没啥难度。
首先能知道一个连通块肯定一次就能跳完，所以可以把连通块缩出来。
然后有一个性质，记 \(cz_i\) 为 \(i\) 连通块内点种通过已知边推出的度数为 \(1\) 的个数为 \(cz_i\)，则 \(cz_i\bmod 2 = 0\)。
记点 \(i\) 通过已知边推出的度数为 \(d_i\)，大致证一下，分三种情况：
- \(d_u = 0, d_v = 0\)，个数 \(+2\)。
- \(d_u = 1, d_v = 1\)，个数 \(-2\)。
- \(d_u = 0, d_v = 1\)，个数不变。
对于 \(cz_i\) 对答案的贡献，分两种情况考虑：
- \(cz_i = 0\)，则这部分肯定会产生 \(1\) 的贡献。
- \(cz_i > 0\)，则很显然可以通过让两个度数为 \(1\) 的点相连是 \(cz_i\) 变为 \(\le cz_i\) 的任何偶数。
则当 \(cz_i = 0\) 时，每个连通块都会产生 \(1\) 的贡献，即最大值；
当 \(cz_i = 2\) 时，可以对于每一个 \(cz_i = 2\) 的连通块相连成一个环，所有连通块只会产生 \(1\) 的贡献，即最小值。