E - Colorful Route Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

N 個の都市と M 本の一方通行の道路があります。i 本目の道路は都市 U_i から都市 V_i へ通じ、色 C_i で塗られています。

あなたは、道路を通ることを繰り返して都市 1 から都市 N まで移動したいです。ただし、同じ色で塗られた道路を 2 回続けて通ってはいけません。

都市 1 から都市 N に辿り着くことができるか判定し、辿り着くことができる場合は道路を通る回数として考えられる最小値を求めてください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i
  • 1 \leq C_i \leq M
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
U_1 V_1 C_1
U_2 V_2 C_2
\vdots
U_M V_M C_M

出力

都市 1 から都市 N に辿り着くことができない場合は -1 と出力せよ。そうでない場合は、道路を通る回数として考えられる最小値を出力せよ。


入力例 1

6 10
1 2 1
2 4 2
2 5 2
3 6 5
4 3 3
5 2 3
5 3 2
5 6 2
6 1 3
6 5 3

出力例 1

4

i 本目の道路を道路 i と表記すると、道路 1, 2, 5, 4 の順で道路を通ることで都市 6 に辿り着くことができます。


入力例 2

3 5
1 2 1
1 2 1
1 2 2
1 2 2
1 2 3

出力例 2

-1

入力例 3

8 10
1 2 1
2 3 2
2 4 1
3 2 3
4 5 2
4 6 1
5 4 3
6 7 2
6 8 1
7 6 3

出力例 3

10

Score : 450 points

Problem Statement

There are N cities and M one-way roads. The i-th road leads from city U_i to city V_i and is painted in color C_i.

You want to travel from city 1 to city N by repeatedly traversing roads. However, you must not traverse roads painted in the same color twice in a row.

Determine whether it is possible to reach city N from city 1, and if it is possible, find the minimum possible number of times you traverse a road.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i
  • 1 \leq C_i \leq M
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
U_1 V_1 C_1
U_2 V_2 C_2
\vdots
U_M V_M C_M

Output

If it is impossible to reach city N from city 1, print -1. Otherwise, print the minimum possible number of times you traverse a road.


Sample Input 1

6 10
1 2 1
2 4 2
2 5 2
3 6 5
4 3 3
5 2 3
5 3 2
5 6 2
6 1 3
6 5 3

Sample Output 1

4

Let road i denote the i-th road. You can reach city 6 by traversing roads 1, 2, 5, 4 in this order.


Sample Input 2

3 5
1 2 1
1 2 1
1 2 2
1 2 2
1 2 3

Sample Output 2

-1

Sample Input 3

8 10
1 2 1
2 3 2
2 4 1
3 2 3
4 5 2
4 6 1
5 4 3
6 7 2
6 8 1
7 6 3

Sample Output 3

10