题目描述

本题是交互题。

你会得到一棵树，树根固定为 $1$ 号点。交互器在这棵树中选定了一个隐藏节点 $x$，你需要把它找出来。

你可以向交互器提出两种问题：

• d u：交互器返回节点 $u$ 到隐藏节点 $x$ 的距离；
• s u：交互器返回从节点 $u$ 出发走向 $x$ 时，路径上的下一个节点。

第二类询问有限制：只有当 $u$ 是 $x$ 的真祖先时，才允许询问 s u。这里的祖先关系以 $1$ 号点为根，并且一个节点不被认为是自己的祖先。

你必须在 $36$ 次询问以内输出隐藏节点。

输入格式

交互开始时，交互器先输出树的点数 $n$，随后输出 $n-1$ 条边。

在本地测试中，交互器使用隐藏输入文件保存树和答案。隐藏输入格式为：

第一行两个整数 $n,x$，其中 $x$ 是隐藏节点。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示树上的一条无向边。

输出格式

如果要询问距离，输出：

d u

交互器会返回 $u$ 到隐藏节点 $x$ 的距离。

如果要询问路径方向，输出：

s u

此时必须保证 $u$ 是 $x$ 的真祖先。交互器会返回从 $u$ 到 $x$ 的路径上的第二个节点。

每次询问后都要刷新输出并读入交互器的回答。

若已经确定隐藏节点，输出：

! x

然后刷新输出并结束程序。

如果交互器返回 $-1$，说明询问非法或询问次数超限，应立即结束程序。

样例

5
1 2
1 3
3 4
3 5
3
5

d 2
s 3
! 5

样例说明

样例中，隐藏节点是 $5$。

询问 d 2 时，节点 $2$ 到节点 $5$ 的距离为 $3$。之后询问 s 3，因为 $3$ 是 $5$ 的真祖先，所以交互器返回从 $3$ 走向 $5$ 的下一点，也就是 $5$。于是最终可以输出答案 $5$。

数据范围

$2\le n\le 2\times 10^5$。

$1\le x\le n$。

输入边保证构成一棵树。

询问总数不超过 $36$。