{"problem":{"name":"F. 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":"CF782F"},"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 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.\n\n## Input\n\nThe 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.\n\n## Output\n\nIf it is possible to find a route with length strictly greater than 1018, print -1. Otherwise, print the maximum length of a suitable path.\n\n[samples]\n\n## Note\n\nIn 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.","is_translate":false,"language":"English"}],"meta":{"iden":"CF782F","tags":["matrices"],"sample_group":[["2 2\n1 2 0\n2 2 1","3"],["2 3\n1 2 0\n2 2 1\n2 2 0","\\-1"]],"created_at":"2026-03-03 11:00:39"}}