UOJ Logo

NOI.AC

1S 512MB

#706. Sabotage

统计

题目描述

如何破坏敌方城市的运输网络?

A国和B国正在进行激烈的战争,现在B国想要破坏A国的运输网络。已知A国的运输网络是一个有向无环图,那些没有出边的点都是发号施令的指令部。现在侦察到有两个点$u,v$(有可能$u=v$)上有运输的部队,B国的需要使得这两支运输部队都无法到达任何指令部。

B城只可以选择破坏一个点,使得满足要求。如果破坏的点是$u$或$v$,则该点上的部队直接被摧毁,因此无法到达指令部。你需要回答$q$个独立的询问,对于每个询问,你需要回答有几个点可以作为被破坏的点。

格式

输入格式

第一行为两个正整数$n,m$,分别表示点数和有向边数。

接下来$m$行,每行两个正整数$x,y$,表示一条从$x$到$y$的有向边。

接下来一行,一个正整数$q$,表示有$q$次询问。

接下来$q$行,每行两个正整数$u,v$,表示一次询问。

输出格式

你需要输出$q$行,每行一个非负整数,表示每个询问的答案。

样例

输入1

8 8 
1 2 
3 4 
3 5 
4 6 
4 7 
5 7 
6 8
7 8
3 
1 3 
6 7 
5 7

输出1

0
1
2

输入2

9 9
1 2
2 3
3 4
4 5
2 4
6 7
7 8
8 5
5 9
4
1 6
2 3
1 3
7 8

输出2

2
3
3
3

数据规模与约定

对于$30\%$的数据,$n\le 1000,\ m\le 2000,\ q\le 100$;

对于$50\%$的数据,$n\le 10000,\ m\le 15000,\ q\le 5000$;

对于所有的数据,$n\le 10^5,\ m\le 1.5\times 10^5,\ q\le 10^5$。