{"raw_statement":[{"iden":"statement","content":"A couple of friends, Axel and Marston are travelling across the country of Bitland. There are _n_ towns in Bitland, with some pairs of towns connected by one-directional roads. Each road in Bitland is either a pedestrian road or a bike road. There can be multiple roads between any pair of towns, and may even be a road from a town to itself. However, no pair of roads shares the starting and the destination towns along with their types simultaneously.\n\nThe friends are now located in the town 1 and are planning the travel route. Axel enjoys walking, while Marston prefers biking. In order to choose a route diverse and equally interesting for both friends, they have agreed upon the following procedure for choosing the road types during the travel:\n\n*   The route starts with a pedestrian route.\n*   Suppose that a beginning of the route is written in a string _s_ of letters P (pedestrain road) and B (biking road). Then, the string is appended to _s_, where stands for the string _s_ with each character changed to opposite (that is, all pedestrian roads changed to bike roads, and vice versa).\n\nIn the first few steps the route will look as follows: P, PB, PBBP, PBBPBPPB, PBBPBPPBBPPBPBBP, and so on.\n\nAfter that the friends start travelling from the town 1 via Bitlandian roads, choosing the next road according to the next character of their route type each time. If it is impossible to choose the next road, the friends terminate their travel and fly home instead.\n\nHelp the friends to find the longest possible route that can be travelled along roads of Bitland according to the road types choosing procedure described above. If there is such a route with more than 1018 roads in it, print -1 instead."},{"iden":"input","content":"The first line contains two integers _n_ and _m_ (1 ≤ _n_ ≤ 500, 0 ≤ _m_ ≤ 2_n_2) — the number of towns and roads in Bitland respectively.\n\nNext _m_ lines describe the roads. _i_\\-th of these lines contains three integers _v__i_, _u__i_ and _t__i_ (1 ≤ _v__i_, _u__i_ ≤ _n_, 0 ≤ _t__i_ ≤ 1), where _v__i_ and _u__i_ denote start and destination towns indices of the _i_\\-th road, and _t__i_ decribes the type of _i_\\-th road (0 for a pedestrian road, 1 for a bike road). It is guaranteed that for each pair of distinct indices _i_, _j_ such that 1 ≤ _i_, _j_ ≤ _m_, either _v__i_ ≠ _v__j_, or _u__i_ ≠ _u__j_, or _t__i_ ≠ _t__j_ holds."},{"iden":"output","content":"If it is possible to find a route with length strictly greater than 1018, print -1. Otherwise, print the maximum length of a suitable path."},{"iden":"examples","content":"Input\n\n2 2\n1 2 0\n2 2 1\n\nOutput\n\n3\n\nInput\n\n2 3\n1 2 0\n2 2 1\n2 2 0\n\nOutput\n\n\\-1"},{"iden":"note","content":"In the first sample we can obtain a route of length 3 by travelling along the road 1 from town 1 to town 2, and then following the road 2 twice from town 2 to itself.\n\nIn the second sample we can obtain an arbitrarily long route by travelling the road 1 first, and then choosing road 2 or 3 depending on the necessary type."}],"translated_statement":[{"iden":"statement","content":"两位朋友 Axel 和 Marston 正在 Bitland 国旅行。Bitland 有 #cf_span[n] 座城市，某些城市对之间由单向道路连接。Bitland 的每条道路要么是步行道，要么是自行车道。任意两座城市之间可能存在多条道路，甚至可能存在从一座城市到自身的道路。然而，没有任何两条道路同时具有相同的起点、终点和类型。\n\n朋友们现在位于城市 1，并计划旅行路线。Axel 喜欢步行，而 Marston 更喜欢骑车。为了使路线对两位朋友都同样有趣，他们约定按照以下规则选择旅行时的道路类型：\n\n前几步的路线类型序列为：P, PB, PBBP, PBBPBPPB, PBBPBPPBBPPBPBBP，依此类推。\n\n之后，朋友们从城市 1 出发，沿着 Bitland 的道路旅行，每次根据路线类型序列中的下一个字符选择下一条道路。如果无法选择下一条道路，则旅行终止，他们改乘飞机回家。\n\n请帮助朋友们找出根据上述道路类型选择规则所能旅行的最长可能路线。如果存在一条包含超过 #cf_span[1018] 条道路的路线，请输出 -1。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 500]，#cf_span[0 ≤ m ≤ 2n2]），分别表示 Bitland 的城市数和道路数。\n\n接下来的 #cf_span[m] 行描述道路。第 #cf_span[i] 行包含三个整数 #cf_span[vi]、#cf_span[ui] 和 #cf_span[ti]（#cf_span[1 ≤ vi, ui ≤ n]，#cf_span[0 ≤ ti ≤ 1]），其中 #cf_span[vi] 和 #cf_span[ui] 分别表示第 #cf_span[i] 条道路的起点和终点城市编号，#cf_span[ti] 表示该道路的类型（0 为步行道，1 为自行车道）。保证对于任意两个不同的索引 #cf_span[i] 和 #cf_span[j]（#cf_span[1 ≤ i, j ≤ m]），要么 #cf_span[vi ≠ vj]，要么 #cf_span[ui ≠ uj]，要么 #cf_span[ti ≠ tj]。\n\n如果存在一条长度严格大于 #cf_span[1018] 的路线，请输出 -1；否则，输出满足条件的最长路径长度。\n\n在第一个样例中，可以通过从城市 1 沿道路 1 行驶到城市 2，然后两次沿道路 2 从城市 2 到自身，获得一条长度为 3 的路线。\n\n在第二个样例中，可以先沿道路 1 行驶，然后根据所需类型选择道路 2 或 3，从而获得任意长的路线。"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 500]，#cf_span[0 ≤ m ≤ 2n2]），分别表示 Bitland 的城市数和道路数。接下来的 #cf_span[m] 行描述道路。第 #cf_span[i] 行包含三个整数 #cf_span[vi]、#cf_span[ui] 和 #cf_span[ti]（#cf_span[1 ≤ vi, ui ≤ n]，#cf_span[0 ≤ ti ≤ 1]），其中 #cf_span[vi] 和 #cf_span[ui] 分别表示第 #cf_span[i] 条道路的起点和终点城市编号，#cf_span[ti] 表示该道路的类型（0 为步行道，1 为自行车道）。保证对于任意两个不同的索引 #cf_span[i] 和 #cf_span[j]（#cf_span[1 ≤ i, j ≤ m]），要么 #cf_span[vi ≠ vj]，要么 #cf_span[ui ≠ uj]，要么 #cf_span[ti ≠ tj]。"},{"iden":"output","content":"如果存在一条长度严格大于 #cf_span[1018] 的路线，请输出 -1；否则，输出满足条件的最长路径长度。"},{"iden":"examples","content":"输入\n2 2\n1 2 0\n2 2 1\n输出\n3\n\n输入\n2 3\n1 2 0\n2 2 1\n2 2 0\n输出\n-1"},{"iden":"note","content":"在第一个样例中，可以通过从城市 1 沿道路 1 行驶到城市 2，然后两次沿道路 2 从城市 2 到自身，获得一条长度为 3 的路线。在第二个样例中，可以先沿道路 1 行驶，然后根据所需类型选择道路 2 或 3，从而获得任意长的路线。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of towns, $ m \\in \\mathbb{Z}_{\\geq 0} $ the number of directed roads.  \nLet $ G = (V, E) $ be a directed multigraph with $ V = \\{1, 2, \\dots, n\\} $.  \nEach edge $ e \\in E $ is a triple $ (v, u, t) $ where $ v, u \\in V $, $ t \\in \\{0,1\\} $, representing a directed road from $ v $ to $ u $ of type $ t $ (0: pedestrian, 1: bike).  \n\nLet $ S = (s_1, s_2, s_3, \\dots) $ be the infinite sequence over $ \\{0,1\\} $ defined recursively:  \n- $ S_1 = 0 $  \n- $ S_{2^k + i} = 1 - S_i $ for $ 1 \\leq i \\leq 2^k $, $ k \\geq 0 $  \nThis generates the Thue-Morse sequence: $ 0, 01, 0110, 01101001, \\dots $  \n\nLet $ \\mathcal{P} $ be the set of finite paths $ \\pi = (v_0, e_1, v_1, e_2, \\dots, e_\\ell, v_\\ell) $ such that:  \n- $ v_0 = 1 $  \n- For each $ i \\in \\{1, \\dots, \\ell\\} $, $ e_i = (v_{i-1}, v_i, t_i) \\in E $ and $ t_i = s_i $  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 500 $  \n2. $ 0 \\leq m \\leq 2n^2 $  \n3. All edges are distinct by $ (v, u, t) $  \n\n**Objective**  \nFind the maximum $ \\ell \\in \\mathbb{Z}_{\\geq 0} $ such that there exists a path $ \\pi \\in \\mathcal{P} $ of length $ \\ell $.  \nIf such $ \\ell > 10^{18} $, output $ -1 $. Otherwise, output $ \\ell $.","simple_statement":null,"has_page_source":false}