Codeforces Round #776 (Div. 3) 問題文和訳

A. Deletions of Two Adjacent Letters / Удаления двух соседних букв
- 入力
- 出力
- 入出力例
- 注記
B. DIV + MOD
- 入力
- 出力
- 入出力例
- 注記
C. Weight of the System of Nested Segments / Вес системы вложенных отрезков
- 入力
- 出力
- 入出力例
- 注記
D. Twist the Permutation / Петя и циклические сдвиги
- 入力
- 出力
- 入出力例
- 注記
E. Rescheduling the Exam / Перенос экзамена
- 入力
- 出力
- 入出力例
- 注記
F. Vitaly and Advanced Useless Algorithms / Виталий и Advanced Useless Algorithms
G. Counting Shortcuts / Подсчёт коротких путей

A. Deletions of Two Adjacent Letters / Удаления двух соседних букв

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

文字列 $s$ が与えられます。その文字列の長さは奇数で、ラテン文字の小文字から成ります。

文字列の長さが $1$ よりも大きい限り、次の操作を行うことができます: 文字列 $s$ 内の任意の隣接する2文字を選び、それを文字列から削除するという操作です。例えば、文字列"lemma"に操作を一度行うと、次の4つの文字列のいずれかを得ることができます: "mma", "lma", "lea", "lem"。具体的には、1回の操作で、文字列の長さは $2$ だけ短くなります。

形式的にが、文字列 $s$ を $s = s_1s_2\dots s_n$ $(n \gt 1)$ という形で表されるとします。1回の操作で、任意のインデックス $1$ $(1 \leq i \lt n)$ を選び、 $s = s_1s_2\dots s_{i-1}s_{i+2}\dots s_n$ に置き換えます。

与えられた文字列 $s$ と文字 $c$ について、最終的に等式 $s=c$ が成立するような一連の操作が可能であるか判別して下さい。即ち、文字 $c$ から成る長さ $1$ の文字列で処理が終了するような一連の操作は存在するでしょうか?

入力

入力データの1行目には1個の整数 $t$ $(1 \leq t \leq 10^3)$ が与えられる、これは入力のテストケース数である。

$t$ 個のテストケースの説明が続く。各テストケースは2行で表される。

$1$ から $49$ までの奇数長で、ラテンアルファベットの小文字で構成される文字列 $s$
ラテンアルファベットの小文字1文字 $c$ から成る文字列

出力

各テストケースについて、別々の行に次を出力せよ。

文字列 $s$ を $s = c$ が真となるように変換できる場合、YES
そうでない場合、NO

YESとNOはどのレターケースで出力してもよい(例えば、文字列yEs, yes, Yes, YESは肯定とみなされる)。

入出力例

5
abcde
c
abcde
b
x
y
aaaaaaaaaaaaaaa
a
contest
t

YES
NO
NO
YES
YES

注記

1つ目のテストケースでは、 $s =$ "abcde"です。 $s =$ "c"にしなければなりません。1回目の操作では、最初の2文字を消し、 $s =$ "cde"となります。2回目の操作で最後の2文字を消し、期待される値 $s =$ "c"を得ます。

3つ目のテストケースでは、 $s =$ "x"で、 $s =$ "y"にしなければなりません。明らかに、これを実現することはできません。

B. DIV + MOD

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

少し前、Влад*1が面白い函数を思いつきました。

$\displaystyle f_a(x) = \left\lfloor \frac{x}{a} \right\rfloor + x \bmod a$ ; ここでは $\displaystyle \left\lfloor \frac{x}{a} \right\rfloor$ は $\displaystyle \frac{x}{a}$ の切り捨てを、 $x \bmod a$ は $x$ を $a$ で割った余りを表す。

例えば、 $a = 3,$ $x = 11$ とすると、 $\displaystyle f_3(11) = \left\lfloor \frac{11}{3} \right\rfloor + 11 \bmod 3 = 3+2 = 5$ という値になります。

