N. 逃不掉的路

Type: RemoteJudge

1000ms

512MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

现代社会，路是必不可少的。

共有 $n$ 个城镇， $m$ 条道路，任意两个城镇都有路相连，而且往往不止一条。

但有些路年久失修，走着很不爽。

按理说条条大路通罗马，大不了绕行其他路呗——可小撸却发现：从 $a$ 城到 $b$ 城不管怎么走，总有一些逃不掉的必经之路。

他想请你计算一下， $a$ 到 $b$ 的所有路径中，有几条路是逃不掉的？

输入格式

第一行是 $n$ 和 $m$ ，用空格隔开。

接下来 $m$ 行，每行两个整数 $x$ 和 $y$ ，用空格隔开，表示 $x$ 城和 $y$ 城之间有一条长为 $1$ 的双向路。

第 $m+2$ 行是 $q$ 。

接下来 $q$ 行，每行两个整数 $a$ 和 $b$ ，用空格隔开，表示一次询问。

输出格式

对于每次询问，输出一个正整数，表示 $a$ 城到 $b$ 城必须经过几条路。

每个输出占一行。

0
1

提示

$1\le n \le 10^5$ ， $1\le m \le 2\times 10^5$ ， $1\le q \le 10^5$
对于全部的数据， $1 \le x,y,a,b \le n$ ；对于任意的道路，两端的城市编号之差不超过 $10^4$ ；
任意两个城镇都有路径相连；同一条道路不会出现两次；道路的起终点不会相同;查询的两个城市不会相同。

Day1A.割点与割边

Not Claimed

Status: Done
Problem: 18
Open Since: 2026-1-26 0:00
Deadline: 2026-3-31 23:59
Extension: 24 hour(s)

N. 逃不掉的路

逃不掉的路

题目描述

输入格式

输出格式

提示

Day1A.割点与割边

SIGN IN