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 JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.List;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;
import java.util.ArrayList;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {

    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        FIhabIBolshoiFinal solver = new FIhabIBolshoiFinal();
        solver.solve(1, in, out);
        out.close();
    }

    static class FIhabIBolshoiFinal {

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            Vertex[] vs = Vertex.emptyGraph(n);
            for (int i = 0; i < n - 1; i++) {
                int u = in.nextInt() - 1;
                int v = in.nextInt() - 1;
                vs[u].adj.add(vs[v]);
                vs[v].adj.add(vs[u]);
            }

            out.println(String.format("d %d", 1));
            out.flush();
            int d0 = in.nextInt();

            boolean[] passable = new boolean[n];
            Arrays.fill(passable, true);
            Vertex prev = vs[0];
            Vertex st = vs[0];

            int[] rank = new int[n];
            while (true) {
                int[] size = new int[n];
                dfs(prev, st, rank[st.idx], passable, rank, size);

                for (Vertex cur : vs) {
                    if (size[cur.idx] == 0) {
                        passable[cur.idx] = false;
                    }
                }

                int sz = 1;
                for (Vertex to : st.adj) {
                    if (to == prev || !passable[to.idx]) {
                        continue;
                    }
                    sz += size[to.idx];
                }

                Vertex centroid = null;
                for (Vertex cur : vs) {
                    if (!passable[cur.idx]) {
                        continue;
                    }
                    boolean isCentroid = true;
                    int all = 0;
                    for (Vertex to : cur.adj) {
                        if (rank[to.idx] < rank[cur.idx] || !passable[to.idx]) {
                            continue;
                        }
                        isCentroid &= size[to.idx] <= sz / 2;
                        all += size[to.idx];
                    }
                    isCentroid &= (sz - all - 1) <= sz / 2;
                    if (isCentroid) {
                        centroid = cur;
                        break;
                    }
                }

                out.println(String.format("d %d", centroid.idx + 1));
                out.flush();
                int d = in.nextInt();
                if (d == 0) {
                    out.println(String.format("! %d", centroid.idx + 1));
                    out.flush();
                    return;
                }
                if (d0 == d + rank[centroid.idx]) {
                    out.println(String.format("s %d", centroid.idx + 1));
                    out.flush();
                    prev = centroid;
                    st = vs[in.nextInt() - 1];
                    if (d == 1) {
                        out.println(String.format("! %d", st.idx + 1));
                        out.flush();
                        return;
                    }
                } else {
                    passable[centroid.idx] = false;
                }
            }
        }

        void dfs(Vertex prev, Vertex cur, int r, boolean[] passable, int[] rank, int size[]) {
            rank[cur.idx] = r;
            size[cur.idx] = 1;
            for (Vertex to : cur.adj) {
                if (to == prev || !passable[to.idx]) {
                    continue;
                }
                dfs(cur, to, r + 1, passable, rank, size);
                size[cur.idx] += size[to.idx];
            }
        }
    }

    static class Vertex {

        int idx;
        List<Vertex> adj = new ArrayList<>();

        public static Vertex[] emptyGraph(int n) {
            Vertex[] vs = new Vertex[n];
            for (int i = 0; i < n; i++) {
                vs[i] = new Vertex();
                vs[i].idx = i;
            }
            return vs;
        }
    }

    static class InputReader {

        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }
}