发现每个点双内两个点的距离为 \(1\)，考虑使用圆方树。
建出圆方树后，方点点权为 \(1\),圆点点权为 \(0\)，每次询问求路径上的点权和即可。
代码
#include<bits/stdc++.h>
using namespace std;
namespace IO{template<typename T>inline void read(T&x){x=0;char c=getchar();bool f=0;while(!isdigit(c)) c=='-'?f=1:0,c=getchar();while(isdigit(c)) x=x*10+c-'0',c=getchar();f?x=-x:0;}template<typename T>inline void write(T x){if(x==0){putchar('0');return ;}x<0?x=-x,putchar('-'):0;short st[50],top=0;while(x) st[++top]=x%10,x/=10;while(top) putchar(st[top--]+'0');}inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}inline void write(char c){putchar(c);}inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
const int maxn=100010;
int n,m,q,dfn[maxn],low[maxn],tot,cnt,fa[maxn*2][20],deep[maxn*2],rdeep[maxn*2];
vector<int>e[maxn],st,r[maxn*2];
void dfs(int u){st.push_back(u);dfn[u]=low[u]=++tot;for(int v:e[u]){if(dfn[v]){low[u]=min(low[u],dfn[v]);continue;}dfs(v);low[u]=min(low[u],low[v]);if(low[v]==dfn[u]){cnt++;while(st.back()!=v){r[cnt].push_back(st.back()),r[st.back()].push_back(cnt);st.pop_back();}r[cnt].push_back(st.back()),r[st.back()].push_back(cnt);st.pop_back();r[cnt].push_back(u),r[u].push_back(cnt);}}
}
void dfs2(int u,int fa=0){rdeep[u]=rdeep[fa]+1;::fa[u][0]=fa;for(int i=1;i<=19;i++) ::fa[u][i]=::fa[::fa[u][i-1]][i-1];for(int v:r[u]){if(v==fa) continue;deep[v]=deep[u]+(v>n);dfs2(v,u);}
}
int lca(int u,int v){if(rdeep[u]<rdeep[v]) swap(u,v);for(int i=19;i>=0;i--) if(rdeep[fa[u][i]]>=rdeep[v]) u=fa[u][i];if(u==v) return u;for(int i=19;i>=0;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];return fa[u][0];
}
signed main(){read(n,m,q);cnt=n;for(int i=1;i<=m;i++){int u,v;read(u,v);e[u].push_back(v),e[v].push_back(u);}for(int i=1;i<=n;i++) if(dfn[i]==0) dfs(i),st.clear();dfs2(1);for(int i=1;i<=q;i++,write('\n')){int u,v;read(u,v);int l=lca(u,v);write(deep[u]+deep[v]-deep[l]-deep[fa[l][0]]);}return 0;
}