数 $a$ は固定で、Владにとって既知です。 $x$ が $l$ から $r$ までの両端を含む $l \lt x \lt r$ 任意の整数を取りえる場合、 $f_a(x)$ の最大値をВладが求められるよう手助けをしてください。

入力

入力データの1行目には1個の整数 $t$ $(1 \leq t \leq 10^4)$ が与えられる、これは入力のテストケース数である。

$t$ 行が続く、そのそれぞれの行には3個の整数 $l_i,\,r_i,\,a_i$ $(1 \leq l_i \leq r_i \leq 10^9,$ $1 \leq a_i \leq 10^9)$ が与えられる、これらは区間の左右の境界と固定値 $a$ である。

出力

各テストケースについて、単一行に1個の整数を出力せよ、その数とは与えられた $a$ について与えられた区間上での函数の最大値である。

入出力例

5
1 4 3
5 8 4
6 10 6
1 1000000000 1000000000
10 12 8

注記

1つ目のテストケースでは

$\displaystyle f_3(1) = \left\lfloor \frac{1}{3} \right\rfloor + 1 \bmod 3 = 0 + 1 = 1$
$\displaystyle f_3(2) = \left\lfloor \frac{2}{3} \right\rfloor + 2 \bmod 3 = 0 + 2 = 2$
$\displaystyle f_3(3) = \left\lfloor \frac{3}{3} \right\rfloor + 3 \bmod 3 = 1 + 0 = 1$
$\displaystyle f_3(4) = \left\lfloor \frac{4}{3} \right\rfloor + 4 \bmod 3 = 1 + 1 = 2$

答えとしては、自明として、 $f_3(2)$ と $f_3(4)$ が適切です。

C. Weight of the System of Nested Segments / Вес системы вложенных отрезков

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

数直線上に $m$ 点が存在し、 $i$ 個目の点の座標は $x_i$ で、重み $w_i$ を持ちます。全ての点の座標は異なり、点には $1$ から $m$ までの番号が振られています。

各組 $i,\,j$ $(1 \leq i \lt j \leq n)$ について条件 $l_i \lt l_j \lt r_j \lt r_i$ を満たすとき、 $n$ 個の区間の列 $[l_1,\,r_i],$ $[l_2,\,r_2],$ $\dots,$ $[l_n,\,r_n]$ は入れ子区間と呼ばれます。言い換えると、2番目の区間は1番目の区間の厳密な内側にあり、 3番目の区間は2番目の区間の厳密な内側にある、という具合に成り立っているというものです。

与えられた数 $n$ について、次を満たす入れ子区間を求めて下さい。

各区間の両端が、与えらえた $m$ 個の点の1つである
区間の端点として用いられる $2 \cdot n$ 個の点の重みの合計が最小である

例えば、 $m = 8$ とします。与えられた点が、図中に示され、重みは赤で、座標は青で書かれています。次のような3つの入れ子区間のシステムを構築します。

1つ目の区間の重み: $1 + 1 = 2$
2つ目の区間の重み: $10 + (-1) = 9$
1つ目の区間の重み: $3 + (-2) = 1$
システム内の全ての区間の重みの和: $2 + 9 + 1 = 12$

f:id:Flkanjin:20220309230248p:plain — 3つの入れ子区間のシステム

入力

入力データの1行目には1個の整数 $t$ $(1 \leq t \leq 10^5)$ が与えられる、これは入力のテストケース数である。

各テストケースの前には空行が書かれている。

各テストケースの1行目には2つの正整数 $n$ $(1 \leq n \leq 10^5),$ $m$ $(2 \cdot n \leq m \lt 2 \cdot 10^5)$ が与えられる。

続く $m$ 行には整数の組 $x_i$ $(-10^9 \leq x_i \leq 10^9),$ $w_i$ $(-10^4 \leq w_i \lt 10^4)$ が与えられる、これらはそれぞれ番号 $i$ の点の座標と重みを表す。全ての $x_i$ は相異なる。

