Without lifting the pencil from the paper
Recall the classic puzzle of drawing a picture without lifting your pencil from the paper, where each line is drawn only once. A well-known example from childhood is the open envelope.
To draw this envelope without lifting the pencil and without retracing any line, you might connect the numbered points in the sequence: 1 4 2 5 4 3 2 1 5.
Here's another example of a drawing that follows these rules:
You will be provided with a description of a drawing consisting of points and the lines connecting them. Your task is to determine if it's possible to draw this picture without lifting the pencil and without retracing any line. Note that if a point is isolated (not connected to any other point), you must lift the pencil to draw it.
Input
The first line of the input file contains two integers N and M, separated by a space. N is the number of points in the drawing (2 ≤ N ≤ 200), and M is the number of lines connecting them (0 ≤ M ≤ N·(N-1)/2). All points are numbered from 1 to N. Each line is defined by a pair of numbers representing the points it connects.
The next M lines describe the lines. Each line contains two natural numbers A and B, separated by a space (1 ≤ A, B ≤ N, A ≠ B). These numbers indicate the points connected by the line. No two points are connected by more than one line.
Output
If the drawing described in the input can be completed according to the rules, the output file should contain the sequence of point numbers, separated by spaces, that need to be connected to draw the picture.
If the drawing cannot be completed, output the single number -1.