考虑树的 \(\text{dfs}\)（根据当前节点 \(u\) 找到 \(v\) 满足存在 \((u, v)\)，然后走向 \(v\) 进入更深的搜索）为和能做到 \(O(n)\) 的复杂度。
原因是没有环的情况，到每个点只有一条路径。
回到这个题，有 \(m\) 条边导致到每个点可能有多条路径了。
能发现其实还是能 \(\text{dfs}\)。
正确性是显然的。
时间复杂度可以去尝试证一个比较宽松的上界，考虑如果走完了 \(m\) 条多余边，那么剩下的可以当作一棵树来处理，就是 \(O(n)\) 的，而对于这 \(m\) 条边可以考虑枚举其顺序和其是从哪一头走又或者不走，\(O(m!3^m)\)，加上枚举起点，于是时间复杂度是 \(O(n^2\times m!3^m)\)。
考虑到这个 \(m\) 很小，于是类似虚树的思想，考虑只拎出来 \(2m\) 个点到根的路径。
那么其他的非关键点到这些关键点肯定都会经过一个固定的关键点，考虑把这些点直接挂在这个关键点上即可。
正确性是因为这些点走出去肯定都要走过这个点，所以走出去后就相当于就是这个点。
时间复杂度 \(O(m^2\log^2 n\times m!3^m)\)。
#include<bits/stdc++.h>
const int mod = 1e9 + 7;
int n;
std::map<int, int> id; int idt;
int ex[4], ey[4];
std::vector<int> E[320];
int siz[320], P[320];
bool vis[320];
inline int dep(int x) {return std::__lg(x);}
inline int calc(int u) {
int dn = dep(n), du = dep(u);
if (dn == du) return 1;
return ((1 << dn - du) - 1) + std::max(0, std::min(1 << dn - du, n - (u << dn - du) + 1));
}
inline void add(int u) {! id.count(u) && (id[u] = ++idt, P[idt] = u);}
void dfs1(int u, int fa) {
for (int v : E[u]) v != fa && (siz[u] -= siz[v], dfs1(v, u), 1);
}
inline int dfs2(int u) {
vis[u] = 1;
int ans = siz[u];
for (int v : E[u]) ! vis[v] && ((ans += dfs2(v)) %= mod);
vis[u] = 0;
return ans;
}
int main() {
int m; scanf("%d%d", &n, &m);
add(1);
for (int i = 0; i < m; i++) {
scanf("%d%d", &ex[i], &ey[i]);
for (int x = ex[i]; x; x >>= 1) add(x);
for (int x = ey[i]; x; x >>= 1) add(x);
}
for (int i = 1; i <= idt; i++) siz[i] = calc(P[i]);
for (int i = 2; i <= idt; i++) E[i].push_back(id[P[i] >> 1]), E[id[P[i] >> 1]].push_back(i);
dfs1(1, 0);
for (int i = 0; i < m; i++) E[id[ex[i]]].push_back(id[ey[i]]), E[id[ey[i]]].push_back(id[ex[i]]);
int ans = 0;
for (int i = 1; i <= idt; i++) (ans += 1ll * siz[i] * dfs2(i) % mod) %= mod;
printf("%d\n", ans);
return 0;
}