题目描述

Alice 有一个大小为 $n$ 的集合 $\{1,2,3,\cdots,n\}$。她定义一个集合的分数为集合中所有元素的异或和。

Alice 特别喜欢两个值在 $1$ 到 $n$ 的整数 $u,v$，所以她想选出一个集合，包含这两个数，并且分数最大。

因为可能有很多集合满足条件，所以 Alice 希望以最省力的方式找到分数最大的集合，她要求你找到包含元素最少的集合。若有多个元素最少的集合，找到其中字典序最小的。集合的字典序定义为从小到大排序后排成一个序列的字典序。

Alice 喜欢的数会发生变化，所以她会问你 $q$ 次，每次给定的 $u,v$ 不同。

输入格式

第一行两个正整数 $n,q$。

接下来 $q$ 行，每行两个正整数 $u,v$。

输出格式

对于每个询问，输出两行，故共有 $2q$ 行输出。

第一行两个整数 $s,t$，用空格分隔。$s$ 表示最大分数，$t$ 表示字典序最小的分数为 $s$ 的集合含有的元素个数。

第二行共 $t$ 个递增的数，表示所求集合的元素。

5 3
1 2
1 3
2 4

7 3
1 2 4
7 3
1 3 5
7 3
1 2 4

数据范围

• 对于 $30\%$ 的数据：$n \le 20$。

• 对于另外 $30\%$ 的数据：存在正整数 $k$ 使得 $n = 2^k - 1$。

• 对于 $100\%$ 的数据：$n \le 10^5$。

• 对于所有数据，$2 \le n \le 10^5$，$1 \le q \le 20$，$1 \le u,v \le n$，$u \neq v$。