> [CF521E Cycling City](https://codeforces.com/contest/521/problem/E)
## 题面
- 给定一张 $n$ 个点 $m$ 条边的无向简单图。
- 问图中能否找到两个点，满足这两个点之间有至少三条完全不相交的简单路径。
- $n,m \le 2 \times 10^5$，图不保证连通。
## 题解
首先建出 dfs 树，那么有解的充要条件是**存在至少一条树边被至少两条返祖边覆盖**，这显然可以树上差分判定。
若有解，考虑如何构造方案。
可以通过两次二分，每次判定使用树上差分，找到两条**至少有一条树边被它们覆盖**的返祖边。
在只保留这两条边的情况下构造方案即可，具体方法见代码。
总时间复杂度 $\mathcal O(n \log m)$，可以做到线性但没必要。
## 代码
```cpp
const int N = 2e5 + 7;
int n, m, v[N], dfn[N], num, f[N], t, d[N];
vi e[N], ans[3];
pi p[N];
void dfs(int x) {
dfn[x] = ++num;
for (auto y : e[x])
if (!dfn[y]) f[y] = x, dfs(y);
else if (y != f[x] && dfn[y] < dfn[x]) p[++t] = mp(x, y);
}
void dfs1(int x) {
v[x] = 1;
for (auto y : e[x])
if (f[y] == x) dfs1(y), d[x] += d[y];
}
inline void work(int o) {
--d[p[o].se], ++d[p[o].fi];
}
inline bool ask(int l, int r) {
for (int i = l; i <= r; i++) work(i);
for (int i = 1; i <= n; i++) if (!v[i]) dfs1(i);
bool ok = 0;
for (int i = 0; i <= n; i++) ok |= d[i] > 1, d[i] = v[i] = 0;
return ok;
}
int main() {
rd(n), rd(m);
for (int i = 1, x, y; i <= m; i++)
rd(x), rd(y), e[x].pb(y), e[y].pb(x);
for (int i = 1; i <= n; i++)
if (!dfn[i]) dfs(i);
if (!ask(1, t)) return prints("NO"), 0;
else prints("YES");
int l = 2, r = t;
while (l < r) {
int mid = (l + r) >> 1;
if (ask(1, mid)) r = mid;
else l = mid + 1;
}
int R = l;
l = 1, r = R - 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (ask(mid, R)) l = mid;
else r = mid - 1;
}
int L = l;
work(L), work(R);
for (int i = 1; i <= n; i++) if (!v[i]) dfs1(i);
int Y = 0;
for (int i = 1; i <= n; i++)
if (d[i] == 2 && dfn[i] > dfn[Y]) Y = i;
int X = Y;
ans[0].pb(X);
while (d[X] == 2) ans[0].pb(X = f[X]);
reverse(ans[0].begin(), ans[0].end());
for (int i = 1; i < 3; i++) {
int Z = X, o = i == 1 ? L : R;
ans[i].pb(Z);
while (Z != p[o].se) ans[i].pb(Z = f[Z]);
ans[i].pb(Z = p[o].fi);
while (Z != Y) ans[i].pb(Z = f[Z]);
}
for (int i = 0; i < 3; i++) {
print(ans[i].size(), ' ');
for (auto x : ans[i]) print(x, ' ');
prints("");
}
return 0;
}
```