Description

有 $m$ 根柱子，第一根柱子上从上到下从小到大放了 $n$ 个大小不同的圆盘，第 $i$ 个圆盘的大小为 $i$，其他柱子上没有圆盘。

你每步可以把一个柱子最顶上的圆盘移动到另一个柱子最顶上，但是大的圆盘不能放在小的圆盘上面。

你要使用尽量少的步数，将所有圆盘移动到第二个柱子上。

Format

Input

一行两个正整数表示 $n,m\,(1\leq n\leq 20,3\leq m\leq 20)$.

Output

第一行输出一个正整数 $k$ 表示你的操作步数。

随后 $k$ 行，每行两个正整数 $a,b$ 表示把第 $a$ 个柱子最上面的圆盘放在第 $b$ 个柱子上。

Samples

3 3

7
1 2
1 3
2 3
1 2
3 1
3 2
1 2

Limitation

1s, 256MiB.