全てのテストケースでの $m$ の和が $2 \cdot 10^5$ を超えないことは保証されている。

出力

各テストケースについて、 $n+1$ 行出力せよ。その1行目には構築したシステムの重みを出力し、続く $n$ 行にはちょうど2個の整数を出力せよ、2つの整数とは $i$ 個目の区間 $(1 \leq i \leq n)$ の端点のインデックスである。区間の端点を出力する順番は重要ではなく、先に左端点のインデックスを出力し、次に右端点の番号を出力してもよく、その逆でもよい。

最小の重みで入れ子区間のシステムを構築する方法が複数ある場合は、そのうちのどれかを出力せよ。

入出力例

注記

1つ目のテストケースでは、問題文の例と一致します。構築されたシステムの重みが最小であることは証明できます。

2つ目のテストケースでは、 $6$ 個の点しかないため、それぞれを用いて $3$ 個の区間を構成する必要があります。

D. Twist the Permutation / Петя и циклические сдвиги

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

Петя*2は $1$ から $n$ の数の配列 $a$ を持っていて、 $a[i] = i$ となっていました。

彼は $n$ 回の操作を順次に行いました。そして最後に、彼は新しい状態の配列 $a$ を受け取りました。

$i$ 回目の操作では、Петяは配列の最初の $i$ 個の要素を選び、それらを右にに似の回数循環シフトさせました( $i+1$ 以上のインデックスの要素はそのままです)。1回の右への循環シフトは、配列 $a = [a_1,\,a_2,\,\dots,\,a_n]$ を配列 $a=[a_i,\,a_1,\,a_2,\,\dots,\,a_{i-2},\,a_{i-1},\,a_{i+1},\,a_{i+2},\,\dots,\,a_n]$ にするような変換です。

例えば、 $a=[5,\,4,\,2,\,1,\,3]$ で $i = 3$ (つまり、3回目の操作)の場合、この操作の結果として、彼は次の3つの配列のいずれかを得ることができます。

$a = [5,\,4,\,2,\,1,\,3]$ ( $0$ 回の循環シフト、もしくは $3$ で割り切れる回数)
$a = [2,\,5,\,4,\,1,\,3]$ ( $1$ 回の循環シフト、もしくは $3$ で割ると $1$ 余る回数)
$a = [4,\,2,\,5,\,1,\,3]$ ( $2$ 回の循環シフト、もしくは $3$ で割ると $2$ 余る回数)

また、別の例を見てみましょう。 $n = 6$ 、即ち初期状態で $a = [1,\,2,\,3,\,4,\,5,\,6]$ とします。考えられるシナリオの1つは次の通りです。

$i = 1$ : Петяが何回循環シフトを行っても配列 $a$ は変化しない
$i = 2$ : Петяが $1$ 回循環シフトを行うとすると、配列は $a = [\textbf{2},\,\textbf{1},\,3,\,4,\,5,\,6]$ となる
$i = 3$ : Петяが $1$ 回循環シフトを行うとすると、配列は $a = [\textbf{3},\,\textbf{2},\,\textbf{1},\,4,\,5,\,6]$ となる
$i = 4$ : Петяが $2$ 回循環シフトを行うとすると、配列は $a = [\textbf{1},\,\textbf{4},\,\textbf{3},\,\textbf{2},\,5,\,6]$ となる
$i = 5$ : Петяが $0$ 回循環シフトを行うとすると、配列は変化しない
$i = 6$ : Петяが $4$ 回循環シフトを行うとすると、配列は $a = [\textbf{3},\,\textbf{2},\,\textbf{5},\,\textbf{6},\,\textbf{1},\,\textbf{4}]$ となる

$n$ 回の操作を行った後の配列 $a$ の最終状態が与えられます。この結果になるような操作方法が存在するか判別してください。答えが存在する場合、 $n$ 回の操作のそれぞれで行った循環シフトの回数を出力して下さい。

入力

入力データの1行目には1個の整数 $t$ $(1 \leq t \leq 500)$ が与えられる、これは入力のテストケース数である。

