問題一覧 > 通常問題

No.1326 Two Dominators

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 30
作問者 : 👑 Nachia / テスター : QCFium
お気に入りにしたユーザー ProblemId : 5539 / 自分の提出
問題文最終更新日: 2021-01-08 23:47:44
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2020 (順位表) の他の問題:

Problem Statement

You are given a connected undirected graph with $N$ vertices and $M$ edges.
It has no multiple edges or self-loops.
The vertices are numbered from $1$ to $N$, and the edges are numbered from $1$ to $M$.
Edge $i$ connects vertex $u_i$ and vertex $v_i$.

Your goal is to delete $1$ vertex that is neither vertex $x$ nor vertex $y$, together with its incident edges, so that vertex $x$ and vertex $y$ belong to different connected components.
How many vertices are there whose deletion achieves the goal?

Answer this for each of the $Q$ pairs $(x,y)$: $(x_1,y_1),(x_2,y_2),\dots,(x_Q,y_Q)$, and print each answer on $1$ line.

Input

The input is given in the following format.
$N\ M$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_M\ v_M$
$Q$
$x_1\ y_1$
$x_2\ y_2$
$\vdots$
$x_Q\ y_Q$

All input values are integers.
$3 \le N \le 5 \times 10^4$
$N-1 \le M \le 10^5$
$1 \le u_i,v_i \le N$ $(1 \le i \le M)$
The input contains no multiple edges or self-loops.
The given graph is connected.
$1 \le Q \le 10^5$
$1 \le x_i,y_i \le N$ $(1 \le i \le Q)$

Output

Print $Q$ lines.
On the $i$-th line $(1 \le i \le Q)$, print the answer for $(x,y)=(x_i,y_i)$.
Print a newline at the end.

Sample

Sample 1
Input
10 12
1 7
1 9
2 3
2 7
3 7
4 7
4 10
5 10
5 8
6 7
6 10
7 9
5
1 3
3 5
4 6
8 10
10 10
Output
1
2
0
1
0

The graph is shown in the figure below.

When $(x,y)=(1,3)$, deleting vertex $7$ achieves the goal.
When $(x,y)=(3,5)$, deleting vertex $7$ or vertex $10$ achieves the goal.
When $(x,y)=(4,6)$, the goal cannot be achieved.
When $(x,y)=(8,10)$, deleting vertex $5$ achieves the goal.
When $(x,y)=(10,10)$, the goal cannot be achieved. Note that $x=y$ is possible.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。