問題一覧 > 通常問題

No.1326 ふたりのDominator

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 18
作問者 : NachiaNachia / テスター : QCFiumQCFium
2 ProblemId : 5539 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-01-08 23:47:44

問題文

$N$ 頂点 $M$ 辺の連結な無向グラフが与えられます。
多重辺や自己ループはありません。
頂点には $1$ から $N$ 、辺には $1$ から $M$ の番号が振られています。
辺 $i$ は頂点 $u_i$ と頂点 $v_i$ を結びます。

あなたの目的は、頂点 $x$ でも頂点 $y$ でもない $1$ つの頂点とそれに隣接する辺を消して、頂点 $x$ と頂点 $y$ が異なる連結成分に属するようにすることです。
消すことで目的を達成できる頂点はいくつありますか。

$Q$ 個の $(x,y)$ の組 $(x_1,y_1),(x_2,y_2),\dots,(x_Q,y_Q)$ について求め、それぞれ $1$ 行に出力してください。

入力

入力は以下の形式で与えられます。
$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$

入力の値はすべて整数です。
$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)$
多重辺や自己ループは与えられません。
与えられるグラフは連結です。
$1 \le Q \le 10^5$
$1 \le x_i,y_i \le N$ $(1 \le i \le Q)$

出力

$Q$ 行出力して下さい。
$i$ $(1 \le i \le Q)$ 行目には $(x,y)=(x_i,y_i)$ のときの答えを出力します。
最後に改行してください。

サンプル

サンプル1
入力
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
出力
1
2
0
1
0

グラフは次の図のようになります。

$(x,y)=(1,3)$ のとき、頂点 $7$ を消せば目的が達成されます。
$(x,y)=(3,5)$ のとき、頂点 $7$ または頂点 $10$ を消せば目的が達成されます。
$(x,y)=(4,6)$ のとき、目的は達成されません。
$(x,y)=(8,10)$ のとき、頂点 $5$ を消せば目的が達成されます。
$(x,y)=(10,10)$ のとき、目的は達成されません。 $x=y$ の場合もあります。

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