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.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;

public class Codeforces {
    static class Node {
        int depth;
        int parent;
        int maxDepthChild ;
        int maxChildDepth;
        int size;
        //child with max size
        int maxSizeChild;
        //size of the above child
        int maxChildSize;
        List<Integer> adj;
        Node() {
            adj = new ArrayList<>();
        }
        public String toString() {
            return "depth(" + depth + "), size(" + size + "), parent(" + parent + "), maxDepthChild (" + maxDepthChild + "), maxChildDepth(" + maxChildDepth + ")"
                   + ", maxSizedChild(" + maxSizeChild + ") maxChildSize(" + maxChildSize + ")";
        }
    }
    static class Tree {
        Node[] nodes;
        Tree(int n) {
            nodes = new Node[1 + n];
            for (int i = 0; i <= n; ++i) {
                nodes[i] = new Node();
            }
        }
        void addEdge(int u, int v) {
            nodes[u].adj.add(v);
            nodes[v].adj.add(u);
        }
        void setDepths() {
            boolean[] visited = new boolean[nodes.length];
            Queue<Integer> q = new LinkedList<>();
            q.add(1);

            nodes[1].depth = 0;
            nodes[1].parent = -1;
            nodes[1].size = 1;
            nodes[1].maxSizeChild = -1;
            nodes[1].maxChildSize = 0;

            nodes[1].maxDepthChild = 1;
            nodes[1].maxChildDepth = 0;

            int maxDepth = 0;
            while (!q.isEmpty()) {
                int node = q.poll();
                if (visited[node]) continue;
                visited[node] = true;
                for (int nei : nodes[node].adj) {
                    if (visited[nei]) continue;
                    nodes[nei].parent = node;
                    nodes[nei].depth = nodes[node].depth + 1;
                    nodes[nei].maxChildDepth = nodes[nei].depth;
                    nodes[nei].maxDepthChild = nei;

                    nodes[nei].size = 1;
                    nodes[nei].maxSizeChild = -1;
                    nodes[nei].maxChildSize = 0;
                    maxDepth = max(maxDepth, nodes[nei].depth);
                    q.add(nei);
                }
            }
            List<Integer>[] depths = new List[1 + maxDepth];
            for (int i = 0; i < depths.length; ++i) {
                depths[i] = new ArrayList<>();
            }
            q.add(1);
            visited = new boolean[nodes.length];
            while (!q.isEmpty()) {
                int node = q.poll();
                if (visited[node]) continue;
                visited[node] = true;
                depths[nodes[node].depth].add(node);
                for (int nei : nodes[node].adj) {
                    if (visited[nei]) continue;
                    q.add(nei);
                }
            }
            // println("Depth array is " + Arrays.toString(depths));
            //merge step
            for (int i = depths.length - 1; i >= 1; --i) {
                for (int ele : depths[i]) {
                    int parent = nodes[ele].parent;
                    if (nodes[ele].size > nodes[parent].maxChildSize) {
                        nodes[parent].maxSizeChild = ele;
                        nodes[parent].maxChildSize = nodes[ele].size;
                        nodes[parent].maxDepthChild = nodes[ele].maxDepthChild;
                        nodes[parent].maxChildDepth = nodes[ele].maxChildDepth;
                    }
                    nodes[parent].size += nodes[ele].size;
                }
            }
        }
        int findy(int v, int dpy) throws IOException {
            while (v != 1) {
                int depth = nodes[v].depth;
                if (depth == dpy) {
                    return v;
                }
                v = nodes[v].parent;
            }
            return 1;
        }
    }
    static void main() throws Exception {
        int n = ni();
        Tree g = new Tree(n);
        for (int i = 0; i < n - 1; ++i) {
            g.addEdge(ni(), ni());
        }
        g.setDepths();
        // for (int i = 1; i < g.nodes.length; ++i) {
        // println("Node " + i + " --> " + g.nodes[i]);
        // }
        println("d 1");
        flush();
        int d1 = ni();
        if (d1 == 0) {
            println("! 1");
            return;
        }

        int u = 1;
        while (true) {
            if (u == -1) {
                break;
            }
            int v = g.nodes[u].maxDepthChild;
            println("d " + v);
            flush();
            int d = ni();
            if (d == 0) {
                println("! " + v);
                return;
            }
            //d(x, v) = dp(x) + dp(v) - 2 * dp(y);
            int dpy = (d1 + g.nodes[v].depth - d) >> 1;
            int y = g.findy(v, dpy);
            if (dpy == d1) {
                println("! " + y);
                flush();
                return;
            }
            println("s " + y);
            flush();
            u = ni();
        }
    }

