Alice, Bob and Play Game
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

牛牛的英文名叫,牛妹的英文名叫故事从下面展开:

黑板上有个整数,初始时
进行轮游戏,第轮游戏流程如下:
选择两个不同的整数,并令
做以下操作之一:
0.令
1.令

为进行了轮游戏后的值。
令序列
想让的字典序尽可能的小,想让的字典序尽可能的大。

很快意识到这是一个不公平的游戏,因为只要足够聪明,一定会有。于是启用了时之魔法,预测了在每轮会选择的整数对。

但是很快又意识到,只要足够聪明,的操作策略会根据操作的策略发生改变,仍然会有。这将可能导致每轮选择的整数对和预测的整数对不一样。而的预测是不可以失效的,因为一旦的预测失效,时空将会发生扭曲,这会造成非常严重的后果。因此,又使用了馄饨赤光魔法使得在进行轮游戏时智商下降。

确切地说,知道在第轮游戏一定会选择整数对

且Bob需要保证如下条件
在第轮游戏结束后,满足

想知道在他保证条件的基础上字典序最大的序列是什么样子,此外,他还想知道他的操作序列。

输入描述:

第一行两个整数
接下来行每行两个整数

输出描述:

第一行个整数
第二行一个长度为表示轮游戏进行的操作。
有多种合法的操作序列只需要输出任意一种即可。
示例1

输入

复制
6 5
1 2
3 4
2 3
2 5
1 6

输出

复制
5 4 4 4 4
00100

备注: