P11022 「LAOI-6」Yet Another Graph Coloration Problem

[English statement](https://www.luogu.com.cn/problem/U477166). You must submit your code at the Chinese version of the statement.

小 R 有一张 $n$ 个节点和 $m$ 条的边简单无向图，节点的编号依次为 $1 \sim n$。她想要为图中的每个节点分配黑色或白色的颜色，使得： - 有至少 $1$ 个黑色节点； - 有至少 $1$ 个白色节点； - 对于任何一对点对 $(u, v)$，只要 $u$ 和 $v$ 的颜色不同，就存在至少 $2$ 条从 $u$ 到 $v$ 的不同的简单路径。 - 简单路径是图上指不重复经过同一点的路径。 - 若两条简单路径不同，要么其长度不同，要么至少存在一个正整数 $i$ 使两条路径经过的第 $i$ 个点不同。 或者，报告解不存在。

无

无

**本题采用捆绑测试**。 - Subtask 0（15 pts）：$\sum 2^n \leq 2^{16}$。 - Subtask 1（25 pts）：$n \leq 3\times 10^3$，$m \leq 3\times 10^3$，$\sum n \leq 10^4$，$\sum m \leq 2\times 10^4$。 - Subtask 2（5 pts）：保证图不连通。 - Subtask 3（10 pts）：保证每个点的度数均为 $2$。 - Subtask 4（20 pts）：保证 $n = m$。 - Subtask 5（25 pts）：无特殊限制。 对于所有数据，保证 $1 \leq T \leq 10^5$，$2 \leq n \leq 2 \times 10^5$，$0 \leq m \leq 2 \times 10^5$，$\sum n \leq 2\times 10^6$，$\sum m \leq 2\times 10^6$，保证给出的图无重边、无自环。