テストケースについての記述が続く。

各テストケースの1行目には1個の整数 $n$ $(2 \leq n \leq 2 \cdot 10^3)$ が与えられる、これは配列 $a$ の長さである。

次の行には配列 $a$ の最終状態である $n$ 個の整数 $a_1,\,a_2,\,\dots,\,a_n$ $(1 \leq a_i \leq n)$ が与えられる。全ての $a_i$ は相異なる。

全てのテストケースでの $m$ の和が $2 \cdot 10^3$ を超えないことは保証されている。

出力

各テストケースについて、答えを個別の行に出力せよ。

与えられた最終の値 $a$ が各操作での任意の数の巡回シフトによって得ることが場合は $-1$ を出力せよ。そうでない場合、 $n$ 個の非負整数 $d_1,\,d_2,\,\dots,\,d_n$ $(d_i \geq 0)$ を出力せよ、ここでの $d_i$ は、 $i$ 番目の操作の間に配列の最初の $i$ 個の要素が右に $d_i$ 回巡回シフトされたことを意味する。

複数の答えが存在する場合、シフトの総数が最小となる(つまり $d_i$ の値の合計が最小の)ものを出力せよ。そのような答えが複数存在する場合は、そのうちのいずれかを出力せよ。

入出力例

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

0 1 1 2 0 4 
0 0 1 
0 1 2 0 2 5 6 2

注記

1つ目のテストケースは、問題文中の例と同じです。

2つ目の入力データセットは単純なものです。答え $[3,\,2,\,1]$ でも同じ順列になりますが、シフトの総数 $3+2+1$ は $0+0+1$ よりも大きいため、この答えは正しくありません。

E. Rescheduling the Exam / Перенос экзамена

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

Дмитрий*3は試験期間に $n$ 個の試験に合格しなければなりません。試験期間は $1$ 日目から $d$ 日間に渡ります。 $i$ 番目の試験は $a_i$ 日目 $(1 \leq a_i \leq d)$ に行われ、 $a_i$ はすべて異なるものです。

f:id:Flkanjin:20220310171210p:plain — $n=3,$ $d=12,$ $a=[3,\,5,\,9]$ の場合のサンプル。試験日は橙。Дмитрийには1つ目の試験の前に $2$ 日、2つ目の試験の前に $1$ 日、3つ目の試験の前に $3$ 日の休みがある。

$n=3,$ $d=12,$ $a=[3,\,5,\,9]$ の場合のサンプル。試験日は橙。Дмитрийには1つ目の試験の前に $2$ 日、2つ目の試験の前に $1$ 日、3つ目の試験の前に $3$ 日の休みがある。

試験期間のスケジュールについて、Дмитрийは特別な値 $\mu$ について考えています、この値は全ての試験の前の休息時間の最小値です。例えば、上の図について、 $\mu = 1$ です。スケジュールにおいて、彼は正確に $n$ 個の数、試験 $i-1$ と $i$ の間の休息日数(試験機関の開始を $i=0$ と見做す*4 )を数えます。そして、この $n$ 個の数の中で最小値である $\mu$ を求めます。

Дмитрийは試験期間のスケジュールを改善できると考えています。彼は、1つの試験の日程を変更する(任意の1つの $a_i$ を変更する)よう求めることができます。 $a_i$ が全て異なるままで、 $\mu$ の値ができるだけ大きくなるように、彼が日付を変更するのを手助けしてください。

例えば、上のスケジュールについて、2回目の試験を試験期間の一番最後に動かすのがДмитрийにとって最も有利です。新しいスケジュールは次のようになります。

f:id:Flkanjin:20220310173431p:plain — 試験前の休息期間は $[2,\,2,\,5]$ となり、 $\mu = 2$ である

試験前の休息期間は $[2,\,2,\,5]$ となり、 $\mu = 2$ である

(状況を改善するために試験を移動させる方法がない場合、)Дмитрийは提供されたスケジュールを変更しないままにしておくこともできます。

