<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

226. Colored graph
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard
output: standard



You are given an oriented graph. Each edge of the graph is colored in one of the three colors. Your task is to find the length of the shortest path from the first vertex to the N-th. Note that any two successive edges in the path can't have the same color.

Input
The first line of the input file consists of two integers N and M (2 <= N <= 200; 0 <= M <= N*N). Next M lines contain descriptions of the edges. Each edge description is a list of three integers X, Y, C (1 <= X, Y <= N, 1 <= C <= 3), where X is the starting vertex of the edge, Y is the finishing vertex and C is the color of the edge.

Output
Output the length of the shortest path between the first and the N-th vertexes. Output "-1" if the path doesn't exist.

Sample test(s)

Input

Test #1
4 4
1 2 1
2 3 2
3 4 3
2 4 1

Test #2
3 2
1 2 1
2 3 1

Output

Test #1
3

Test #2
-1
Author:	---
Resource:	---
Date:	---

<|response|>
1. Abridged problem statement  
You are given a directed graph with N vertices (numbered 1…N) and M edges. Each edge has one of three colors (1, 2 or 3). Find the minimum number of edges in a path from vertex 1 to vertex N under the constraint that no two consecutive edges in the path share the same color. If no such path exists, output –1.

2. Key observations  
- A standard shortest‐path algorithm that only tracks “which vertex” you’re at is insufficient, because legality of the next move depends on the color of the edge you just used.  
- To enforce “no two consecutive edges of the same color,” we must remember, as part of our state, the color of the last edge taken.  
- There are only three colors, so we can expand each vertex into three “colored” states.  
- Performing a breadth‐first search (BFS) over this expanded state space yields an optimal (shortest) path in O(N + M) time (more precisely O(3N + 3M)).

3. Full solution approach  
(a) State definition  
   Let dist[u][c] = the minimum number of edges needed to reach vertex u if the last edge used had color c (where c∈{1,2,3}).  

(b) Initial states  
   At the start we are at vertex 1 and have not yet taken any edge. We can model this by “pretending” we arrived at vertex 1 via an edge of each possible color, all with distance 0:  
     dist[1][1] = dist[1][2] = dist[1][3] = 0.  
   Enqueue the three start‐states (1,1), (1,2), (1,3).  

(c) BFS transitions  
   While the queue is not empty, pop state (u, last_color).  
   For each outgoing edge e = (u → v) of color col:  
     if col ≠ last_color and dist[v][col] > dist[u][last_color] + 1, then  
       dist[v][col] = dist[u][last_color] + 1  
       enqueue (v, col).  

(d) Answer extraction  
   After the BFS finishes, examine dist[N][1], dist[N][2], dist[N][3]. Let ans = minimum of these three values.  
   If ans is still “infinite” (unreached), print –1; otherwise print ans.  

Time complexity: O(3N + 3M) ≈ O(N + M), which easily fits for N≤200, M≤N² under 0.25 s.

4. C++ implementation with detailed comments  
```cpp
#include <bits/stdc++.h>
using namespace std;

static const int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    // Build adjacency list: adj[u] = list of (v, color)
    // We'll store colors as 0,1,2 internally.
    vector<vector<pair<int,int>>> adj(N);
    for (int i = 0; i < M; i++) {
        int X, Y, C;
        cin >> X >> Y >> C;
        X--; Y--; C--;  // zero‐based indexing
        adj[X].emplace_back(Y, C);
    }

    // dist[u][c] = shortest path length to reach u
    //              when the last edge used had color c
    vector<array<int,3>> dist(N);
    for (int u = 0; u < N; u++) {
        dist[u].fill(INF);
    }

    // Initialize start at vertex 0 (originally 1)
    // “Pretend” we arrived via each color with cost 0
    queue<pair<int,int>> q;
    for (int c = 0; c < 3; c++) {
        dist[0][c] = 0;
        q.emplace(0, c);
    }

    // BFS over (vertex, last_color) states
    while (!q.empty()) {
        auto [u, last_col] = q.front();
        q.pop();
        int d = dist[u][last_col];
        // Try every outgoing edge
        for (auto &edge : adj[u]) {
            int v = edge.first;
            int edge_col = edge.second;
            // Enforce different‐color constraint
            if (edge_col != last_col && dist[v][edge_col] > d + 1) {
                dist[v][edge_col] = d + 1;
                q.emplace(v, edge_col);
            }
        }
    }

    // Compute answer for vertex N-1 over all possible last colors
    int answer = min({ dist[N-1][0], dist[N-1][1], dist[N-1][2] });
    if (answer == INF) answer = -1;
    cout << answer << "\n";
    return 0;
}
```

5. Python implementation with detailed comments  
```python
from collections import deque
import sys

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    N = int(next(it))
    M = int(next(it))

    # Build adjacency list: adj[u] = list of (v, color)
    # Store colors as 0,1,2 internally.
    adj = [[] for _ in range(N)]
    for _ in range(M):
        u = int(next(it)) - 1
        v = int(next(it)) - 1
        c = int(next(it)) - 1
        adj[u].append((v, c))

    INF = 10**9
    # dist[u][c] = min edges to reach u if last edge had color c
    dist = [[INF]*3 for _ in range(N)]

    # Initialize BFS queue with the three start states at vertex 0
    q = deque()
    for c in range(3):
        dist[0][c] = 0
        q.append((0, c))

    # BFS over state space
    while q:
        u, last_col = q.popleft()
        d = dist[u][last_col]
        for v, edge_col in adj[u]:
            # we may take this edge only if its color differs
            if edge_col != last_col and dist[v][edge_col] > d + 1:
                dist[v][edge_col] = d + 1
                q.append((v, edge_col))

    # Answer is the best among the three colors at vertex N-1
    ans = min(dist[N-1])
    print(ans if ans < INF else -1)

if __name__ == "__main__":
    main()
```