Loginess
本题没有可用的提交语言。
Description
You are given a directed graph with $n$ vertices and $m$ edges. The vertices are numbered with integers from $1$ to $n$. Each vertex $v$ is labeled with a positive integer $a_v$.
A path is a sequence of $\ell \geq 2$ distinct vertices $v_1$, $v_2$, $\ldots$, $v_{\ell}$ such that for each $i$ from $1$ to $\ell-1$ there is an edge from $v_i$ to $v_{i+1}$. The loginess of an edge from vertex $u$ to vertex $v$ is defined as $\log_{a_u}(a_v)$. The loginess of such a path is equal to the product of the loginess of the edges.
Your task is to find the maximum loginess over all possible paths in the graph!
The first line contains two integers $n$ and $m$ ($2 \leq n \leq 2\cdot 10^5$, $1 \leq m \leq 2\cdot 10^5$), the numbers of vertices and edges in the graph. The next line contains $n$ integers $a_1$, $\ldots$, $a_n$ ($2 \leq a_v \leq 10^9$), the labels of the vertices. The next $m$ lines contain the description of the edges. The $i$-th of these line contains two integers $u_i$ and $v_i$, the endpoints of the $i$-th edge of the graph, meaning there is a directed edge from $u_i$ to $v_i$.
The graph contains no self-loops or duplicate edges. Between any two vertices, there can be edges in both directions.
Output a single real number, the maximum loginess over all paths in the graph. The relative or absolute error cannot exceed $10^{-6}$.
Input
The first line contains two integers $n$ and $m$ ($2 \leq n \leq 2\cdot 10^5$, $1 \leq m \leq 2\cdot 10^5$), the numbers of vertices and edges in the graph. The next line contains $n$ integers $a_1$, $\ldots$, $a_n$ ($2 \leq a_v \leq 10^9$), the labels of the vertices. The next $m$ lines contain the description of the edges. The $i$-th of these line contains two integers $u_i$ and $v_i$, the endpoints of the $i$-th edge of the graph, meaning there is a directed edge from $u_i$ to $v_i$.
The graph contains no self-loops or duplicate edges. Between any two vertices, there can be edges in both directions.
Output
Output a single real number, the maximum loginess over all paths in the graph. The relative or absolute error cannot exceed $10^{-6}$.
3 4
10 20 30
2 1
3 1
2 3
3 2
4 2
10 30 20 10
2 3
4 1
1.13534758
1