#pragma comment(linker, "/STACK:65536000") #include #include #include #include #include #include #include #include #include #define clr(a,b) memset(a,b,sizeof(a)) #define mpr(a,b) make_pair(a,b) #define ll long long #define eps 1e-6 using namespace std; const int N=100005,M=300005; int n,m,q,eid,id,now,top; int head[N],ed[M],nxt[M]; int dfn[N],low[N],gid[N]; int sta[N],block[N]; vector >gra[N],qu[N]; int f[N],vis[N],come[N],out[N],fa[N]; int tlca[3*N],pt[3*N][2]; int aa[N],bb[N],cc[N]; int findfa(int s){return s==fa[s]?s:fa[s]=findfa(fa[s]);} void addedge(int s,int e){ ed[eid]=e;nxt[eid]=head[s];head[s]=eid++; } void tarjan(int s,int f,int b){ dfn[s]=low[s]=++now; sta[top++]=s;block[s]=b; for(int i=head[s];~i;i=nxt[i]){ int e=ed[i]; if(i==f||i==(f^1))continue; if(!dfn[e]){ tarjan(e,i,b); low[s]=min(low[s],low[e]); }else low[s]=min(low[s],dfn[e]); } if(low[s]==dfn[s]){ id++; while(top){ int k=sta[--top]; gid[k]=id; if(k==s)return ; } } } void lca(int s,int f){ fa[s]=s; for(int i=0;i<(int)gra[s].size();i++){ int e=gra[s][i].first; if(e==f)continue; lca(e,s); fa[findfa(e)]=s; } vis[s]=1; for(int i=0;i<(int)qu[s].size();i++){ int e=qu[s][i].first,d=qu[s][i].second; if(vis[e])tlca[d]=findfa(e); } } void dfs(int s,int f){ for(int i=0;i<(int)qu[s].size();i++){ int d=qu[s][i].second; int k=(tlca[d]==s)?-1:out[tlca[d]]; if(~pt[d][0])pt[d][1]=k; else pt[d][0]=k; } for(int i=0;i<(int)gra[s].size();i++){ int e=gra[s][i].first,g=gra[s][i].second; if(e==f){ come[s]=g;continue; } out[s]=g; dfs(e,s); } } int main(){ while(~scanf("%d%d",&n,&m)){ eid=0;clr(head,-1); for(int i=0;i