入力

入力データの1行目には1個の整数 $t$ $(1 \leq t \leq 10^4)$ が与えられる、これは入力のテストケース数である。テストケースについての記述が続く。

各テストケースの前には空行が書かれている。

各テストケースの1行目には2個の整数 $n,\,d$ $(2 \leq n \leq 2 \cdot 10^5,$ $1 \leq d \leq 10^9)$ が与えられる、これらはそれぞれ、試験の個数と期間の長さである。

各テストケースの2行目には $n$ 個の整数 $a_i$ $(1 \leq a_i \leq d,$ $a_i \lt a_{i+1})$ が与えられる、この $i$ 番目の数が $i$ 番目の試験の日付を表す。

全てのテストケースでの $n$ の和が $2 \cdot 10^5$ を超えないことは保証されている。

出力

各テストケースについて、Дмитрийが1つの試験を任意の日に移動させることができる場合の $\mu$ の最大値を出力せよ。 $a_i$ の値は全て異なるままでなければならない。

入出力例

9

3 12
3 5 9

2 5
1 5

2 100
1 2

5 15
3 6 9 12 15

3 1000000000
1 400000000 500000000

2 10
3 4

2 2
1 2

4 15
6 11 12 13

2 20
17 20

注記

1つ目の入出力例は、問題文中に書かれています。

2つ目の入出力例での最適なスケジュール変更は次の通りです。

f:id:Flkanjin:20220310174740p:plain — 初期スケジュール

f:id:Flkanjin:20220310174950p:plain — 新しいスケジュール

3つ目の入出力例では、 $1$ 日目の試験を $4$ 日目から $100$ 日目の間の任意の日に移動させる必要があります。

4つ目の入出力例では、いかなるスケジュールの変更でも $\mu$ が小さくなるため、スケジュールをそのままにしておくべきです。

5つ目の入出力例では、 $1$ 日目の試験を $100000000$ 日目から $300000000$ 日目の間の任意の日に移動させる必要があります。

6つ目の入出力例での最適なスケジュール変更は次の通りです。

f:id:Flkanjin:20220310175502p:plain — 初期スケジュール

f:id:Flkanjin:20220310175514p:plain — 新しいスケジュール

7つ目の入出力例では、どの日も試験日であり、スケジュールを変更することは不可能です。

F. Vitaly and Advanced Useless Algorithms / Виталий и Advanced Useless Algorithms

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

Виталий*5は"Advanced Useless Algorithms"というコースを登録しました。このコースは $n$ 個のタスクで構成されています。Виталийはを行うのにコース登録した日からタスク $i$ を完了させるのに $a_i$ 時間あるということを計算しました。言い換えれば、 $i$ 番目のタスクの締め切りの前に $a_i$ 時間あるということです。配列 $a$ は昇順ソートされていて、即ち、タスク番号は提出する順序に対応しています。

Виталийは何事も誠実に行うため、各タスクを $100 \%$ 以上完了させたいと思っています。初期状態では、彼の各タスクの完了率は $0 \%$ です。

Виталийには複数のトレーニングオプションがあり、各オプションは1度までしか使用できません。 $i$ 番目のオプションは3つの整数 $e_i,\,t_i,\,p_i$ によって特徴づけられます。Виталийが $i$ 番目のオプションを利用した場合、(現時点から) $t_i$ 時間後に彼は、タスク $e_i$ の進捗を $p_i \%$ 進めることになります。

例えば、Виталийに3つのタスクがあるとします。配列 $a$ が $a = [5,\,7,\,8]$ であるとします。Виталийには次の $5$ つのオプションがあるとします: $[e_1=1,\,t_1=1,\,p_1=30],$ $[e_2=2,\,t_2=3,\,p_2=50],$ $[e_3=2,\,t_3=3,\,p_3=100],$ $[e_4=1,\,t_4=1,\,p_4=80],$ $[e_5=3,\,t_5=3,\,p_5=100]$ 。

