Counting on a directed graph Problem Code: GRAPHCNT

Read problems statements in Mandarin Chinese and Russian.

Given an directed graph with N nodes (numbered from 1 to N) and M edges, calculate the number of unordered pairs (X, Y) such there exist two paths, one from node 1 to node X, and another one from node 1 to node Y, such that they don‘t share any node except node 1.

Input

There is only one test case in one test file.

The first line of each test case contains two space separated integers N, M. Each of the next M lines contains two space separated integers u, v denoting a directed edge of graph G, from node u to node v. There are no multi-edges and self loops in the graph.

Output

Print a single integer corresponding to the number of unordered pairs as asked in the problem..

Constraints and Subtasks

• 1 ≤ N ≤ 10⁵
• 0 ≤ M ≤ 5 * 10⁵

Subtask 1: (30 points)

• The graph is a Directed Acyclic Graph (DAG) i.e. there is no cycle in the graph.

Subtask 2: (20 points)

• N * M ≤ 50000000

Subtask 3 (50 points)

• No additional constraints

Example

Input:6 61 21 31 42 52 63 6Output:14

Explanation

There are 14 pairs of vertices as follows: 
(1,2) 
(1,3) 
(1,4) 
(1,5) 
(1,6) 
(2,3) 
(2,4) 
(2,6) 
(3,4) 
(3,5) 
(3,6) 
(4,5) 
(4,6) 
(5,6)

Author:5★ztxz16

Tester:7★kevinsogo

Editorial:http://discuss.codechef.com/problems/GRAPHCNT

Tags:dominator may15 medium-hard ztxz16

Date Added:25-03-2015

Time Limit:2 secs

Source Limit:50000 Bytes

Languages:ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<stack>using namespace std;const int maxn=100000+5,maxm=500000+5;int n,m,tot,f[maxn],fa[maxn],id[maxn],dfn[maxn],siz[maxn],node[maxn],semi[maxn],idom[maxn];long long ans;stack<int> dom[maxn];struct M{		int cnt,hd[maxn],to[maxm],nxt[maxm];		inline void init(void){		cnt=0;		memset(hd,-1,sizeof(hd));	}		inline void add(int x,int y){		to[cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt++;	}	}G,tr;inline bool cmp(int x,int y){	return dfn[semi[x]]<dfn[semi[y]];}inline int find(int x){	if(f[x]==x)		return x;	int fx=find(f[x]);	node[x]=min(node[f[x]],node[x],cmp);	return f[x]=fx;}inline void dfs(int x){	dfn[x]=++tot;id[tot]=x;	for(int i=tr.hd[x];i!=-1;i=tr.nxt[i])		if(!dfn[tr.to[i]])			dfs(tr.to[i]),fa[tr.to[i]]=x;}inline void LT(void){	dfs(1);dfn[0]=tot<<1;	for(int i=tot,x;i>=1;i--){		x=id[i];		if(i!=1){			for(int j=G.hd[x],v;j!=-1;j=G.nxt[j])				if(dfn[G.to[j]]){					v=G.to[j];					if(dfn[v]<dfn[x]){						if(dfn[v]<dfn[semi[x]])							semi[x]=v;					}					else{						find(v);						if(dfn[semi[node[v]]]<dfn[semi[x]])							semi[x]=semi[node[v]];					}				}			dom[semi[x]].push(x);		}		while(dom[x].size()){			int y=dom[x].top();dom[x].pop();find(y);			if(semi[node[y]]!=x)				idom[y]=node[y];			else				idom[y]=x;		}		for(int j=tr.hd[x];j!=-1;j=tr.nxt[j])			if(fa[tr.to[j]]==x)				f[tr.to[j]]=x;	}	for(int i=2,x;i<=tot;i++){		x=id[i];		if(semi[x]!=idom[x])			idom[x]=idom[idom[x]];	}	idom[id[1]]=0;}signed main(void){	tr.init();G.init();	scanf("%d%d",&n,&m);	for(int i=1,x,y;i<=m;i++)		scanf("%d%d",&x,&y),tr.add(x,y),G.add(y,x);	for(int i=1;i<=n;i++)		f[i]=node[i]=i;	LT();ans=1LL*tot*(tot-1);	for(int i=tot;i>=2;i--){		siz[id[i]]++; 		if(idom[id[i]]!=1)			siz[idom[id[i]]]+=siz[id[i]];		else			ans-=1LL*siz[id[i]]*(siz[id[i]]-1);	}	ans>>=1;	printf("%lld\n",ans);	return 0;}