English · Original
Chinese · Translation
Formal · Original
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.
The 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:
* The route starts with a pedestrian route.
* 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).
In the first few steps the route will look as follows: P, PB, PBBP, PBBPBPPB, PBBPBPPBBPPBPBBP, and so on.
After 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.
Help 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.
## Input
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.
Next _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.
## Output
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.
[samples]
## Note
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.
In 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.
两位朋友 Axel 和 Marston 正在 Bitland 国旅行。Bitland 有 #cf_span[n] 座城镇，某些城镇对之间由单向道路连接。Bitland 的每条道路要么是步行道，要么是自行车道。任意两座城镇之间可能存在多条道路，甚至可能存在从一座城镇到自身的道路。然而，没有任何两条道路同时具有相同的起点、终点和类型。
现在，两位朋友位于城镇 1，并计划旅行路线。Axel 喜欢步行，而 Marston 更喜欢骑车。为了使路线对两位朋友都同样有趣，他们商定了一种选择道路类型的规则：
前几步的路线类型序列为：P, PB, PBBP, PBBPBPPB, PBBPBPPBBPPBPBBP，依此类推。
之后，朋友们从城镇 1 出发，沿着 Bitland 的道路旅行，每次根据路线类型序列中的下一个字符选择下一条道路。如果无法选择下一条道路，旅行将终止，他们将乘飞机回家。
请帮助朋友们找出符合上述道路类型选择规则的最长可能路线。如果存在长度超过 #cf_span[1018] 的路线，请输出 -1。
第一行包含两个整数 #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]。
如果存在长度严格大于 #cf_span[1018] 的路线，请输出 -1；否则，输出符合条件的路径的最大长度。
在第一个样例中，可以通过从城镇 1 沿道路 1 前往城镇 2，然后两次沿道路 2 从城镇 2 到自身，获得一条长度为 3 的路线。
在第二个样例中，可以先沿道路 1 行驶，然后根据所需类型选择道路 2 或 3，从而获得任意长的路线。
## Input
第一行包含两个整数 #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]。
## Output
如果存在长度严格大于 #cf_span[1018] 的路线，请输出 -1；否则，输出符合条件的路径的最大长度。
[samples]
## Note
在第一个样例中，可以通过从城镇 1 沿道路 1 前往城镇 2，然后两次沿道路 2 从城镇 2 到自身，获得一条长度为 3 的路线。
在第二个样例中，可以先沿道路 1 行驶，然后根据所需类型选择道路 2 或 3，从而获得任意长的路线。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of towns, $ m \in \mathbb{Z}_{\geq 0} $ the number of directed roads.
Let $ G = (V, E) $ be a directed multigraph with $ V = \{1, 2, \dots, n\} $.
Each edge $ e \in E $ is a triple $ (u, v, t) $, where $ u, v \in V $, $ t \in \{0,1\} $, denoting a directed road from $ u $ to $ v $ of type $ t $ (0: pedestrian, 1: bike).
Let $ S = (s_1, s_2, s_3, \dots) $ be the infinite sequence over $ \{0,1\} $ defined recursively:
- $ s_1 = 0 $
- $ s_{2k} = 1 - s_k $, $ s_{2k+1} = s_k $ for $ k \geq 1 $
This is the Thue-Morse sequence starting with 0.
**Constraints**
1. $ 1 \leq n \leq 500 $
2. $ 0 \leq m \leq 2n^2 $
3. For all distinct edges $ e_i = (u_i, v_i, t_i) $, $ e_j = (u_j, v_j, t_j) $, if $ u_i = u_j $ and $ v_i = v_j $, then $ t_i \ne t_j $.
4. The travel starts at town 1.
**Objective**
Find the maximum integer $ L $ such that there exists a walk $ v_0, v_1, \dots, v_L $ with $ v_0 = 1 $, and for each $ i \in \{1, \dots, L\} $, there exists an edge $ (v_{i-1}, v_i, s_i) \in E $.
If such an $ L $ exists with $ L > 10^{18} $, output $ -1 $.
Otherwise, output $ \max L $.
API Response (JSON)
{
"problem": {
"name": "D. Axel and Marston in Bitland",
"description": {
"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",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 5000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF781D"
},
"statements": [
{
"statement_type": "Markdown",
"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...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "两位朋友 Axel 和 Marston 正在 Bitland 国旅行。Bitland 有 #cf_span[n] 座城镇，某些城镇对之间由单向道路连接。Bitland 的每条道路要么是步行道，要么是自行车道。任意两座城镇之间可能存在多条道路，甚至可能存在从一座城镇到自身的道路。然而，没有任何两条道路同时具有相同的起点、终点和类型。\n\n现在，两位朋友位于城镇 1，并计划旅行路线。Axel 喜欢步行，...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**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,...",
"is_translate": false,
"language": "Formal"
}
]
}