1158 - 神父过河

通过次数

0

提交次数

2

时间限制 : 1 秒
内存限制 : 128 MB

nn 个神父和 nn 个恶魔一同来到了河岸,他们现在要过河。

他们可以通过一个容量为 mm 的船过去。

在渡河过程中,在河岸和船上,神父的数量都不能小于恶魔的数量,否则会被吃掉。

船不会自己划,因此最少需要一个神父或者一个恶魔去划船。

请你设计一个渡河流程,使得 nn 个神父和 nn 个恶魔都能过河。

输入

第一行两个整数 nnmm,含义如题目描述。

输出

第一行输出最少的步数 tt,如果不行,输出 1-1.

接下来 tt 行,每行表示哪些去划船。如果有多少方案,由于河流湍急,输出乘船数交多的。

如果还有多少种方案,输出神父较多的。可以认为,如果有多种方案,输出字典序最大的。

字典序的比较流程:

(1)数量多的优先

(2)神父的数量多的优先

具体输出方式,见样例。

样例

输入
复制

3 2

输出
复制

11
1 father and 1 devil.
1 father.
2 devils.
1 devil.
2 fathers.
1 father and 1 devil.
2 fathers.
1 devil.
2 devils.
1 father.
1 father and 1 devil.

提示

注意单复数。

对于 30%30\% 的数据共 66 组,nn3388n=mn=m;

对于 70%70\% 的数据,nn 的范围 [2,50][2,50];

对于 100%100\% 的数据,nn 的范围 [2,100],mn[2,100],m≤n;