AT_oupc2023_day1_p Score for Cutting Graph

各頂点に正整数が書かれた無向グラフ $ 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 $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられます。 > $ T $ $ \mathrm{case}_1 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられます。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

$ k $ 番目に $ \mathrm{case}_k $ の答えを出力してください。 スコアの総和を $ M $ 以下にすることが不可能である場合は `No` と出力してください。 可能である場合は $ 1 $ 行目に `Yes` と出力し、 $ 2 $ 行目以降に $ G $ の辺の作成方法を以下の形式に従って $ N-1 $ 行出力してください。 > $ s_1 $ $ t_1 $ $ s_2 $ $ t_2 $ $ \vdots $ $ s_{N-1} $ $ t_{N-1} $ $ s_j, t_j $ は $ G $ の辺を表します。これは頂点 $ s_j $ と頂点 $ t_j $ を結ぶ辺であることを示します。 答えが複数存在する場合、どれを出力しても正解となります。

### 小課題 1. ( $ 1 $ 点) $ N \leq 7 $ 2. ( $ 99 $ 点) 追加の制約はない ### Sample Explanation 1 $ 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 $ の制約を満たします。 ### Sample Explanation 2 このケースは小課題 $ 1 $ の制約を満たしません。 ### Constraints - $ 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 $ 以下 - 入力はすべて整数