Tarjan的三大应用之一：求解点双联通分量。
求解点双联通分量。然后缩点，差分优化即可。
//BZOJ 3331
//by Cydiater
//2016.10.29
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <map>
#include <cstring>
#include <string>
#include <algorithm>
#include <set>
#include <bitset>
#include <iomanip>
#include <ctime>
#include <vector>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define Auto(i,a) for(int i=LINK[a];i;i=e[i].next)
#define vci vector<int>
#define pb push_back
const int MAXN=4e5+5;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,M,Q,lable[MAXN],dfn[MAXN],low[MAXN],stack[MAXN],top=0,dfs_clock=0,fa[MAXN][25],dep[MAXN],group_num=0;
vci group[MAXN];
struct edge{int x,y,next;};
struct Graph{
int LINK[MAXN],len;
Graph(){memset(LINK,0,sizeof(LINK));len=0;}
edge e[MAXN];
inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].x=x;}
inline void Insert(int x,int y){insert(x,y);insert(y,x);}
void tarjan(int node){
dfn[node]=low[node]=++dfs_clock;
stack[++top]=node;int son=0;
Auto(i,node)if(!dfn[e[i].y]){
tarjan(e[i].y);
cmin(low[node],low[e[i].y]);
if(low[e[i].y]>=dfn[node]){
int tmp;group_num++;
do{
tmp=stack[top--];
group[group_num].pb(tmp);
}while(tmp!=e[i].y);
group[group_num].pb(node);
}
}else cmin(low[node],dfn[e[i].y]);
}
void dfs(int node,int deep,int father){
fa[node][0]=father;dep[node]=deep;
Auto(i,node)if(e[i].y!=father)dfs(e[i].y,deep+1,node);
}
void get_ancestor(){
up(i,1,20)up(node,1,N+group_num)if(fa[node][i-1])
fa[node][i]=fa[fa[node][i-1]][i-1];
}
int LCA(int x,int y){
if(x==y) return x;
if(dep[x]<dep[y])swap(x,y);
down(i,20,0)if(dep[x]-(1<<i)>=dep[y])x=fa[x][i];
if(x==y) return x;
down(i,20,0)if(fa[x][i]!=0&&fa[x][i]!=fa[y][i]){
x=fa[x][i];y=fa[y][i];
}
return fa[x][0];
}
void re_dfs(int node){
Auto(i,node)if(e[i].y!=fa[node][0]){
re_dfs(e[i].y);
lable[node]+=lable[e[i].y];
}
}
}G1,G2;
namespace solution{
void init(){
N=read();M=read();Q=read();
up(i,1,M){
int x=read(),y=read();
G1.Insert(x,y);
}
}
void slove(){
G1.tarjan(1);
up(i,1,group_num)up(j,0,group[i].size()-1)G2.Insert(i+N,group[i][j]);
G2.dfs(1,0,0);G2.get_ancestor();
memset(lable,0,sizeof(lable));
while(Q--){
int x=read(),y=read(),lca=G2.LCA(x,y);
lable[x]++;lable[y]++;lable[lca]--;lable[fa[lca][0]]--;
}
G2.re_dfs(1);
}
void output(){
up(i,1,N)printf("%d\n",lable[i]);
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
slove();
output();
return 0;
}