このとき、次のように準備を行うと、Виталийは時間内に全てを完了させることができます。

Виталийが $4$ 番目のオプションを選ぶ。 $1$ 時間後に、 $1$ 番目のタスクを $80 \%$ にする。 $1$ 番目のタスクの締切まであと $4$ 時間である。
Виталийが $3$ 番目のオプションを選ぶ。 $3$ 時間後に、 $2$ 番目のタスクを完了させる。 $1$ 番目のタスクの締切まであと $1$ 時間、 $3$ 番目のタスクの締切まであと $4$ 時間である。
Виталийが $1$ 番目のオプションを選ぶ。 $1$ 時間後に、 $1$ 番目のタスクを $110 \%$ で完了させ、締め切りちょうどに $1$ 番目のタスクが完了したことになる。
Виталийが $5$ 番目のオプションを選ぶ。 $2$ 時間後に、 $3$ 番目のタスクを完了させ、締め切りちょうどに $1$ 番目のタスクが完了したことになる。*6

このようにして、 $4$ つのオプションを行うことで、Виталийは時間内にコースを完全に完了させることができます。

Виталийは正しい順番でタスクを完了させることができるように、オプションを出力し、Виталийを助けてください。各オプションは一度までしか使用できないことに注意してください。答えが複数存在する場合、そのいずれをを出力してもいいです。

入力

入力データの1行目には1個の整数 $T$ $(1 \leq T \leq 10^4)$ が与えられる、これは入力のテストケース数である。

テストケースについての記述が続く。

各テストケースの記述の1行目には2個の整数 $n,\,m$ $(1 \leq n,\,m \leq 10^5)$ が与えられる、これらはそれぞれ、タスクとトレーニングオプションの個数である。

次の行には $n$ 個の整数 $a_1,\,a_2,\,\dots,\,a_n$ $(1 \leq a_i \leq 10^9)$ が与えられる、タスク $i$ の締め切りを表す。配列の値は非減少、即ち $a_1 \leq a_2 \leq \dots \leq a_n$ となっている。

続く $m$ 行には、3つ組の整数 $e_i,\,t_i,\,p_i$ $(1 \leq e_i \leq n,$ $1 \leq t_i \leq 10^9,$ $1 \leq p_i leq 100)$ が与えられる、もしВиталийがこのオプションを選択すれば、 $t_i$ 時間後にタスク $e_i$ の進捗を $p_i \%$ 進める。オプションには入力データの順に $1$ から $m$ までの番号が振られている。

全てのテストケースでの $n+m$ の和が $2 \cdot 10^5$ を超えないことは保証されている。

出力

各テストケースについて、1行目に、数 $k$ を出力せよ、これは、オプションのうち $k$ 個を用いて、Виталийが各タスクを $100 \%$ 以上で完了できることを表す。同じオプションは繰り返してはいけない。Виталийが全てのタスクを時間内に完了できない場合は、 $-1$ を出力せよ。

もし答えが存在する場合、続く行に $1$ から $m$ までの異なる整数 $k$ 個を、望む順序での選択肢の番号を、出力せよ。複数の答えが存在する場合、そのいずれを出力してもよい。

入出力例

5
3 5
5 7 8
1 1 30
2 3 50
2 3 100
1 1 80
3 3 100
1 5
51
1 36 91
1 8 40
1 42 83
1 3 45
1 13 40
2 9
9 20
2 8 64
2 7 64
1 20 56
2 8 76
2 20 48
1 2 89
1 3 38
2 18 66
1 7 51
3 2
7 18 33
1 5 80
3 4 37
2 5
569452312 703565975
1 928391659 66
1 915310 82
2 87017081 92
1 415310 54
2 567745964 82

3
3 9
20 31 40
1 9 64
3 17 100
3 9 59
3 18 57
3 20 49
2 20 82
2 14 95
1 8 75
2 16 67
2 6
20 36
2 2 66
2 20 93
1 3 46
1 10 64
2 8 49
2 18 40
1 1
1000000000
1 1000000000 100

