给定一个有 $N$ 个顶点和 $N$ 条边的顶点带权重的简单无向连通图 $G$，以及一个正整数 $K$。第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。每个顶点 $i$ 具有一个正整数权重 $A_i$。

请你求出满足以下条件的 $G$ 上的简单路径的最大边数：

• 路径上出现的所有顶点（包括端点）的权重之积不超过 $K$。

什么是简单路径？简单路径是指一列顶点 $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$ 分。

样例解释 1

边数为 $3$ 的简单路径 $(5, 2, 3, 6)$ 的顶点权重之积为 $2 \times 2 \times 1 \times 3 = 12 \leq K = 14$。而其他边数大于 $3$ 的简单路径及其顶点权重之积如下：

• $(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$

这些都大于 $K$。

样例解释 2

简单路径 $(5, 2, 1, 4, 3, 6)$ 的顶点权重之积为 $108 = K$，没有边数更大的路径。

样例解释 3

在这个输入样例中，任意包含 $2$ 个及以上顶点的简单路径的顶点权重之积都会超过 $K$。因此，仅包含单个顶点的路径，比如 $(1)$，其边数为 $0$，也是最大的。

数据范围与约定

• $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$
• 所给图为简单无向连通图
• 所有输入均为整数。

由 ChatGPT 5 翻译