1158 - 神父过河

通过次数

0

提交次数

2

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

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

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

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

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

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

输入

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

输出

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

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

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

字典序的比较流程:

(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\% 的数据共 6 组,n38n=m;

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

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