原题链接：P2783 有机化学之神偶尔会做作弊
一看，是黑题，太毒瘤了，不写
什么单链？？！
只会画有机化学中正六边形的我觉得这样不行QAQ（我才初二）
当然，题目也给你了详细的解释
实际呢，这道题先给你了一个图，让你把图中的环全缩成一个点，在求两个点之间的距离
这道题估计是你谷最简单黑题
先用tarjan缩点，再重新建图
在新建的图上跑lca求距离
就是这么简单
代码上有些细节需要注意
#pragma GCC optimize("O3")#define N 100001#include <bits/stdc++.h>using namespace std;inline int read(){register int f=1,x=0;register char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');return f*x;}inline int Min(register int a,register int b){if(a<b)return a;return b;}inline void Swap(register int &a,register int &b){a^=b^=a^=b;}int tmp[64];inline void print(register int res) {if(res==0) {puts("0");return;}if(res<0) {putchar('-');res=0-res;}while(res) tmp[++tmp[0]]=res&1,res>>=1;while(*tmp) putchar(tmp[(*tmp)--]+'0');putchar('\n');} int n,m,tot,q,sign,top,cnt;int first[N<<1][2],next[N<<1][2],to[N<<1][2],dfn[N],low[N],sta[N],id[N],dep[N];int p[N][50],xx[N],yy[N];bool insta[N];inline void ADD(register int x,register int y,register int w){next[++tot][w]=first[x][w];to[tot][w]=y;first[x][w]=tot;}inline void add(register int x,register int y,register int w){ADD(x,y,w);ADD(y,x,w);}inline void DFS(register int x,register int fa){dfn[x]=low[x]=++sign;sta[++top]=x;insta[x]=true;int k=first[x][0],u;while(k){u=to[k][0];if(u==fa){k=next[k][0];continue;}if(!dfn[u]){DFS(u,x);low[x]=Min(low[u],low[x]);}else if(insta[u])low[x]=Min(low[x],dfn[u]);k=next[k][0];}if(low[x]==dfn[x]){++cnt;while(19260817){int y=sta[top--];id[y]=cnt;if(x==y)break;}}return;}inline void rebuild(){tot=0;for(register int i=1;i<=m;++i)if(id[xx[i]]!=id[yy[i]])add(id[xx[i]],id[yy[i]],1);}inline void DFS2(register int son,register int fa){dep[son]=dep[fa]+1;p[son][0]=fa;for(register int i=first[son][1];i;i=next[i][1])if(to[i][1]!=fa)DFS2(to[i][1],son);}inline int LCA(register int a,register int b){if(a==b)return a;if(dep[a]>dep[b])Swap(a,b);for(register int i=20;i>=0;--i)if(dep[p[b][i]]>=dep[a])b=p[b][i];if(a==b)return a;for(register int i=20;i>=0;--i)if(p[a][i]!=p[b][i])a=p[a][i],b=p[b][i];return p[a][0];}int main(){n=read(),m=read();for(register int i=1;i<=m;++i){xx[i]=read(),yy[i]=read();add(xx[i],yy[i],0);}for(register int i=1;i<=n;++i)if(!dfn[i])DFS(i,0);rebuild();DFS2(1,0); for(register int i=1;i<=20;++i)for(register int j=1;j<=cnt;++j)p[j][i]=p[p[j][i-1]][i-1];q=read();while(q--){int a=read(),b=read();a=id[a],b=id[b];int lca=LCA(a,b),ans=0;ans=dep[a]+dep[b]-(dep[lca]<<1)+1;print(ans);}return 0;}
