서커스

주쿠는 보드게임을 그다지 잘하지 못한다. 그래서 다음 게임 모임 전에 혼자 '서커스'를 연습하기로 했다.

'서커스'는 간단한 보드게임이다. 게임판에는 1번부터 $N$번까지 번호가 매겨진 $N$개의 칸이 있다. 모든 플레이어의 말은 1번 칸에서 출발한다. 자기 차례에 플레이어는 6면체 주사위를 굴리고, 나온 눈(1부터 6까지)만큼 말을 앞으로 옮긴다. 일부 칸에는 뱀이나 사다리가 시작된다. 뱀은 말을 뒤로 보내고, 사다리는 말을 앞으로 보낸다. 말이 뱀이 시작되는 칸에 멈추면, 말을 뱀의 반대쪽 끝으로 옮겨야 한다. 마찬가지로 말이 사다리가 시작되는 칸에 멈추면, 말을 사다리의 반대쪽 끝으로 옮겨야 한다. 말이 $N$번 칸에 도달하거나 그보다 멀리 가면 플레이어가 이긴다.

주쿠는 앞으로 얼마나 더 발전할 여지가 있는지 알고 싶어 한다. 그래서 게임에서 이기는 데 필요한 주사위 던지기 횟수의 최솟값을 구하려 한다.

첫 줄에는 칸의 수 $N$과 뱀과 사다리의 총 개수 $M$이 주어진다($2 \le N \le 10^5$, $0 \le M$). 다음 $M$개의 줄에는 각각 뱀 또는 사다리를 나타내는 두 정수 $A$와 $L$이 주어진다($1 < A < N$, $1 \le L \le N$, $A \neq L$).

• $A < L$이면 그 줄은 $A$번 칸에서 시작해 $L$번 칸으로 이어지는 사다리이다.
• $A > L$이면 그 줄은 $A$번 칸에서 시작해 $L$번 칸으로 이어지는 뱀이다.

모든 줄에서 $A$의 값은 서로 다르다. 또한 어떤 $L$의 값도 어떤 $A$의 값과 같지 않다.

첫 줄에는 게임에서 이기기 위해 필요한 주사위 던지기 횟수의 최솟값을 출력한다. 둘째 줄에는 주사위 결과를 빈칸으로 구분하여 순서대로 출력한다. 가능한 결과 수열이 여러 개이면 그중 아무거나 출력해도 된다. 게임에서 이길 수 없으면 한 줄에 \verb'EI SAA'만 출력한다.