Problem: This is an interactive problem.

You're given a tree consisting of n nodes, rooted at node 1. A tree is a connected graph with no cycles.

We chose a hidden node x. In order to find this node, you can ask queries of two types: 

  * d u (1 ≤ u ≤ n). We will answer with the distance between nodes u and x. The distance between two nodes is the number of edges in the shortest path between them. 
  * s u (1 ≤ u ≤ n). We will answer with the second node on the path from u to x. However, there's a plot twist. If u is not an ancestor of x, you'll receive "Wrong answer" verdict! 



Node a is called an ancestor of node b if a ≠ b and the shortest path from node 1 to node b passes through node a. Note that in this problem a node is not an ancestor of itself.

Can you find x in no more than 36 queries? The hidden node is fixed in each test beforehand and does not depend on your queries.

Input

The first line contains the integer n (2 ≤ n ≤ 2 ⋅ 10^5) — the number of nodes in the tree.

Each of the next n-1 lines contains two space-separated integers u and v (1 ≤ u,v ≤ n) that mean there's an edge between nodes u and v. It's guaranteed that the given graph is a tree.

Output

To print the answer, print "! x" (without quotes).

Interaction

To ask a question, print it in one of the formats above: 

  * d u (1 ≤ u ≤ n), or 
  * s u (1 ≤ u ≤ n). 



After each question, you should read the answer: either the distance or the second vertex on the path, as mentioned in the legend. 

If we answer with -1 instead of a valid answer, that means you exceeded the number of queries, made an invalid query, or violated the condition in the second type of queries. Exit immediately after receiving -1 and you will see Wrong answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After printing a query, do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  * fflush(stdout) or cout.flush() in C++;
  * System.out.flush() in Java;
  * flush(output) in Pascal;
  * stdout.flush() in Python;
  * See the documentation for other languages.



Hacks:

The first line should contain two integers n and x (2 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ x ≤ n).

Each of the next n-1 lines should contain two integers u and v (1 ≤ u,v ≤ n) that mean there is an edge between nodes u and v. The edges must form a tree.

Example

Input


5
1 2
1 3
3 4
3 5
3
5

Output


d 2
s 3
! 5

Note

In the first example, the hidden node is node 5.

<image>

We first ask about the distance between node x and node 2. The answer is 3, so node x is either 4 or 5. We then ask about the second node in the path from node 3 to node x. Note here that node 3 is an ancestor of node 5. We receive node 5 as the answer. Finally, we report that the hidden node is node 5.

Solution (in PYTHON):

Solution:
from sys import stdin, stdout
from itertools import repeat
memo = {}
def Qd(x):
    if x in memo:
        return memo[x]
    print 'd', x
    stdout.flush()
    res = int(stdin.readline())
    if res == -1:
        quit()
    memo[x] = res
    return res
def Qs(x):
    print 's', x
    stdout.flush()
    res = int(stdin.readline())
    if res == -1:
        quit()
    return res
def A(x):
    print '!', x
    quit()

def main():
    n = int(stdin.readline())
    dat = [stdin.readline().split() for i in xrange(n - 1)]
    dat = [x for l in dat for x in l]
    dat = map(int, dat, repeat(10, 2 * n - 2))
    la = [None] * (n + 1)
    xt = [0] * (2 * n - 2)
    j = 0
    for i in xrange(n - 1):
        x, y = dat[i*2], dat[i*2+1]
        xt[j] = la[y]
        la[y] = j
        j += 1
        xt[j] = la[x]
        la[x] = j
        j += 1
    st = [1]
    pu = st.append
    po = st.pop
    par = [-1] * (n + 1)
    dep = [0] * (n + 1)
    col = [0] * (n + 1)
    col[1] = 1
    while st:
        x = po()
        y = la[x]
        while y is not None:
            v = dat[y]
            if not col[v]:
                par[v] = x
                dep[v] = dep[x] + 1
                col[v] = 1
                pu(v)
            y = xt[y]
    bad = [0] * (n + 1)
    ch = [0] * (n + 1)
    root = 1
    for i in xrange(2, 50):
        if n == 1:
            A(root)
        if n <= 2:
            y = Qd(root)
            if y:
                y = la[root]
                while y is not None:
                    v = dat[y]
                    if not bad[v] and dep[v] > dep[x]:
                        A(v)
                    y = xt[y]
            else:
                A(root)
        h = n / 2
        g = []
        pu(root)
        while st:
            x = po()
            y = la[x]
            if col[x] < i:
                col[x] = i
                pu(x)
                while y is not None:
                    v = dat[y]
                    if not bad[v] and col[v] < i:
                        pu(v)
                    y = xt[y]
            else:
                ch[x] = 1
                f = 1
                while y is not None:
                    v = dat[y]
                    if not bad[v] and dep[v] > dep[x]:
                        ch[x] += ch[v]
                        if ch[v] > h:
                            f = 0
                    y = xt[y]
                if n - ch[x] > h:
                    f = 0
                if f:
                    g.append(x)
        if len(g) == 1:
            x = g[0]
            if x != root:
                g.append(par[x])
            else:
                y = Qd(x)
                if y == 0:
                    A(x)
                else:
                    y = Qs(x)
                    bad[x] = 1
                    root = y
                    n = ch[y]
                continue
        x = g[0]
        y = g[1]
        if dep[x] > dep[y]:
            x, y = y, x
        xd = Qd(x)
        yd = Qd(y)
        if xd < yd:
            bad[y] = 1
            n -= ch[y]
        else:
            bad[x] = 1
            root = y
            n = ch[y]
main()