City Mapping

Time limit1sMemory limit512 MB

Summary

Recover every edge and weight of a hidden tree with at most three roads per junction, using shortest-distance queries limited to Q questions.

Level: Medium7 of 10
Topics: Tree, Divide and conquer, Graph
Solved: No attempts yet

Problem

Peanut is going on a holiday to the city Silvermill, so he needs a map of Silvermill. Unfortunately, his computer is broken, so he cannot search for a map online.

Silvermill has $N$ road junctions, numbered 1 to $N$ , and $N-1$ roads. Road $i$ connects junctions $A_i$ and $B_i$ in both directions, and it takes $W_i$ minutes to travel along it in either direction. The city is fully connected, so you can travel from any junction to any other junction using the roads. To avoid congestion, the governor of Silvermill has decided that no junction has more than three roads connected to it.

Peanut needs a map of Silvermill. In other words, he needs $(A_i, B_i, W_i)$ for $i = 1, \ldots, N-1$ .

Peanut has hired a cartographer in Silvermill to do this. The cartographer is not very skilled and can only answer one kind of question: what is the minimum time, in minutes, needed to travel from junction $X$ to junction $Y$ ? The cartographer only answers $Q$ questions before he quits.

Peanut needs you to design a list of questions that lets him map out Silvermill. Can you help him?

Constraints

$2 \le N \le 1000$
$1 \le A_i, B_i \le N$
$1 \le W_i \le 10^9$

Examples1

Example 1
Input
```
2
7
```
Expected output
```
? 1 2
!
1 2 7
```