AT_nupc2024_n しゃくとり on Namori

**$ N $ 頂点 $ N $ 辺**の頂点重み付き単純無向連結グラフ $ G $ と正整数 $ K $ が与えられます。 $ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結んでいます。 また、 各頂点 $ i $ は正整数の重み $ A_i $ を持ちます。 以下を満たす $ G $ 上の単純パスの最大の辺数を求めて下さい。 - パス上に現れる（端点を含む）頂点の重みの総積が $ K $ 以下 単純パスとは？ 単純パスとは、 $ G $ の頂点の列 $ P = (p_1, p_2, \dots, p_\ell) $ であって、「任意の $ 1 \leq i \leq \ell-1 $ について、 $ p_i $ と $ p_{i+1} $ は辺で結ばれている」かつ「同じ頂点は二度現れない」ものです。 $ P $ の辺数は、 $ \ell-1 $ として定義されます。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ K $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_N $ $ v_N $

標準出力へ答えを一行で出力してください。

### 部分点 追加の制約 $ N \le 5000 $ を満たすデータセットに正解した場合は $ 1 $ 点が与えられます。 ### Sample Explanation 1 辺数 $ 3 $ の単純パス $ (5, 2, 3, 6) $ の頂点重みの総積は $ 2 \times 2 \times 1 \times 3 = 12 \leq K = 14 $ です。 一方で、辺数 $ 4 $ 以上の単純パスとその頂点重みの総積は、以下のとおりすべて $ K $ より大きいです。 - $ (1, 4, 3, 2, 5) $ とその逆 : $ 36 $ - $ (2, 1, 4, 3, 6) $ とその逆 : $ 54 $ - $ (3, 4, 1, 2, 5) $ とその逆 : $ 36 $ - $ (4, 1, 2, 3, 6) $ とその逆 : $ 54 $ - $ (5, 2, 1, 4, 3, 6) $ とその逆 : $ 108 $ ### Sample Explanation 2 単純パス $ (5, 2, 1, 4, 3, 6) $ の頂点重みの総積は $ 108 = K $ であり、これより辺数の大きい単純パスはありません。 ### Sample Explanation 3 この入力例において、 $ 2 $ 頂点以上からなる単純パスの頂点の重みの総積は $ K $ より大きくなります。 したがって、 $ 1 $ 頂点のみからなるパス、たとえば $ (1) $ が辺数 $ 0 $ で最大となります。 ### Constraints - $ 3 \le N \le 2\times 10^5 $ - $ 1 \le K \le 10^9 $ - $ 1 \le A_i \le K $ - $ 1 \le u_i < v_i \le N $ - 与えられるグラフは単純無向連結 - 入力はすべて整数