Problem: This is an interactive problem.

After getting AC after 13 Time Limit Exceeded verdicts on a geometry problem, Kuroni went to an Italian restaurant to celebrate this holy achievement. Unfortunately, the excess sauce disoriented him, and he's now lost!

The United States of America can be modeled as a tree (why though) with n vertices. The tree is rooted at vertex r, wherein lies Kuroni's hotel.

Kuroni has a phone app designed to help him in such emergency cases. To use the app, he has to input two vertices u and v, and it'll return a vertex w, which is the lowest common ancestor of those two vertices.

However, since the phone's battery has been almost drained out from live-streaming Kuroni's celebration party, he could only use the app at most ⌊ n/2 ⌋ times. After that, the phone would die and there will be nothing left to help our dear friend! :(

As the night is cold and dark, Kuroni needs to get back, so that he can reunite with his comfy bed and pillow(s). Can you help him figure out his hotel's location?

Interaction

The interaction starts with reading a single integer n (2 ≤ n ≤ 1000), the number of vertices of the tree.

Then you will read n-1 lines, the i-th of them has two integers x_i and y_i (1 ≤ x_i, y_i ≤ n, x_i ≠ y_i), denoting there is an edge connecting vertices x_i and y_i. It is guaranteed that the edges will form a tree.

Then you can make queries of type "? u v" (1 ≤ u, v ≤ n) to find the lowest common ancestor of vertex u and v.

After the query, read the result w as an integer.

In case your query is invalid or you asked more than ⌊ n/2 ⌋ queries, the program will print -1 and will finish interaction. You will receive a Wrong answer verdict. Make sure to exit immediately to avoid getting other verdicts.

When you find out the vertex r, print "! r" and quit after that. This query does not count towards the ⌊ n/2 ⌋ limit.

Note that the tree is fixed beforehand and will not change during the queries, i.e. the interactor is not adaptive.

After printing any query do not forget to print end of line and flush the output. Otherwise, you might 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

To hack, use the following format:

The first line should contain two integers n and r (2 ≤ n ≤ 1000, 1 ≤ r ≤ n), denoting the number of vertices and the vertex with Kuroni's hotel.

The i-th of the next n-1 lines should contain two integers x_i and y_i (1 ≤ x_i, y_i ≤ n) — denoting there is an edge connecting vertex x_i and y_i.

The edges presented should form a tree.

Example

Input


6
1 4
4 2
5 3
6 3
2 3

3

4

4



Output








? 5 6

? 3 1

? 1 2

! 4

Note

Note that the example interaction contains extra empty lines so that it's easier to read. The real interaction doesn't contain any empty lines and you shouldn't print any extra empty lines as well.

The image below demonstrates the tree in the sample test:

<image>

Solution (in JAVA):

Solution:
/**
 * BaZ :D
 */

import java.lang.reflect.Array;
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class ACMIND
{
    static FastReader scan;
    static PrintWriter pw;
    static long MOD = 1_000_000_007;
    static long INF = 2_000_000_000_000_000_000L;
    static long inf = 2_000_000_000;
    public static void main(String[] args) {
        new Thread(null,null,"BaZ",1<<27)
        {
            public void run()
            {
                try
                {
                    solve();
                }
                catch(Exception e)
                {
                    e.printStackTrace();
                    System.exit(1);
                }
            }
        }.start();
    }

    static void solve() throws IOException
    {
        scan = new FastReader();
        pw = new PrintWriter(System.out,true);
        StringBuilder sb = new StringBuilder();
        int n = ni();
        Map<Integer, ArrayList<Integer>> edges = new HashMap<>();
        for(int i=1;i<n;++i) {
            int u = ni(), v = ni();
            add(u,v,edges);
        }
        findRoot(edges);
        pw.flush();
        pw.close();
    }

    static int findRoot(Map<Integer, ArrayList<Integer>> edges) throws IOException {
//        pl("Solving edges : ");
//        for(int e : edges.keySet()) {
//            pl(e+" ");
//            pa("adjacent nodes : ", edges.get(e));
//        }
        if(edges.size() == 1) {
            int x = -1;
            for(int e : edges.keySet()) {
                x = e;
                break;
            }
            pl("! "+x);
            pw.flush();
            System.exit(0);
        }
        ArrayList<Integer> diameter = getDiameter(edges);
        int d = diameter.size();
        int u = diameter.get(0), v = diameter.get(d-1);
        int lca = getLCA(u,v);
        if(lca==u) {
            pl("! "+u);
            pw.flush();
            System.exit(0);
        }
        else if(lca==v) {
            pl("! "+v);
            pw.flush();
            System.exit(0);
        }

        int prev = -1, next = -1;
        for(int i=0;i<d;++i) {
            if(diameter.get(i) == lca) {
                if(i>0) {
                    prev = diameter.get(i-1);
                }
                if(i+1<d) {
                    next = diameter.get(i+1);
                }
                break;
            }
        }

        Map<Integer, ArrayList<Integer>> newedges = new HashMap<>();
        for(int e : edges.get(lca)) {
            if(e==prev || e==next) {
                continue;
            }
            add(lca, e, newedges);
            addEdges(e,lca,edges, newedges);
        }
        if(newedges.size() == 0) {
            pl("! "+lca);
            pw.flush();
            System.exit(0);
        }
        return findRoot(newedges);
    }
    static void addEdges(int v, int par, Map<Integer, ArrayList<Integer>> edges, Map<Integer, ArrayList<Integer>> new_edges) {
        for(int e : edges.get(v)) {
            if(e!=par) {
                add(v,e,new_edges);
                addEdges(e,v,edges, new_edges);
            }
        }
    }
    static void add(int u, int v, Map<Integer, ArrayList<Integer>> edges) {
        ArrayList<Integer> list = edges.get(u);
        if(list==null) {
            list = new ArrayList<>();
        }
        list.add(v);
        edges.put(u,list);
        list = edges.get(v);
        if(list==null) {
            list = new ArrayList<>();
        }
        list.add(u);
        edges.put(v,list);
    }
    static ArrayList<Integer> getDiameter(Map<Integer, ArrayList<Integer>> map) {
        int first = -1;
        for(int e : map.keySet()) {
            first = e;
            break;
        }

        //pl("First Node : "+first);

        Map<Integer, Pair> from_first = BFS(first, map);
        int dis = -1, farthest_node = -1;
        for(Map.Entry<Integer, Pair> entry : from_first.entrySet()) {
            if(entry.getValue().x > dis) {
                dis = entry.getValue().x;
                farthest_node = entry.getKey();
            }
        }

        //pl("Farthest Node : "+farthest_node+" Dis : "+dis);

        Map<Integer, Pair> from_second = BFS(farthest_node,map);
        dis = -1;
        int farthest_from_farthest_node = -1;
        for(Map.Entry<Integer, Pair> entry : from_second.entrySet()) {
            if(entry.getValue().x > dis) {
                dis = entry.getValue().x;
                farthest_from_farthest_node = entry.getKey();
            }
        }

        //pl("fff : "+farthest_from_farthest_node+" Dis : "+dis);

        ArrayList<Integer> diameter = new ArrayList<>();
        int curr = farthest_from_farthest_node;
        while(curr!=-1) {
            diameter.add(curr);
            curr = from_second.get(curr).y;
        }
        //pa("Diameter : ", diameter);
        return diameter;
    }

    static Map<Integer, Pair> BFS(int from, Map<Integer, ArrayList<Integer>> edges) {
        //pl("Running BFS from "+from);
        Map<Integer, Pair> info = new HashMap<>();
        info.put(from, new Pair(0, -1));
        LinkedList<Integer> queue = new LinkedList<>();
        queue.addLast(from);
        while (!queue.isEmpty()) {
            int curr = queue.pollFirst();
            //pl("curr : "+curr);
            int dis = info.get(curr).x;
            for(int e : edges.get(curr)) {
                if(!info.containsKey(e)) {
                    info.put(e, new Pair(dis+1, curr));
                    queue.addLast(e);
                }
            }
        }
        return info;
    }

    static class Pair implements Comparable<Pair>
    {
        int x,y;
        Pair(int x,int y)
        {
            this.x=x;
            this.y=y;
        }
        public int compareTo(Pair other)
        {
            if(this.x!=other.x)
                return this.x-other.x;
            return this.y-other.y;
        }
        public String toString()
        {
            return "("+x+","+y+")";
        }
    }
    static int getLCA(int u, int v) throws IOException {
        pl("? "+u+" "+v);
        pw.flush();
        return ni();
    }
    static int ni() throws IOException
    {
        return scan.nextInt();
    }
    static long nl() throws IOException
    {
        return scan.nextLong();
    }
    static double nd() throws IOException
    {
        return scan.nextDouble();
    }
    static void pl()
    {
        pw.println();
    }
    static void p(Object o)
    {
        pw.print(o+" ");
    }
    static void pl(Object o)
    {
        pw.println(o);
    }
    static void psb(StringBuilder sb)
    {
        pw.print(sb);
    }
    static void pa(String arrayName, Object arr[])
    {
        pl(arrayName+" : ");
        for(Object o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, int arr[])
    {
        pl(arrayName+" : ");
        for(int o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, long arr[])
    {
        pl(arrayName+" : ");
        for(long o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, double arr[])
    {
        pl(arrayName+" : ");
        for(double o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, char arr[])
    {
        pl(arrayName+" : ");
        for(char o : arr)
            p(o);
        pl();
    }
    static void pa(String listName, List list)
    {
        pl(listName+" : ");
        for(Object o : list)
            p(o);
        pl();
    }
    static void pa(String arrayName, Object[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(Object o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, int[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(int o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, long[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(long o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, char[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(char o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, double[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(double o : arr[i])
                p(o);
            pl();
        }
    }
    static class FastReader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public FastReader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public FastReader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[1000000];
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg) return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg) return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (c == '.') while ((c = read()) >= '0' && c <= '9') ret += (c - '0') / (div *= 10);
            if (neg) return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1) buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead) fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null) return;
            din.close();
        }
    }
}