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

public class R562F
{
	
	static int[] par;
	static int[] size;
	static int[] distanceToRoot;
	static boolean[] removed;
	static ArrayList<Integer>[] to;

	public static void main(String[] args)
	{
		JS scan = new JS();
		PrintWriter out = new PrintWriter(System.out);
		int n = scan.nextInt();
		par = new int[n];
		removed = new boolean[n];
		distanceToRoot = new int[n];
		size = new int[n];
		to = new ArrayList[n];
		for(int i = 0; i < n; i++) to[i] = new ArrayList<Integer>();
		for(int i = 0; i < n-1; i++) {
			int u = scan.nextInt()-1;
			int v = scan.nextInt()-1;
			to[u].add(v);
			to[v].add(u);
		}
		out.println("d 1");
		out.flush();
		int ld = scan.nextInt();
		if(ld == 0) {
			out.println("! "+1);
			out.flush();
			return;
		}
		int curr = 0;
		while(true) {
			out.println("s "+(curr+1));
			out.flush();
			int nr = scan.nextInt()-1;
			ld--;
			if(ld == 0) {
				out.println("! "+(nr+1));
				out.flush();
				return;
			}
			
			updateSubtreeSizes(nr);
			dist(nr, 0);
			//System.out.println(Arrays.toString(size));
			//System.out.println(Arrays.toString(distanceToRoot));
			//System.out.println(size[nr]);
			int c = findCentroid(nr, size[nr]);
			out.println("d "+(c+1));
			out.flush();
			int nd = scan.nextInt();
			if(nd == 0) {
				out.println("! "+(c+1));
				out.flush();
				return;
			}
			
			if(ld == nd+distanceToRoot[c]) {
				curr = c;
				ld = nd;
			}
			else {
				removed[c] = true;
				curr = nr;
			}
		}
	}
	
	static int findCentroid(int root, int n) {
		int biggest = 0;
		int max = 0;
		boolean g = true;
		for(int i = 0; i < to[root].size(); i++) {
			int e = to[root].get(i);
			if(par[root] != e && !removed[e]) {
				if(size[e] > max) {
					biggest = e;
					max = size[e];
				}
				if(size[e] > n/2) g = false;
			}
		}
		//System.out.println(Math.max(n-size[root], sum));
		if(g && n-size[root] <= n/2) return root;
		return findCentroid(biggest, n);
	}
	
	static int updateSubtreeSizes(int root) {
		size[root] = 1;
		for(int i = 0; i < to[root].size(); i++) {
			int e = to[root].get(i);
			if(par[root] != e && !removed[e]) {
				par[e] = root;
				size[root] += updateSubtreeSizes(e);
			}
		}
		return size[root];
	}
	
	static void dist(int root, int c) {
		distanceToRoot[root] = c;
		for(int i = 0; i < to[root].size(); i++) {
			int e = to[root].get(i);
			if(par[root] != e) {
				par[e] = root;
				dist(e, c+1);
			}
		}
	}
	
	
	static class JS{
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public JS() {
			in = new BufferedInputStream(System.in, BS);
		}

		public JS(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}				
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
	}
}