Cho một đồ thị vô hướng gồm \(n\) đỉnh và \(m\) cạnh. Các đỉnh được đánh số từ \(1\) đến \(n\). Các cạnh được đánh số từ \(1\) đến \(m\). Cạnh thứ \(i\) nối hai đỉnh \(a_i\) và \(b_i\), trên cạnh này có ghi một kí tự \(c_i\).

Một ''đường đi'' trên đồ thị có thể được biểu diễn bởi dãy số \(v_0, e_1, v_1, e_2, v_2, \ldots, v_{k-1}, e_k, v_k\), trong đó với mọi \(1 \leq i \leq k\), ta luôn có:

• \(1 \leq v_{i-1}, v_i \leq n\),
• \(1 \leq e_i \leq m\),
• Cạnh thứ \(e_i\) có hai đỉnh kề là \(v_{i-1}\) và \(v_i\).

Khi đó, đường đi này xuất phát ở đỉnh \(v_0\) và kết thúc ở đỉnh \(v_k\). Chú ý rằng các đỉnh \(v_0, v_1, \ldots, v_k\) hay các cạnh \(e_1, e_2, \ldots, e_k\) không nhất thiết phải đôi một phân biệt. Nói cách khác, một đường đi có thể đi qua một đỉnh hay một cạnh nhiều hơn một lần. Do mỗi cạnh của đồ thị có chứa một kí tự, ta viết lần lượt các chữ cái có trên các cạnh theo thứ tự của đường đi, và tạo ra xâu kí tự \(S = c_{e_1} c_{e_2} \ldots c_{e_k}\). Xâu kí tự này được gọi là ''xâu biểu diễn'' đường đi.

Cho đồ thị ở trên, bạn cần tìm ra đường đi ngắn nhất (chứa ít cạnh nhất) từ đỉnh \(1\) tới đỉnh \(2\), sao cho xâu biểu diễn của đường đi này là một xâu đối xứng.

Nhắc lại, xâu đối xứng là xâu kí tự mà khi đọc ngược hay xuôi đều như nhau. Ví dụ, a, ahiha hay abba là các xâu đối xứng; nhưng na, ahihi hay huhu thì không.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((2 \leq n \leq 20, 2 \leq 2 \cdot m \leq n \cdot (n - 1))\) lần lượt là số đỉnh và số cạnh của đồ thị.

• Trong \(m\) dòng còn lại, dòng thứ \(i\) chứa hai số nguyên \(a_i\), \(b_i\) \((1 \leq a_i, b_i \leq n)\) và một chữ cái Lattin in thường \(c_i\) thể hiện cạnh thứ \(i\) của đồ thị.

Output

• In ra một số nguyên duy nhất là độ dài (tính theo số cạnh) của đường đi ngắn nhất từ đỉnh \(1\) đến đỉnh \(2\) có xâu biểu diễn là xâu đối xứng. Nếu không tồn tại đường đi như vậy, in ra \(-1\).

Example

5 5
3 1 a
3 2 b
1 4 x
4 5 y
5 2 x 

3

5 5
3 1 a
3 2 b
1 4 x
4 5 y
5 2 z 

-1