#1720. Nauuo and Binary Tree

Nauuo and Binary Tree

Description

This is an interactive problem.

Nauuo is a girl who loves binary trees.

One day, she created a binary tree consisting of nn nodes. The nodes are numbered from 11 to nn. The root of the tree is the node 11.

However, Nauuo can't remember the tree exactly. She only remembers the distance between every two nodes, you can make some queries on the distance to find the whole binary tree.

The distance between two nodes is the number of edges of the shortest path between the two nodes.

You are allowed to make no more than 3000030000 queries, and you only have to tell Nauuo the parent of each node except the root.

Interaction

The interaction starts with a line containing one integer nn (2n30002\le n\le 3000) --- the number of nodes.

After that, you can make queries.

To make a query, print a line "? u v\texttt{? u v}" (1u,vn1\le u,v\le n), then flush\texttt{flush} the output.

After each query, read a single integer dd (0dn10\le d\le n-1) --- the distance between uu and vv.

When you find the whole binary tree, print a line "! p\texttt{! p}", flush\texttt{flush} the output and terminate. pp is an array containing n1n-1 integers, where the ii-th element of pp is the parent of node i+1i+1.

The interactor will cost no more than 500ms500ms if you make no more than 3000030000 queries.

Your solution will get Wrong Answer\texttt{Wrong Answer} or Time Limit Exceeded\texttt{Time Limit Exceeded} if you make more than 3000030000 queries.

Your solution will get Idleness Limit Exceeded\texttt{Idleness Limit Exceeded} if you don't print anything or forget to flush the output.

To flush\texttt{flush} you need to do the following right after printing a query and a line end:

  • fflush(stdout)\texttt{fflush(stdout)} or cout.flush()\texttt{cout.flush()} in C++;
  • System.out.flush()\texttt{System.out.flush()} in Java;
  • flush(output)\texttt{flush(output)} in Pascal;
  • stdout.flush()\texttt{stdout.flush()} in Python;
  • see documentation for other languages.

Hacks

The first line contains a single integer nn (2n30002\le n\le 3000) --- the number of nodes.

The second line contains an array pp containing n1n-1 integers, where the ii-th element of pp is the parent of node i+1i+1.

For hacks, you have to guarantee that the given parents can form a tree.

Example 1

4
1
2
3
? 1 2
? 1 3
? 3 4
! 1 2 1

The binary tree is as follows.

In the first query, the distance between 11 and 22 is 11 (121\rightarrow2).

In the second query, the distance between 11 and 33 is 22 (1231\rightarrow2\rightarrow3).

In the third query, the distance between 33 and 44 is 33 (32143\rightarrow2\rightarrow1\rightarrow4).

5
4
1
? 4 3
? 2 4
! 1 5 2 1

The binary tree is as follows.