Given a directed graph, print a path from vertex 0 to every other vertex. When there is more than one vertex that can be visited next, prioritize visiting the smaller vertex first.

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

• If there exists a path from vertex 0 to v, print one such path.
• If multiple paths exist, print the path determined by the traversal order.
• 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 a directed edge from u to v.

Output

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

• Print one line containing a path from vertex 0 to vertex v.
• Vertices on 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