下文中称御道为黄金边、非御道为普通边，先考虑 $30$ 分暴力怎么做.

任意求出原图的一棵生成树，借助这棵生成树求出黄金边的集合.

枚举不在生成树上的边 $(u,v)$，考虑将 $(u,v)$ 以及生成树上 $u$ 到 $v$ 的路径上，边的属性都确定下来.

• 若在之前，这些边的状态都未被确定：

  注意到 $(u,v)$ 以及该生成树共同构成一棵生成基环树，在该环上任意去掉一条边，均为一棵生成树.

  依次枚举去掉哪条边，并询问该生成树，则一共只有两种可能的答案；去掉某条边之后，答案比较大说明该条边是普通边，比较小说明是黄金边.

  若所有边去掉之后，答案都一样，由于不可能都是黄金边，则说明都是普通边.

• 若在之前，至少有一条边的状态已被确定：

  在该基环树上，任取一条已被确定的边，断开并询问；再依次枚举未被确定的边，断开并询问，比较两次询问的结果，一样说明该条边和取的那条边属性一致，不一样说明属性不一致.

以上算法用一次询问，可以处理一个未被确定的边的属性，并在每个环上至多浪费一次询问；故而，消耗的询问个数 $\leq2m$，可以获得 $30$ 分.

继续推进，考虑在上述步骤中，只求出生成树上的边的属性.

具体地，若之前都未被确定，则基环树在断开 $(u,v)$ 后就是原生成树，无需额外询问，其他照常枚举即可；若之前存在被确定，则任取一条，断开并询问之后，再枚举的时候，只枚举在生成树上未被确定的边即可.

在求出生成树上的边的属性之后，依次枚举不在生成树上的边 $(u,v)$，在 $u$ 到 $v$ 的路径上，任意断开一条边并加上 $(u,v)$ 这条边，比对其询问结果与原生成树询问结果，一样说明属性一致，否则不一致.

则生成树上的边，每条各最多消耗两个询问，总共消耗的询问个数 $\leq2n$；不在生成树上的边，每条各最多消耗两个询问，总共消耗的询问个数 $\leq m$，可以获得 $51$ 分.

考虑减少浪费，注意到其实，可以指定任意生成森林，并用一次询问求出，该生成森林中的边，一共有多少条黄金边；具体地，只需要维护一个并查集，先将该生成森林中的边加入并查集中，再依次考察生成树上的边，若其端点，在并查集中不已经连通，则将该边加入并查集中；用一次询问问出并查集中的所有边，中的黄金边条数，再去除掉生成树上的边，所带来的贡献即可.

一个结点的所有邻接边，构成一片生成森林；考虑依次枚举每个结点，并找出该结点的邻接边中，所有的黄金边；我们先将所有邻接边，单独拎出来考虑，设共有 $\mu$ 条邻接边，编号为 $1,2,\cdots,\mu$.

分治，当前处理的区间是 $[1,\mu]$；在处理区间 $[l,r]$ 时，需要已知该区间的邻接边中，黄金边的条数；若为 $0$ 则直接返回即可，若 $l=r$ 则说明，找到了一条黄金边；否则设 $p=\lfloor\dfrac{l+r}2\rfloor$，询问出区间 $[l,p]$ 中黄金边的条数，并递归到 $[l,p]$ 和 $(p,r]$ 进行处理.

设区间 $[1,\mu]$ 中一共有 $\gamma$ 条黄金边，则以上算法，用不超过 $\gamma\cdot\lceil\log\mu\rceil$ 条询问，即可找出所有的黄金边.

该算法所消耗的询问次数为 $n\log n+3n-\mathcal{O}(1)$，时间复杂度为 $\mathcal{O}(n^2\log n)$，空间复杂度为 $\mathcal{O}(n^2)$.

