問題文

各頂点に正整数が書かれた無向グラフ G' に対するスコアを以下で定義します。

• G' のすべての連結成分に対して、各連結成分に含まれる頂点に書かれた正整数の総積を求め、その和をスコアとする。

正整数からなる長さ N の数列 A = (A_1, A_2, \ldots, A_N) と正整数 M が与えられます。頂点に 1 から N の番号が付けられた N 頂点 N - 1 辺の単純連結無向グラフ G であって、以下の条件を満たすものが存在するかどうかを判定し、存在するのであれば辺の作成方法を教えてください。

• G の頂点 i (1 \leq i \leq N) には A_i が書かれている。
• G から 1 本以下の辺を削除して得られる N 個のグラフに対するスコアの総和が M 以下となる。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 1 \leq T \leq 5
• 2 \leq N \leq 200{,}000
• 1 \leq M \leq 10^{18}
• 1 \leq A_i \leq 10^{18}
• 1 つの入力に含まれるテストケースについて、N の総和は 200{,}000 以下
• 入力はすべて整数

小課題

1. (1 点) N \leq 7
2. (99 点) 追加の制約はない

入力例 1

3
4 60
1 2 3 4
4 24
1 2 3 4
7 1000000000000000000
1 2 3 4 5 6 7

出力例 1

Yes
1 2
1 3
1 4
No
Yes
1 3
3 5
5 4
2 5
7 6
1 6

1 つ目のテストケースとその出力例について、例えば以下のような場合が考えられます。

• どの辺も削除されない場合、スコアは (1 \times 2 \times 3 \times 4) = 24
• 1 番目の辺が削除される場合、スコアは (2) + (1 \times 3 \times 4) = 14
• 2 番目の辺が削除される場合、スコアは (3) + (1 \times 2 \times 4) = 11
• 3 番目の辺が削除される場合、スコアは (4) + (1 \times 2 \times 3) = 10

スコアの総和は 59 となります。 他にもスコアの総和が 60 以下となる G はありますが、そのどれを出力しても正解となります。

2 つ目のテストケースについて、スコアの総和が 24 以下になるような G は存在しないため、No を出力します。

このケースは小課題 1 の制約を満たします。

入力例 2

3
10 20
1 1 1 1 1 1 1 1 1 1
4 3000
20 24 1 6
10 3000000
20 2 4 1 6 20 2 4 1 6

出力例 2

Yes
3 1
4 7
5 7
10 3
2 9
8 9
3 8
6 9
7 1
No
Yes
10 9
4 6
5 4
4 9
9 3
9 1
8 4
1 2
7 9

このケースは小課題 1 の制約を満たしません。