问题 C: Wordle游戏Ⅰ

问题 C: Wordle游戏Ⅰ

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

Wordle游戏是一款风靡全球的益智游戏,在一场Wordle游戏中,你共有6次机会来猜出一个完全随机的单词,这个单词的长度和游戏的级别相关,让我们以一场级别5的Worlde游戏为例:


在第一轮中,我们尝试了单词 power,其中:

① 字母 p,o,r 的提示为灰色,表示这三个字母不会出现在答案中;

② 字母 w,e 的提示为黄色,表示这两个字母会出现在答案中,但是不在当前的位置上;也就是说在答案中,字母 w 不会在位置 3 上出现,字母 e 不会在位置 4 上出现;


在第二轮中,我们尝试了单词 twine,其中:

① 字母 t 的提示为灰色,表示字母 t 不会出现在答案中;

② 字母 w,i,n的提示为黄色,表示这三个字母会出现在答案中,但是不在当前的位置上;也就是说在答案中,字母 w 不会在 位置 2 上出现,字母 i 不会在位置 3 上出现,字母 n 不会在位置 4 上出现;

③ 字母 e 的提示为绿色,表示字母 e 目前的摆放位置正确;也就是说答案的第 5 个字母是字母 e;


到目前为止,我们获取了如下信息:

① 字母 r,t,o,p 不会出现在答案中;

② 答案中包含字母 w,且不会出现在第 2 个位置或第 3 个位置上;

③ 答案中包含字母 i,且不会出现在第 3 个位置上;

④ 答案中包含字母 n,且不会出现在第 4 个位置上;

⑤ 答案的第 5 个字母一定是字母 e ;


让我们用下划线来表示不能确定的字母,那么答案只有可能是以下 7 个排列中的一个:

win_e
wn_ie
w_nie

in_we
i_nwe
ni_we
_inwe



我们现在适当简化一下这个游戏:设游戏的级别为n,且在游戏进行了若干轮之后,我们已经知道了组成答案的全部n个字母(分别标号为1~n)只是不知道它们各自的位置;并且我们知道了一些提示:某些位置上绝对不可能出现某些字母;能否请你编写一份代码,按照字典序输出满足这些条件的、所有可能的字母排列,帮助我们完成填字游戏?

输入

输入第一行包含两个正整数n和k,分别表示单词的长度和表示限制的数量;
接下来k行,每行两个整数x,y,表示数字x绝对不可能出现在第i个位置上;

输出

输出包含多行,表示所有满足限制条件的排列;
每行包含n个整数,表示一个排列,数字中间用空格隔开;

样例输入

3 3
1 1
2 1
1 2

样例输出

3 2 1

提示

对于输入样例,3个字母的全排列共6种,但满足条件的排列只有一个:

1 2 3  × 不满足限制①

1 3 2  × 不满足限制①

2 3 1  × 不满足限制②

2 1 3  × 不满足限制②③

3 1 2  × 不满足限制③

3 2 1  √

对于100%的数据,保证 2 <= n <= 10; 0 <= k <= 50;

[提交][状态]