#include <bits/stdc++.h>
#include "simurgh.h"
#define rep(a,b,c) for(register int a=(b);a<=(c);++a)
#define dow(a,b,c) for(register int a=(b);a>=(c);--a)
using namespace std;
constexpr int MaxN = 500 + 5;
struct Vertex {
    int Fa, Rev;
    int Inn, Out;
    int head_0;
    int head_1;
};
Vertex vt[MaxN];
inline int Lch(const int e) {
    return (e << 1);
}
inline int Rch(const int e) {
    return (e << 1 | 1);
}
struct Edge_0 {
    int u, v;
    char Flag;
    int next;
};
Edge_0 ed_0[MaxN * MaxN];
int Overall_Ed_0 = 1;
inline void Ins_edge_0(const int u, const int v) {
    const int Ed = (++Overall_Ed_0);
    ed_0[Ed].u = u, ed_0[Ed].v = v;
    ed_0[Ed].Flag = '.';
    ed_0[Ed].next = vt[u].head_0;
    vt[u].head_0 = Ed;
}
inline void Ins_Edge_0(const int u, const int v) {
    Ins_edge_0(u, v), Ins_edge_0(v, u);
}
int arr_0[MaxN], arr_Inv[(MaxN * MaxN) >> 1];
std::vector<int> r;
inline int Query(const int n) {
    rep(i, 1, n - 1)
    r[i - 1] = (arr_0[i] - 1);
    return count_common_roads(r);
}
struct Edge_1 {
    int u, v;
    int idx;
    char Flag;
    int next;
};
Edge_1 ed_1[MaxN << 1];
int Overall_Ed_1 = 1;
inline void Ins_edge_1(const int u, const int v, const int idx) {
    const int Ed = (++Overall_Ed_1);
    ed_1[Ed].u = u, ed_1[Ed].v = v;
    ed_1[Ed].idx = idx;
    ed_1[Ed].Flag = '.';
    ed_1[Ed].next = vt[u].head_1;
    vt[u].head_1 = Ed;
}
inline void Ins_Edge_1(const int u, const int v, const int idx) {
    Ins_edge_1(u, v, idx), Ins_edge_1(v, u, idx);
}
int Overall_Inn;
inline void Dfs_Basics(const int u) {
    int v;
    vt[u].Inn = vt[u].Out = (++Overall_Inn);

    for (int e = vt[u].head_1; e; e = ed_1[e].next) {
        if ((v = ed_1[e].v) == vt[u].Fa)
            continue;

        vt[v].Fa = u, vt[v].Rev = e, Dfs_Basics(v);
        vt[u].Out = vt[v].Out;
    }
}
inline bool Is_Ancestor(const int u, const int v) {
    return ((vt[u].Inn <= vt[v].Inn) && (vt[v].Out <= vt[u].Out));
}
struct Connection_DisjointSet {
    int Fa[MaxN];
    inline void Initalize(const int n) {
        rep(i, 1, n) Fa[i] = i;
    }
    inline int getf(const int u) {
        if (u != Fa[u])
            Fa[u] = getf(Fa[u]);

        return Fa[u];
    }
    inline bool Merge(const int u, const int v) {
        const int Fu = getf(u), Fv = getf(v);

        if (Fu == Fv)
            return false;

        return ((Fa[Fv] = Fu), true);
    }
};
Connection_DisjointSet Con;
int arr_1[MaxN];
inline int Query_Arbitary(const int n, const int arr_1_Tot) {
    int u, v;
    Con.Initalize(n);
    int arr_0_Tot = 0;
    rep(i, 1, arr_1_Tot) {
        u = ed_0[Lch(arr_1[i])].u, v = ed_0[Lch(arr_1[i])].v;
        Con.Merge(u, v), arr_0[++arr_0_Tot] = arr_1[i];
    }
    int Count = 0;
    rep(i, 1, n - 1) {
        u = ed_1[Lch(i)].u, v = ed_1[Lch(i)].v;

        if (Con.Merge(u, v)) {
            arr_0[++arr_0_Tot] = ed_1[Lch(i)].idx;

            if (ed_1[Lch(i)].Flag == '1')
                ++Count;
        }
    }
    return (Query(n) - Count);
}
int the[MaxN];
bitset<MaxN> Bitset;
inline void Locate_Every(const int n, const int lef, const int rig, const int Count) {
    if (!Count)
        return;

    if (lef == rig) {
        Bitset[lef] = true;
        return;
    }

    const int mid = ((lef + rig) >> 1);
    rep(i, lef, mid)
    arr_1[i - lef + 1] = the[i];
    const int Count_mid = Query_Arbitary(n, mid - lef + 1);
    Locate_Every(n, lef, mid, Count_mid);
    Locate_Every(n, mid + 1, rig, (Count - Count_mid));
}
int Record[MaxN];
inline void Solve_IOI2017_Simurgh(const int n, const int m) {
    int u, v;
    Con.Initalize(n);
    rep(i, 1, m) {
        u = ed_0[Lch(i)].u, v = ed_0[Lch(i)].v;

        if (Con.Merge(u, v))
            ed_0[Lch(i)].Flag = ed_0[Rch(i)].Flag = '*', Ins_Edge_1(u, v, i);
    }
    rep(i, 1, n - 1)
    arr_Inv[arr_0[i] = ed_1[Lch(i)].idx] = i;
    const int Record_arr = Query(n), Tree_Root = 1;
    Dfs_Basics(Tree_Root);
    int the_Tot;
    rep(i, 1, m) {
        if (ed_0[Lch(i)].Flag == '*')
            continue;

        u = ed_0[Lch(i)].u, v = ed_0[Lch(i)].v, the_Tot = 0;

        while (!Is_Ancestor(u, v))
            the[++the_Tot] = (vt[u].Rev >> 1), u = vt[u].Fa;

        while (v != u)
            the[++the_Tot] = (vt[v].Rev >> 1), v = vt[v].Fa;

        int Count = 0;
        rep(i, 1, the_Tot)

        if (ed_1[Lch(the[i])].Flag != '.')
            ++Count;

        if (!Count) {
            int Record_Max = Record_arr;
            rep(j, 1, the_Tot) {
                arr_0[arr_Inv[ed_1[Lch(the[j])].idx]] = i;
                Record_Max = max(Record_Max, (Record[j] = Query(n)));
                arr_0[arr_Inv[ed_1[Lch(the[j])].idx]] = ed_1[Lch(the[j])].idx;
            }
            rep(j, 1, the_Tot)
            ed_1[Lch(the[j])].Flag = ed_1[Rch(the[j])].Flag = ((Record[j] == Record_Max) ? '0' : '1');
        } else if (Count != the_Tot) {
            int Record_Max, pos;
            rep(j, 1, the_Tot)

            if (ed_1[Lch(the[j])].Flag != '.') {
                pos = j;
                break;
            }

            arr_0[arr_Inv[ed_1[Lch(the[pos])].idx]] = i;
            Record_Max = (Query(n) + (ed_1[Lch(the[pos])].Flag == '1'));
            arr_0[arr_Inv[ed_1[Lch(the[pos])].idx]] = ed_1[Lch(the[pos])].idx;
            rep(j, 1, the_Tot) {
                if (ed_1[Lch(the[j])].Flag != '.')
                    continue;

                arr_0[arr_Inv[ed_1[Lch(the[j])].idx]] = i;
                ed_1[Lch(the[j])].Flag = ed_1[Rch(the[j])].Flag = ((Query(n) == Record_Max) ? '0' : '1');
                arr_0[arr_Inv[ed_1[Lch(the[j])].idx]] = ed_1[Lch(the[j])].idx;
            }
        }
    }
    rep(i, 1, n - 1) {
        if (ed_1[Lch(i)].Flag == '.')
            ed_1[Lch(i)].Flag = ed_1[Rch(i)].Flag = '1';

        ed_0[Lch(ed_1[Lch(i)].idx)].Flag = ed_0[Rch(ed_1[Lch(i)].idx)].Flag = ed_1[Lch(i)].Flag;
    }
    rep(i, 1, n) {
        the_Tot = 0;

        for (int e = vt[i].head_0; e; e = ed_0[e].next) {
            if (ed_0[e].Flag != '.')
                continue;

            the[++the_Tot] = (e >> 1);
        }

        if (!the_Tot)
            continue;

        rep(j, 1, the_Tot)
        arr_1[j] = the[j], Bitset[j] = false;
        Locate_Every(n, 1, the_Tot, Query_Arbitary(n, the_Tot));
        rep(j, 1, the_Tot)
        ed_0[Lch(the[j])].Flag = ed_0[Rch(the[j])].Flag = (Bitset[j] ? '1' : '0');
    }
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
    const int m = u.size();
    rep(i, 1, m)
    Ins_Edge_0((u[i - 1] + 1), (v[i - 1] + 1));
    r.resize(n - 1), Solve_IOI2017_Simurgh(n, m);
    int r_Tot = (-1);
    rep(i, 1, m)

    if (ed_0[Lch(i)].Flag == '1')
        r[++r_Tot] = (i - 1);

    return r;
}