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:
//package round563;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class F {
	Scanner in;
	PrintWriter out;
	String INPUT = "";
	
	void solve()
	{
		int n = ni();
		int[] from = new int[n - 1];
		int[] to = new int[n - 1];
		for (int i = 0; i < n - 1; i++) {
			from[i] = ni() - 1;
			to[i] = ni() - 1;
		}
		int[][] g = packU(n, from, to);
		int[][] pars = parents3(g, 0);
		int[] par = pars[0], ord = pars[1], dep = pars[2];
//		int[][] spar = logstepParents(par);
		
		int cur = 0;
		int d0 = d(cur);
		if(d0 == 0){
			out.println("! " + (cur+1));
			out.flush();
			return;
		}
		
		boolean[] cans = new boolean[n];
		for(int i = 0;i < n;i++){
			if(dep[i] == d0){
				cans[i] = true;
			}
		}
		int[] des = new int[n];
		for(int i = n-1;i >= 0;i--){
			int c = ord[i];
			des[c] += cans[c] ? 1 : 0;
			if(c > 0)des[par[c]] += des[c];
		}
		
		while(true){
			int ncan = 0;
			int who = -1;
			for(int i = 0;i < n;i++){
				if(cans[i]){
					ncan++;
					who = i;
				}
			}
			if(ncan == 1){
				out.println("! " + (who+1));
				out.flush();
				return;
			}
			
			int max = 0;
			int arg = -1;
			while(true){
				max = 0;
				arg = -1;
				for(int e : g[cur]){
					if(par[cur] == e)continue;
					if(des[e] > max){
						max = des[e];
						arg = e;
					}
				}
				if(max == des[cur]){
					cur = arg;
				}else{
					break;
				}
			}
			int pos = arg;
			while(des[pos]*2 > des[cur]){
				max = 0;
				arg = -1;
				for(int e : g[pos]){
					if(par[pos] == e)continue;
					if(des[e] > max){
						max = des[e];
						arg = e;
					}
				}
				pos = arg;
			}
			// pos-cur
			if(dep[pos] - dep[cur] == 1){
				cur = s(cur);
				boolean[] rs = rs(cur, g, par[cur]);
				for(int i = 0;i < n;i++){
					cans[i] &= rs[i];
				}
			}else{
				int d = d(pos);
				if(d == 0){
					out.println("! " + (pos+1));
					out.flush();
					return;
				}
				int[] ds = ds(pos, g);
				for(int i = 0;i < n;i++){
					cans[i] &= ds[i] == d;
				}
			}
			
			des = new int[n];
			for(int i = n-1;i >= 0;i--){
				int c = ord[i];
				des[c] += cans[c] ? 1 : 0;
				if(c > 0)des[par[c]] += des[c];
			}
		}
	}
	
	boolean[] rs(int x, int[][] g, int px)
	{
		int n = g.length;
		boolean[] d = new boolean[n];
		d[x] = true;
		int[] q = new int[n];
		int p = 0;
		q[p++] = x;
		for(int r = 0;r < p;r++){
			int cur = q[r];
			for(int e : g[cur]){
				if(e != px && !d[e]){
					d[e] = true;
					q[p++] = e;
				}
			}
		}
		return d;
	}
	
	int[] ds(int x, int[][] g)
	{
		int n = g.length;
		int[] d = new int[n];
		Arrays.fill(d, 9999999);
		d[x] = 0;
		int[] q = new int[n];
		int p = 0;
		q[p++] = x;
		for(int r = 0;r < p;r++){
			int cur = q[r];
			for(int e : g[cur]){
				if(d[e] > d[cur] + 1){
					d[e] = d[cur] + 1;
					q[p++] = e;
				}
			}
		}
		return d;
	}
	
	int d(int x)
	{
		out.println("d " + (x+1));
		out.flush();
		return ni();
	}
	
	int s(int x)
	{
		out.println("s " + (x+1));
		out.flush();
		return ni()-1;
	}
	
	public static int lca2(int a, int b, int[][] spar, int[] depth) {
		if (depth[a] < depth[b]) {
			b = ancestor(b, depth[b] - depth[a], spar);
		} else if (depth[a] > depth[b]) {
			a = ancestor(a, depth[a] - depth[b], spar);
		}

		if (a == b)
			return a;
		int sa = a, sb = b;
		for (int low = 0, high = depth[a], t = Integer.highestOneBit(high), k = Integer
				.numberOfTrailingZeros(t); t > 0; t >>>= 1, k--) {
			if ((low ^ high) >= t) {
				if (spar[k][sa] != spar[k][sb]) {
					low |= t;
					sa = spar[k][sa];
					sb = spar[k][sb];
				} else {
					high = low | t - 1;
				}
			}
		}
		return spar[0][sa];
	}

	protected static int ancestor(int a, int m, int[][] spar) {
		for (int i = 0; m > 0 && a != -1; m >>>= 1, i++) {
			if ((m & 1) == 1)
				a = spar[i][a];
		}
		return a;
	}

	public static int[][] logstepParents(int[] par) {
		int n = par.length;
		int m = Integer.numberOfTrailingZeros(Integer.highestOneBit(n - 1)) + 1;
		int[][] pars = new int[m][n];
		pars[0] = par;
		for (int j = 1; j < m; j++) {
			for (int i = 0; i < n; i++) {
				pars[j][i] = pars[j - 1][i] == -1 ? -1 : pars[j - 1][pars[j - 1][i]];
			}
		}
		return pars;
	}


	public static int[][] parents3(int[][] g, int root) {
		int n = g.length;
		int[] par = new int[n];
		Arrays.fill(par, -1);

		int[] depth = new int[n];
		depth[0] = 0;

		int[] q = new int[n];
		q[0] = root;
		for (int p = 0, r = 1; p < r; p++) {
			int cur = q[p];
			for (int nex : g[cur]) {
				if (par[cur] != nex) {
					q[r++] = nex;
					par[nex] = cur;
					depth[nex] = depth[cur] + 1;
				}
			}
		}
		return new int[][] { par, q, depth };
	}

	static int[][] packU(int n, int[] from, int[] to) {
		int[][] g = new int[n][];
		int[] p = new int[n];
		for (int f : from)
			p[f]++;
		for (int t : to)
			p[t]++;
		for (int i = 0; i < n; i++)
			g[i] = new int[p[i]];
		for (int i = 0; i < from.length; i++) {
			g[from[i]][--p[from[i]]] = to[i];
			g[to[i]][--p[to[i]]] = from[i];
		}
		return g;
	}

	
	void run() throws Exception
	{
		in = oj ? new Scanner(System.in) : new Scanner(INPUT);
		out = new PrintWriter(System.out);

		long s = System.currentTimeMillis();
		solve();
		out.flush();
		tr(System.currentTimeMillis()-s+"ms");
	}
	
	public static void main(String[] args) throws Exception
	{
		new F().run();
	}
	
	int ni() { return Integer.parseInt(in.next()); }
	long nl() { return Long.parseLong(in.next()); }
	double nd() { return Double.parseDouble(in.next()); }
	boolean oj = System.getProperty("ONLINE_JUDGE") != null;
	void tr(Object... o) { if(!oj)System.out.println(Arrays.deepToString(o)); }
}