# 终点## 题目背景!httpscdnluogucomcnuploadimage_hosting3u2zy1q5png出题人怎么还没鸟加这首歌啊。## 题目描述这是一道交互题。dXqwq 有一棵 $n$ 个点的有根树结点从 $1$ 到 $n$ 编号。您需要通过若干次询问得到这棵树的结构。您可以选择两个整数 $1leq uvleq n$并输出 u v 进行询问。对于每次询问如果 $uv$ 的路径

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int id, n;
    cin >> id >> n;

    vector<int> deg(n + 1, 0);

    // Step 1: Find a leaf node
    int leaf = -1;
    for (int i = 2; i <= n; i++) {
        cout << "? " << i << " 1" << endl;
        int res;
        cin >> res;
        if (res == 0) {
            leaf = i;
            break;
        }
        deg[res]++;
    }

    // Step 2: Find the parent of the leaf node
    int parent = -1;
    for (int i = 1; i <= n; i++) {
        if (deg[i] == 0 && i != leaf) {
            cout << "? " << leaf << " " << i << endl;
            int res;
            cin >> res;
            if (res != 0) {
                parent = res;
                break;
            }
        }
    }

    // Step 3: Process the remaining nodes
    for (int i = 1; i <= n; i++) {
        if (i == leaf) {
            continue;
        }
        cout << "? " << leaf << " " << i << endl;
        int res;
        cin >> res;
        if (res == 0) {
            cout << "? " << parent << " " << i << endl;
            cin >> res;
        }
        deg[res]++;
    }

    // Step 4: Output the edges
    cout << "!" << endl;
    for (int i = 1; i <= n; i++) {
        if (i != parent) {
            cout << parent << " " << i << endl;
        }
    }

    return 0;
}
``