Permutaciones feas P80445

En este problema, decimos que una permutación es $k$-fea si tiene exactamente $k$ pares de posiciones adyacentes con dos números consecutivos. Dada una $n$, una $k$ y $m$ posiciones para las cuales ya se ha fijado el contenido, escribid todas las permutaciones $k$-feas de $\{0, \dots, n - 1\}$ con el contenido fijado.

Entrada

La entrada consiste en diversos casos, cada uno con una $n$ entre 1 y 10, seguida de una $k$ entre 0 y $n - 1$, seguida de una $m$ entre 0 y $n$, seguida de $m$ pares $i$ $x$, indicando que en la posición $i$ tiene que haber una $x$. Suponed $0 \le y < n$, $0 \le x < n$, que todas las $i$ son diferentes, y que todas las $x$ son diferentes.

Salida

Para cada caso, escribid todas las permutaciones $k$-feas de $\{0, \dots, n - 1\}$ con las posiciones fijadas, en orden lexicográfico. Escribid una línia con 20 asteriscos al final de cada caso.