Circus

Juku is not very good at board games. So before the next game night, he decided to practice playing Circus alone.

Circus is a simple board game. The board has $N$ squares, numbered 1 to $N$. Every player's piece starts on square 1. On a turn, a player rolls a six-sided die and moves the piece forward by the number of pips shown (1 to 6). Some squares have a snake or a ladder starting on them. Snakes move a piece back, and ladders move it forward. If a piece stops on a square where a snake starts, the piece must be moved to the other end of the snake. Likewise, if a piece stops on a square where a ladder starts, the piece must be moved to the other end of the ladder. A player wins when the piece reaches square $N$ or goes past it.

Juku wants to know how much room he still has to improve, so he asks for the minimum number of die rolls needed to win the game.

The first line contains the number of squares $N$ and the total number of snakes and ladders $M$ ($2 \le N \le 10^5$, $0 \le M$). Each of the next $M$ lines describes either a ladder or a snake with two integers $A$ and $L$ ($1 < A < N$, $1 \le L \le N$, $A \neq L$):

• If $A < L$, the line describes a ladder that starts on square $A$ and leads to square $L$.
• If $A > L$, the line describes a snake that starts on square $A$ and leads to square $L$.

It is guaranteed that all values of $A$ are pairwise distinct across all lines, and that no value of $L$ coincides with any value of $A$.

On the first line, print the minimum number of die rolls needed to win. On the second line, print the sequence of die results separated by spaces. If several sequences are possible, print any of them. If the game cannot be won, print the single line \verb'EI SAA'.