Xoracle

题目背景

在 Xordic 诸国的中心，有一片古老森林。森林中隐藏着一棵树，你看不到边，也看不到每个点的度数。

神谕者 Xoracle 只会回答一种问题：给定两个点 $u,v$，回答这两个点度数的按位异或值。

你的任务是通过有限次询问，确定整棵树所有点的度数多重集。

题目描述

这是一道交互题。

有一棵包含 $N$ 个点、$N-1$ 条边的无向连通树，点编号为 $1$ 到 $N$。设点 $i$ 的度数为 $\deg(i)$。

你可以询问：

? u v

交互器会返回：

其中 $\oplus$ 表示按位异或。

你最多可以询问 $Q$ 次。

最后你需要输出：

! d_1 d_2 \cdots d_N

其中 $d_1,d_2,\ldots,d_N$ 应当是这棵树所有点的度数。注意：你只需要输出度数的多重集，顺序任意。

交互格式

程序开始时，从标准输入读入两个整数：

N Q

表示隐藏树的点数和最多允许询问次数。

每次询问时，输出：

? u v

其中 $1 \le u,v \le N$。随后你需要刷新输出缓冲区，并从标准输入读入一个整数，表示 $\deg(u) \oplus \deg(v)$。

当你确定答案后，输出：

! d_1 d_2 \cdots d_N

然后立即结束程序。

在 C++ 中，使用 endl 可以同时输出换行并刷新缓冲区；也可以使用 cout.flush() 手动刷新。

样例交互

若隐藏树为一棵星形树，边为：

1-2, 1-3, 1-4

则点的度数分别为：

3, 1, 1, 1

一种合法交互过程如下：

输入：
4 3

输出：
? 2 4

输入：
0

输出：
? 4 1

输入：
2

输出：
? 3 3

输入：
0

输出：
! 1 3 1 1

因为只要求输出度数多重集，所以 ! 3 1 1 1、! 1 1 1 3 等也都是正确的。

数据范围

对于所有测试点：

• $2 \le N \le 10^5$；
• 隐藏图是一棵树；
• $Q \le 10^5$；
• 测试数据保证：无论选手如何询问，都存在唯一的度数多重集与所有回答一致。

子任务

提示

可以固定一个点，例如点 $1$，询问它与其他所有点的度数异或值。设得到的值为 $\deg(1) \oplus \deg(i)$。再利用树的度数和恒等式：

以及题目保证的唯一性，可以恢复整棵树的度数多重集。