    public static void main(String[] args) throws Exception {
        scannerIn = System.in;
        printerBW = new BufferedWriter(new OutputStreamWriter(System.out));
        main();
        close();
    }

    static int abs(int a) {
        return Math.abs(a);
    }

    static long abs(long a) {
        return Math.abs(a);
    }

    static float abs(float a) {
        return Math.abs(a);
    }

    static double abs(double a) {
        return Math.abs(a);
    }

    static int min(int x, int y) {
        return Math.min(x, y);
    }

    static long min(long x, long y) {
        return Math.min(x, y);
    }

    static double min(double x, double y) {
        return Math.min(x, y);
    }

    static int min(int ... arr) {
        int min = Integer.MAX_VALUE;
        for (int var : arr)
            min = Math.min(min, var);
        return min;
    }

    static long min(long ... arr) {
        long min = Long.MAX_VALUE;
        for (long var : arr)
            min = Math.min(min, var);
        return min;
    }

    static double min(double ... arr) {
        double min = Double.MAX_VALUE;
        for (double var : arr)
            min = Math.min(min, var);
        return min;
    }

    static int max(int x, int y) {
        return Math.max(x, y);
    }

    static long max(long x, long y) {
        return Math.max(x, y);
    }

    static double max(double x, double y) {
        return Math.max(x, y);
    }

    static int max(int ... arr) {
        int max = Integer.MIN_VALUE;
        for (int var : arr)
            max = Math.max(max, var);
        return max;
    }

    static long max(long ... arr) {
        long max = Long.MIN_VALUE;
        for (long var : arr)
            max = Math.max(max, var);
        return max;
    }

    static double max(double ... arr) {
        double max = -Double.MAX_VALUE;
        for (double var : arr)
            max = Math.max(max, var);
        return max;
    }
    //IO Stuff
    private static byte[] scannerByteBuffer = new byte[1024]; // Buffer of Bytes
    private static int scannerIndex;
    private static InputStream scannerIn;
    private static int scannerTotal;
    private static BufferedWriter printerBW;

    private static int next() throws IOException { // Scan method used to scan buf
        if (scannerTotal < 0)
            throw new InputMismatchException();
        if (scannerIndex >= scannerTotal) {
            scannerIndex = 0;
            scannerTotal = scannerIn.read(scannerByteBuffer);
            if (scannerTotal <= 0)
                return -1;
        }
        return scannerByteBuffer[scannerIndex++];
    }

    static int ni() throws IOException {
        int integer = 0;
        int n = next();
        while (isWhiteSpace(n)) // Removing startPointing whitespaces
            n = next();
        int neg = 1;
        if (n == '-') { // If Negative Sign encounters
            neg = -1;
            n = next();
        }
        while (!isWhiteSpace(n)) {
            if (n >= '0' && n <= '9') {
                integer *= 10;
                integer += n - '0';
                n = next();
            } else
                throw new InputMismatchException();
        }
        return neg * integer;
    }

    private static boolean isNewLine(int n) {
        return n == '\n' || n == '\r' || n == -1;
    }

    private static boolean isWhiteSpace(int n) {
        return n == ' ' || isNewLine(n) || n == '\t';
    }

    static <T> void print(T ... str) {
        try {
            for (T ele : str)
                printerBW.append(ele.toString());
        } catch (IOException e) {
            System.out.println(e.toString());
        }
    }

    static <T> void println(T ... str) {
        if (str.length == 0) {
            print('\n');
            return;
        }
        for (T ele : str)
            print(ele, '\n');
    }

    static void flush() throws IOException {
        printerBW.flush();
    }

    static void close() {
        try {
            printerBW.close();
        } catch (IOException e) {
            System.out.println(e.toString());
        }
    }
}