Problem 1
依据题意（定义 从 0 开始）：
且
Problem 2
(a)
由题意，得到
(b)
由题意，得到
Problem 3
(a)
(b)
""
假设 是二分图，其顶点集可以划分为两个互不相交的集合 和 ，且同集合内的顶点之间没有边。则考虑图中的任意一个环
由于是二分图，环上的顶点必须在 和 之间交替。即如果 ，则 , ，依此类推。只有当下标为偶数时，顶点才属于 。因为起点和终点是同一个顶点（），所以 必须是偶数。
因此，图中不可能存在奇数长度的环。
""
假设 中不包含奇数长度的环。首先假设 是联通的
任选一个起始顶点 ，定义两个集合：
我们断言 内部均不存在边，由于 互斥且并为 ，所以如果断言成立，那么我们就成功划分了 ，即 为二分图
假设 （或 ）内部存在一条边 ，首先我们证明 到 和 的最短路径都不可能经过
因为如若不然，比如 到 的最短路径 包含 ，那么首先 必然是这条路径的最后一段，否则后面的部分都被删去也是一个满足要求的路径，与最短性矛盾，因此这个路径去掉最后一段构成了 到 的一个路径
这时，这个 到 的路径一定是 到 的最短路径，否则可以找到一个更小的路径 ，这时 是一个更短的路径，与 的最短性矛盾
这时我们得到：
与奇偶性相同矛盾，于是断言成立，所以 是二分图
最后，如若 可被分为 个联通分量 （），则对每个联通分量使用以上的策略，可以把 分割为 ，分别内部无边，则对任意的 （或 ），若 不等，由连通分量假设知二者之间也无边，因此，我们可以把 分割为彼此无边的
即证 本身是二分图
综上，证毕
(c)
对这个唯一的奇环 去掉任意一个点，这个操作不会生成新的奇环，这是因为如果这个点本来和这个环的其他点构成一个大环，去掉这个点会使得这个环被破坏，如果这个点和这个环不构成大环，去掉这个点对这个环不影响。
因此，由 (b)，去掉任意点，剩下的 都是一个二分图。
那么我们对这个点 着色为颜色 3，可以对 用两种颜色着色（ 着色 1， 着色 2），这时原本的 显然是 well-coloured 的
另一方面，我们再证明不可能用两种颜色对 进行着色，这只需要证明对奇环不能用两种颜色着色，设这个环为
则把 着色为 ， 必须着色为 2， 必须着色为 ，…，最终 必须着色为 ，而这与 矛盾，因此 必须用三种颜色着色，包含 的 也必须用三种颜色着色
综上，需要 3 种
Problem 4
回顾一下 算法的 setting
则输入为 ，由于题目要求使用复杂度为 ，所以考虑使用邻接表来输入
对于第一个问题，对每条边反向添加到 即可
对于第二个问题，在 DFS 递归返回之前将节点放入结果列表即可