G. Counting Shortcuts / Подсчёт коротких путей

テストごとの時間制限: 2秒
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力

$n$ 個の頂点と $m$ 本の辺を持つ無向の連結グラフが与えられます。このグラフには自己辺(ある頂点からそれ自身への辺)や多重辺が含まれません(即ち、各頂点の組の間に1つ以上の辺がない)。グラフの頂点には $1$ から $n$ までの番号が振られています。

頂点 $s$ から $t$ への経路のうち、 $s$ から $t$ までの最短経路と長さの差が $1$ 以下である経路の数を求めて下さい。このとき、同じ頂点や辺を2回以上通るもの(単純でないパス)であっても、条件を満たす形を全てを考慮する必要があります。

f:id:Flkanjin:20220310185641p:plain — $6$ 頂点 $8$ 辺から成るグラフ

例えば、 $n=6,$ $m=8,$ $s=6,$ $t=1$ として、上図のようなグラフであるとします。 $s$ から $t$ への最短経路の長さは $1$ です。長さが最大で $1+1=2$ である経路を全て考えます。

$6 \rightarrow 1$ : 経路長は $1$
$6 \rightarrow 4 \rightarrow 1$ : 経路長は $2$
$6 \rightarrow 2 \rightarrow 1$ : 経路長は $2$
$6 \rightarrow 5 \rightarrow 1$ : 経路長は $2$

合致する経路は全部で4本あります。

入力

入力データの1行目には1個の整数 $t$ $(1 \leq t \leq 10^4)$ が与えられる、これは入力のテストケース数である。テストケースについての記述が続く。

各テストケースの前には空行が書かれている。

各テストケースの1行目には2個の整数 $n,\,m$ $(2 \leq n \leq 2 \cdot 10^5,$ $1 \leq m \leq 2 \cdot 10^5)$ が与えられる、これらはグラフの頂点数と辺の本数である。

2行目には2個の整数 $s,\,t$ $(1 \leq s,\,t \leq n;$ $s \neq t)$ が与えられる、これらは経路の始点と終点の番号である。

続く $m$ 行には辺の記述が与えられ、その $i$ 行目には2個の整数 $u_,\,v_i$ $(1 \leq u_,\,v_i \leq n)$ が与えられる、これらは $i$ 本目の辺が結ぶ頂点の番号である。グラフは連結であり、自己辺や多重辺が含まないことは保証されている。

入力データ内の全てのテストケースでの $n$ の和が $2 \cdot 10^5$ を超えないことは保証されている。同様に、入力データ内の全てのテストケースでの $m$ の和が $2 \cdot 10^5$ を超えないことは保証されている。

出力

各テストケースについて、単一の数を出力せよ、その数とは $s$ から $t$ までの最短経路と長さの差が $1$ 以下である経路の個数である。

この数は大きくなるかもしれないため、modulo $10^9+7$ で出力せよ。

入出力例

*1:露[vɫat](ヴラド、Vlad); Vladはルーマニア語などではスラブ系の男性名 Vladimirなどの短縮形・愛称の一つであるが、ここではロシア人名とした

*2:露[ˈpʲetʲə](ピェチャ、Petya, Pjetja): ロシア男性名 Пётр(Петр、Petr、ピョートル)の指小形、愛称、英Peteに相当、Пётрは英独Peter等と同じく聖ペテロに由来

*3:露[ˈdmʲitrʲɪj](ドミトリー、Dmitri, Dmitry, Dmitrij) ロシア男性名、英Demetriusに相当、Пётрは英独Peter等と同じく古典ギリシャ男性名Δημήτριος(Dēmḗtrios)に由来

*4:この部分は意訳、恐らく誤記あり

*5:露[vʲɪˈtalʲɪj](ヴィタリー、Vitali, Vitaly, Vitalij) ロシア男性名、ラテン男性名Vītālisに由来

*6:この部分も意訳