{"raw_statement":[{"iden":"statement","content":"You are given a graph with $n$ nodes and $m$ **directed** edges. One lowercase letter is assigned to each node. We define a path's value as the number of the most frequently occurring letter. For example, if letters on a path are \"_abaca_\", then the value of that path is $3$. Your task is find a path whose value is the largest."},{"iden":"input","content":"The first line contains two positive integers $n, m$ ($1 \\leq n, m \\leq 300\\,000$), denoting that the graph has $n$ nodes and $m$ directed edges.\n\nThe second line contains a string $s$ with only lowercase English letters. The $i$\\-th character is the letter assigned to the $i$\\-th node.\n\nThen $m$ lines follow. Each line contains two integers $x, y$ ($1 \\leq x, y \\leq n$), describing a directed edge from $x$ to $y$. Note that $x$ can be equal to $y$ and there can be multiple edges between $x$ and $y$. Also the graph can be not connected."},{"iden":"output","content":"Output a single line with a single integer denoting the largest value. If the value can be arbitrarily large, output _\\-1_ instead."},{"iden":"examples","content":"Input\n\n5 4\nabaca\n1 2\n1 3\n3 4\n4 5\n\nOutput\n\n3\n\nInput\n\n6 6\nxzyabc\n1 2\n3 1\n2 3\n5 4\n4 3\n6 4\n\nOutput\n\n\\-1\n\nInput\n\n10 14\nxzyzyzyzqx\n1 2\n2 4\n3 5\n4 5\n2 6\n6 8\n6 5\n2 10\n3 9\n10 9\n4 6\n1 10\n2 8\n3 7\n\nOutput\n\n4"},{"iden":"note","content":"In the first sample, the path with largest value is $1 \\to 3 \\to 4 \\to 5$. The value is $3$ because the letter '_a_' appears $3$ times."}],"translated_statement":[{"iden":"statement","content":"你被给定一个包含 $n$ 个节点和 $m$ 条有向边的图。每个节点被分配一个小写字母。我们定义一条路径的值为该路径上出现频率最高的字母的出现次数。例如，如果路径上的字母为 \"_abaca_\"，则该路径的值为 $3$。你的任务是找到一条值最大的路径。\n\n第一行包含两个正整数 $n, m$ ($1 lt.eq n, m lt.eq 300 thin 000$)，表示图中有 $n$ 个节点和 $m$ 条有向边。\n\n第二行包含一个仅由小写英文字母组成的字符串 $s$。第 $i$ 个字符是分配给第 $i$ 个节点的字母。\n\n接下来 $m$ 行，每行包含两个整数 $x, y$ ($1 lt.eq x, y lt.eq n$)，描述一条从 $x$ 指向 $y$ 的有向边。注意 $x$ 可以等于 $y$，$x$ 和 $y$ 之间可能存在多条边，且图可能不连通。\n\n请输出一行一个整数，表示最大的值。如果值可以任意大，请输出 _-1_。 \n\n在第一个样例中，值最大的路径是 $1 arrow.r 3 arrow.r 4 arrow.r 5$。该路径的值为 $3$，因为字母 '_a_' 出现了 $3$ 次。"},{"iden":"input","content":"第一行包含两个正整数 $n, m$ ($1 lt.eq n, m lt.eq 300 thin 000$)，表示图中有 $n$ 个节点和 $m$ 条有向边。第二行包含一个仅由小写英文字母组成的字符串 $s$。第 $i$ 个字符是分配给第 $i$ 个节点的字母。接下来 $m$ 行，每行包含两个整数 $x, y$ ($1 lt.eq x, y lt.eq n$)，描述一条从 $x$ 指向 $y$ 的有向边。注意 $x$ 可以等于 $y$，$x$ 和 $y$ 之间可能存在多条边，且图可能不连通。"},{"iden":"output","content":"请输出一行一个整数，表示最大的值。如果值可以任意大，请输出 _-1_。"},{"iden":"examples","content":"输入\n5 4\nabaca\n1 2\n1 3\n3 4\n4 5\n输出\n3\n\n输入\n6 6\nxzyabc\n1 2\n3 1\n2 3\n5 4\n4 3\n6 4\n输出\n-1\n\n输入\n10 14\nxzyzyzyzqx\n1 2\n2 4\n3 5\n4 5\n2 6\n6 8\n6 5\n2 10\n3 9\n10 9\n4 6\n1 10\n2 8\n3 7\n输出\n4"},{"iden":"note","content":"在第一个样例中，值最大的路径是 $1 arrow.r 3 arrow.r 4 arrow.r 5$。该路径的值为 $3$，因为字母 '_a_' 出现了 $3$ 次。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be a directed graph with $ n = |V| $ nodes and $ m = |E| $ edges.  \nLet $ s \\in \\Sigma^n $ be a string of lowercase letters, where $ s_i $ is the letter assigned to node $ i \\in V $.  \nFor a path $ P = (v_1, v_2, \\dots, v_k) $, define its *letter frequency vector* $ f_P : \\Sigma \\to \\mathbb{N} $ as $ f_P(c) = |\\{ i \\in \\{1,\\dots,k\\} \\mid s_{v_i} = c \\}| $, and its *value* as $ \\max_{c \\in \\Sigma} f_P(c) $.  \n\n**Constraints**  \n1. $ 1 \\le n, m \\le 300{,}000 $  \n2. Each edge $ (x, y) \\in E $ satisfies $ 1 \\le x, y \\le n $  \n3. Self-loops and multiple edges are allowed  \n4. The graph may be disconnected  \n\n**Objective**  \nCompute $ \\max_{P \\in \\mathcal{P}} \\max_{c \\in \\Sigma} f_P(c) $, where $ \\mathcal{P} $ is the set of all finite paths in $ G $.  \nIf there exists a path with arbitrarily large value (i.e., a cycle containing at least one node with letter $ c $ and reachable from itself with positive length), output $ -1 $.","simple_statement":null,"has_page_source":false}