El burro de ajedrez P66799

Tenemos una nueva ficha de ajedrez, semejante al caballo, pero que hace saltos extrañísimos: la llamamos “el burro”. En concreto, un burro puede hacer $k$ tipos de saltos distintos $(x_1, y_1), \ldots, (x_k, y_k)$, donde un salto de tipo $(x_i, y_i)$ indica que el burro puede desplazarse $x_i$ columnas a la derecha, y $y_i$ filas hacia arriba. Los valores $x_i$ o $y_i$ pueden ser negativos. Por ejemplo, un burro se movería igual que un caballo de ajedrez si tuviera $k=8$ saltos de tipos $$(2,1), (1,2), (-1,2), (-2,1), (-2,-1), (-1,-2), (1,-2), (2,-1)$$ Los movimientos del burro no tienen porque ser simétricos. Por ejemplo, si los saltos del burro fueran $$(-2,1), (-1,2), (1,2), (2,1)$$ nuestra ficha sería un caballo que únicamente puede desplazarse hacia arriba (no podría retroceder).

Se te pide que escribas un programa que obtenga una secuencia de movimientos que permita desplazarse a un burro desde la casilla $(o_x, o_y)$ de un tablero $n\times n$ hasta la casilla $(f_x, f_y)$ (donde $1\leq o_x, f_x\leq n$ representa una columna, de izquierda a derecha, y $1\leq o_y, f_y\leq n$ representa una fila, de abajo a arriba). En concreto, se pide que retornes el mínimo número de movimientos necesarios, y la secuencia de movimientos con ese número mínimo que sea lexicográficamente menor, según los índices de los movimientos (es decir: que a la hora de escoger entre varios movimientos, que tenga preferencia el escoger un tipo de salto $(x_i, y_i)$ con la mínima $i$ posible).

Entrada

Un juego de pruebas está formado por un nombre indeterminado de casos. Cada caso empieza con una línea con los números $n$ (tamaño del tablero) y $k$ (número de tipos de saltos del burro). A continuación, $k$ líneas con los valores $x_i, y_i$ del tipo de salto $i$-ésimo del burro, para $1\leq i \leq k$. Finalmente, una línea con los valores $o_x, o_y, f_x$ y $f_y$, separados por espacios. Entre dos casos se dejará una línea en blanco.

Salida

Para cada caso, escribe la secuencia de movimientos buscada. En concreto, escribe todas las casillas que ocupa el burro, y los índices de los saltos que realiza (sigue el formato de los ejemplos, donde S$i$ indica que el burro realiza un salto de tipo $i$). Si no hubiera ninguna secuencia válida, escribe una línea con tres guiones (---). Escribe dos líneas en blanco después de cada uno de los casos (¡incluyendo el último!).

Pista

Haz un recorrido en anchura, escogiendo el orden correcto y recordando cómo has llegado a cada casilla del tablero.