Problem Statement

P.P. has a phobia of palindromes and feels unpleasant whenever he sees one. This P.P. has become trapped in a connected undirected graph with $N$ vertices and $M$ edges, where each edge has a lowercase English letter as its label. P.P. is currently at vertex $1$, and it is known that the exit is at vertex $N$.

For P.P.'s sake, please find $1$ escape route such that the string formed by arranging the labels of the traversed edges in order is not a palindrome. You may pass through the same vertex or the same edge multiple times, but since it would be too cruel to P.P. if the route were excessively long, output one in which the total number of edge traversals is at most $2N$.

Input

$N$ $M$
$A_1\ \ B_1\ \ C_1$
$A_2\ \ B_2\ \ C_2$
    $\vdots$
$A_M\ \ B_M\ \ C_M$

• $2 \le N \le 10^5$
• $1 \le M \le 2 \times 10^5$
• $1 \le A_i, B_i \le N,\ A_i \neq B_i \ \ (1 \le i \le M)$
• $C_i \ (1 \le i \le M)$ is a lowercase English letter.
• All values in the input except $C_i$ $(1 \le i \le M)$ are integers.
• The given graph is a connected undirected graph.
• The vertices are numbered $1, 2, \dots, N$.
• The edges are numbered $1, 2, \dots, M$.
• Edge $i$ connects vertex $A_i$ and vertex $B_i$ bidirectionally.

Output

Output a route from vertex $1$ to vertex $N$ such that the string formed by arranging the labels of the traversed edges in order is not a palindrome and the total number of edge traversals is at most $2N$.

On line $1$, output the total number of edge traversals $k$, and on lines $2$ through $k + 1$, output the numbers of the traversed edges in order. However, if no route satisfying the conditions exists, output only $-1$ on line $1$.

Sample

3 3
1 2 a
2 3 a
1 3 b

3
1
1
3

4 4
1 2 a
1 2 b
2 3 a
3 4 b

3
1
3
4

2 1
1 2 a

-1