{"problem":{"name":"Non-Decreasing Colorful Path","description":{"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.   Each vertex has an integer written on it, with i","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc335_e"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   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$.\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc335_e","tags":[],"sample_group":[["5 6\n10 20 30 40 50\n1 2\n1 3\n2 5\n3 4\n3 5\n4 5","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."],["4 5\n1 10 11 4\n1 2\n1 3\n2 3\n2 4\n3 4","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$."],["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","5"]],"created_at":"2026-03-03 11:01:13"}}