{"raw_statement":[{"iden":"problem statement","content":"There is a connected undirected graph with $N$ vertices and $M$ edges, where the $i$\\-th edge connects vertex $U_i$ and vertex $V_i$ bidirectionally.  \nEach vertex has an integer written on it, with integer $A_v$ written on vertex $v$.\nFor a simple path from vertex $1$ to vertex $N$ (a path that does not pass through the same vertex multiple times), the score is determined as follows:\n\n*   Let $S$ be the sequence of integers written on the vertices along the path, listed in the order they are visited.\n*   If $S$ is not non-decreasing, the score of that path is $0$.\n*   Otherwise, the score is the number of distinct integers in $S$.\n\nFind the path from vertex $1$ to vertex $N$ with the highest score among all simple paths and print that score.\nWhat does it mean for $S$ to be non-decreasing? A sequence $S=(S_1,S_2,\\dots,S_l)$ of length $l$ is said to be non-decreasing if and only if $S_i \\le S_{i+1}$ for all integers $1 \\le i < l$."},{"iden":"constraints","content":"*   All input values are integers.\n*   $2 \\le N \\le 2 \\times 10^5$\n*   $N-1 \\le M \\le 2 \\times 10^5$\n*   $1 \\le A_i \\le 2 \\times 10^5$\n*   The graph is connected.\n*   $1 \\le U_i < V_i \\le N$\n*   $(U_i,V_i) \\neq (U_j,V_j)$ if $i \\neq j$."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $A_2$ $\\dots$ $A_N$\n$U_1$ $V_1$\n$U_2$ $V_2$\n$\\vdots$\n$U_M$ $V_M$"},{"iden":"sample input 1","content":"5 6\n10 20 30 40 50\n1 2\n1 3\n2 5\n3 4\n3 5\n4 5"},{"iden":"sample output 1","content":"4\n\nThe path $1 \\rightarrow 3 \\rightarrow 4 \\rightarrow 5$ has $S=(10,30,40,50)$ for a score of $4$, which is the maximum."},{"iden":"sample input 2","content":"4 5\n1 10 11 4\n1 2\n1 3\n2 3\n2 4\n3 4"},{"iden":"sample output 2","content":"0\n\nThere is no simple path from vertex $1$ to vertex $N$ such that $S$ is non-decreasing. In this case, the maximum score is $0$."},{"iden":"sample input 3","content":"10 12\n1 2 3 3 4 4 4 6 5 7\n1 3\n2 9\n3 4\n5 6\n1 2\n8 9\n4 5\n8 10\n7 10\n4 6\n2 8\n6 7"},{"iden":"sample output 3","content":"5"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}