#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std; 

int n; 
int fa[505], dep[505]; 
int vis[500005]; // 是否是树边
int type[500005]; // 边的种类
int id[505], ID[505][505]; 
vector<pair<int, int>> G[505]; 

int f[505]; 
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
bool merge(int x, int y) {
    if ((x = find(x)) == (y = find(y))) return 0; 
    return f[x] = y, 1; 
}

inline int ask(int u, int l, int r) {
    for (int i = 0; i < n; ++i) f[i] = i; 
    vector<int> w; 
    for (auto it : G[u]) {
        int v = it.first; 
        if (l <= v && v <= r) {
            assert(merge(u, v)); 
            w.push_back(it.second); 
        }
    }
    int base = 0; 
    for (int i = 1; i < n; ++i) 
        if (merge(fa[i], i)) base += (type[id[i]] == 1), w.push_back(id[i]); 
    assert(w.size() == n - 1); 
    return count_common_roads(w) > base; 
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
    memset(ID, -1, sizeof ID); ::n = n; 

    vector<int> w; 
    int m = u.size(); 
    for (int i = 0; i < m; ++i) G[u[i]].push_back({v[i], i}), G[v[i]].push_back({u[i], i}), ID[u[i]][v[i]] = ID[v[i]][u[i]] = i; 

    function<void(int, int)> dfs = [&](int x, int y) {
        dep[x] = dep[y] + 1, fa[x] = y; 
        for (auto it : G[x])
            if (!dep[it.first])
                vis[id[it.first] = it.second] = 1, 
                w.push_back(it.second), 
                dfs(it.first, x); 
    };
    dfs(0, n);
    int ans0 = count_common_roads(w); 

    for (int i = 0; i < m; ++i)
        if (!vis[i]) { // 非树边
            vector<int> tmp;
            for (int j = u[i], k = v[i]; j != k; tmp.push_back(id[j]), j = fa[j])
                if (dep[j] < dep[k]) swap(j, k); 

            for (int o : tmp) if (!type[o]) goto gg; 
            continue; 

        gg:;
            int mn = ans0, mx = ans0;
            vector<int> ans;
            for (int o : tmp)
                if (type[o]) { // 有被确定的，转一圈即可
                    vector<int> w2 = w; 
                    w2.erase(find(begin(w2), end(w2), o)); 
                    w2.push_back(i); 
                    int val = count_common_roads(w2); // 删掉这条确定的，加入这条非树边
                    for (int x : tmp) if (!type[x]) {
                        w2 = w, w2.erase(find(begin(w2), end(w2), x)), w2.push_back(i); 
                        if (count_common_roads(w2) == val) type[x] = type[o]; 
                        else type[x] = -type[o]; 
                    }
                    goto g2;
                }
            
            // 什么都不到
            for (int o : tmp) {
                vector<int> w2 = w;
                w2.erase(find(begin(w2), end(w2), o)); 
                w2.push_back(i); 
                int val = count_common_roads(w2); 
                ans.push_back(val), mn = min(mn, val), mx = max(mx, val); 
            }
            if (mn == mx) --mn; // 没有好东西
            for (int j = 0; j < tmp.size(); ++j)
                if (ans[j] == mn) type[tmp[j]] = 1; // 没它不行
                else type[tmp[j]] = -1; 
        g2:;
        }
    
    for (int i = 0; i < m; ++i) if (vis[i] && type[i] == 0) type[i] = 1; 
    // for (int i = 0; i < m; ++i) if (type[i] == 1) cout << i << " ";  cout << "\n"; 

    for (int i = 0; i < n; ++i) {
        int p = i + 1; 
        while (p < n) {
            if (!ask(i, p, n - 1)) break; 
            int l = p - 1, r = n; 
            while (l + 1 != r) {
                int mid = l + r >> 1; 
                if (ask(i, p, mid)) r = mid; 
                else l = mid; 
            }
            assert(ID[i][r] != -1); 
            assert(ask(i, p, r)); 
            type[ID[i][r]] = 1; 
            // cout << i << " " << p << " " << r << "\n"; 
            p = r + 1; 
        }
    }
    vector<int> ans; 
    for (int i = 0; i < m; ++i) if (type[i] == 1) ans.push_back(i); 
    // for (int i : ans) cout << i << " "; cout << "\n"; 
    return ans; 
}