#P3488. [ONTAK2010]Highways
[ONTAK2010]Highways
Highways
题目描述
Byteland 有 座城市,由 条双向普通道路连通。只使用普通道路时,两座城市之间有且只有一条简单路线,称为它们之间的主路线。为了缓解交通拥堵,Byteland 还修建了一些双向高速公路。
每条路线都是一串相连的道路,沿途的城市不能重复。从城市 到城市 可以走主路线,也可以走一条恰好使用一条高速公路的路线。后一种路线与主路线只能在两端的城市 相交,中途不能经过主路线上的任何城市。
对每对给定的城市,求可以采用的路线总数,主路线也算一种。
输入格式
第一行包含一个整数 。城市编号从 到 。
接下来 行,每行两个整数 ,表示一条普通道路的两个端点。
接下来一行是高速公路数 ,其后 行分别给出一条高速公路的两个端点。
再接下来一行是询问数 ,其后 行分别给出一次询问的起点 和终点 。
输出格式
输出 行,第 行是第 次询问的路线数。
样例 #1
9
1 2
2 3
4 2
1 5
5 6
7 5
7 8
9 7
4
2 5
3 4
6 4
8 3
4
4 9
2 5
1 6
1 7
1
4
2
2
数据范围
,。所有城市编号在 到 之间。每条公路的两个端点不同,每次询问的起点和终点也不同。