Given an undirected graph, print a path from vertex 0 to every other vertex in the graph. When there is more than one adjacent vertex that can be visited, prioritize the smaller-numbered vertex first.

For each vertex v (1 ≤ v < n):

• If there exists a path from vertex 0 to vertex v, print the vertices on that path.
• Vertices on the path must be separated by the character -.
• If vertex v is unreachable from vertex 0, print -1.

Input

• The first line consists of two positive integers, the number of vertices n (0 < n < 10^5) and the number of edges m (0 < m < 2 × 10^5).
• Then there are m lines, each containing two integers u and v (u, v < 10^5), representing an undirected edge connecting vertex u and vertex v.

Output

For each vertex v (1 ≤ v < n):

• Print one line containing a path from vertex 0 to vertex v.
• Consecutive vertices in the path must be separated by -.
• If no path exists, print -1.

Example Input

4 4
0 3
3 2
1 0
0 1

Example Output

0-1
0-1-3-2
0-1-3