Axel and Marston in Bitland
Contest: Технокубок 2017 - Финал (только для онсайт-финалистов)
Difficulty rating: 2400
Tags: bitmasks, dp, graphs, matrices

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 $$s$$ is appended to s, where $$s$$ 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 format:
The first line contains two integers n and m (1 ≤ n ≤ 500, 0 ≤ m ≤ 2n2) — the number of towns and roads in Bitland respectively.

Next m lines describe the roads. i-th of these lines contains three integers vi, ui and ti (1 ≤ vi, ui ≤ n, 0 ≤ ti ≤ 1), where vi and ui denote start and destination towns indices of the i-th road, and ti 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 vi ≠ vj, or ui ≠ uj, or ti ≠ tj holds.

Output format:
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.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

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.

Example input:
2 2
1 2 0
2 2 1

Example output:
3

Example input:
2 3
1 2 0
2 2 1
2 2 0

Example output:
-1

Editorial:
Let us write Ai for the binary string obtained after i inverse-append steps, for example, A0 = 0, A1 = 01, and so on. Let us also write $$\overline{B_i} = \overline{A_i}$$. By definition we must have $$A_{i+1} = A_i B_i$$, and $$B_{i+1} = B_i A_i$$.
Let us store matrices Pk and Qk, with entries Pk / Qk(v, u) equal to 1 for pairs of vertices v, u such that there is a Ak/Bk-path from v to u. Note that P0 and Q0 are exactly the adjacency matrices with 0- and 1-arcs respectively.
Next, note that Pk + 1(v, u) = 1 if and only if there is a vertex w such that Pk(v, w) = Qk(w, u) = 1, and a similar condition can be written for Qk + 1(v, u). It follows that Pk + 1 and Qk + 1 can be computed using Pk and Qk in O(n3) time (the method is basically boolean matrix multiplication: $$P_{k+1} = P_k Q_k$$, $$Q_{k+1} = Q_k P_k$$).
To use the matrices Pk and Qk to find the answer, let us store L — the largest answer found, and S — the set of vertices reachable from the vertex 1 in exactly L steps. Let's process k by decreasing from a certain value k0, and see if L can be increased by 2k. The next 2k characters after L-th position will form the string Ak or Bk depending on the popcount parity of L. Let's denote S' the set of vertices reachable from S following Ak / Bk. If S' is non-empty, we can increase L by 2k, and assign S = S', otherwise, we don't change anything. In the end, L will be the maximal path length as long as it at less than 2k0.
Note that we can take k0 = 60 since we don't care about exact value of answer if it is greater than 260. This results in an O(k0n3) solution, which is too slow. However, optimizing boolean multiplication with bitsets cuts the working time $$\sim 64$$ times, and the solution is now fast enough.
Complexity: $${\cal O}(k\alpha n^{3}/w)$$ time, and $${\mathcal O}(k_{0}n^{2})$$ memory. Here $$k_{0}=\log_{2}10^{18}$$, and w = 64 is the word length in bits.