Un edificio tiene \(2N\) pisos, numerados de \(1\) a \(2N\). Hay \(M\) códigos de ascensor; cada uno permite subir del piso \(S\) al piso \(T\) \((S < T)\). Los pisos están agrupados en \(N\) pares: el sensor \(i\) \((1 \le i \le N)\) vigila los pisos \(i\) e \(i + N\).

Una ruta es una secuencia de pisos \(f_1, f_2, \dots, f_k\) tal que:

• \(f_1 = 1\) y \(f_k = 2N\);
• para cada \(1 \le i < k\) existe un código que lleva de \(f_i\) a \(f_{i+1}\);
• no hay dos pisos de la ruta vigilados por el mismo sensor.

Encuentra una ruta o indica que no existe.

Entrada

La primera línea tiene dos enteros \(N\) \((1 \le N \le 500)\) y \(M\) \((1 \le M \le 1000)\).

Cada una de las siguientes \(M\) líneas tiene dos enteros \(S\) y \(T\) \((1 \le S < T \le 2N)\): un código para subir de \(S\) a \(T\).

Salida

Si existe una ruta, imprime dos líneas: la primera con \(k\) y la segunda con \(f_1, f_2, \dots, f_k\). Si hay varias, cualquiera es aceptada. Si no existe, imprime una línea con el carácter *.

Ejemplo 1

Entrada

1 1
1 2

Salida

*

Ejemplo 2

Entrada

4 9
1 2
2 3
3 6
6 7
7 8
1 3
3 7
2 6
6 8

Salida

4
1 3 6 8

Ejemplo 3

Entrada

4 8
1 2
1 3
2 3
2 6
3 7
6 7
6 8
7 8

Salida

*

Regional Latinoamericana 2025 del ICPC, problema I («Infiltration Route»). Versión en español redactada para este juez; el enunciado oficial, en inglés, está aquí abajo.