问题描述

我们有一棵包含 $N$ 个顶点的树，编号为 $1, \ldots, N$。对于每个 $i=1,\\ldots,N-1$，第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$。 在对这棵树进行操作时，最多可以将每个顶点放置一个物体。操作的定义如下：

• 同时将每个物体移动到与其所占据的顶点相邻的顶点之一。

当满足以下条件时，我们称操作是好的：

• 每条边至多被一个物体占据。
• 每个顶点在操作完成后至多被一个物体占据。

高桥将在他选择的一个或多个顶点上放置物体。在 $2^N-1$ 种放置物体的方式中，找出满足以下条件的数量，并对 $998244353$ 取模。

• 对于每个非负整数 $K$，满足以下条件。
  • 可以执行 $K$ 次好操作。
  • 设 $S_K$ 是执行 $K$ 次好操作后物体所占据的顶点的集合。那么，$S_K$ 是唯一的。

约束条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq a_i < b_i \leq N$
• 给定的图是一棵树。
• 输入中的所有值都是整数。

输入和输出

这是一个交互式任务，你的程序通过输入和输出与评测系统进行交互。

首先，从标准输入中以以下格式读入输入：

$N$ $a_1$ $b_1$ $\vdots$ $a_{N-1}$ $b_{N-1}$

然后，你可以提出问题。
一个问题应该以以下格式打印出来（末尾带有换行符）：

? $u$ $v$

如果问题是有效的，从标准输入中给出响应 $d_{u,v}$：

$d_{u,v}$

如果问题被判定为无效，例如格式有误或者你提问次数过多，你将得到响应 -1 替代：

-1

此时，你的提交已被判定为错误。评测系统的程序随后终止；你的程序也应该尽快终止。

当你找到答案 $d_{1,2}$ 时，请以以下格式打印到标准输出（末尾带有换行符）：

! $d_{1,2}$

注意事项

• 在每次输出后使用 Flush Standard Output。否则，可能导致超时错误。