1
#include <bits/stdc++.h>
2
// #ifdef LOCAL_GCC
3
#define print cout << format
4
// #endif
5
#define up(i,x,y) for (auto i=x;i<=y;i++)
6
#define upn(i,x,y) for (auto i=x;i<y;i++)
7
#define down(i,x,y) for (auto i=x;i>=y;i--)
8
#define elif else if
9
using ll=long long;
10
using namespace std;
11
struct dsu {
12
    int tot;
13
    vector<int> pa, size;
14
    dsu(int n) : pa(n+1), size(n+1, 1), tot(n) {
15
        iota(pa.begin(),pa.end(),0);
16
        size[0]=0;
17
    }
18

19
    int find(int x) { return pa[x]==x? x : pa[x]=find(pa[x]) ;}
20
    int operator[](int x) {return find(x);}
21

22
    void unite(int x, int y) {
23
        x=find(x),y=find(y);
24
        if (x==y) return;
25
        tot--;
26
        if (size[x]<size[y]) swap(x,y);
27
        pa[y]=x;
28
        size[x]+=size[y];
29
    }
30
};
31
void solve(){
32
    int n;
33
    cin>>n;
34
    dsu t={2*n};
35
    vector ans(0,0);
36
    ans.reserve(n);
37
    up(i,1,n) {
38
        int u,v;
39
        cin>>u>>v;
40
        if (t[u]==t[v]) continue;
41
        else{
42
            ans.push_back(i);
43
            t.unite(u,v);
44
        }
45
    }
46
    print("{}\n",ans.size());
47
    for (auto&&i:ans) print("{} ",i);
48
    print("\n");
49
}
50
int main(){
51
    ios::sync_with_stdio(false);
52
    cin.tie(nullptr);
53
    cout.tie(nullptr);
54
    int T=1;
55
    cin>>T;
56
    while(T--) solve();
57
}

1
#include <bits/stdc++.h>
2
// #ifdef LOCAL_GCC
3
#define print cout << format
4
// #endif
5
#define up(i,x,y) for (auto i=x;i<=y;i++)
6
#define upn(i,x,y) for (auto i=x;i<y;i++)
7
#define down(i,x,y) for (auto i=x;i>=y;i--)
8
#define elif else if
9
using ll=long long;
10
using namespace std;
11
template<typename T=int>
12
struct fenwick {
13
    int n;
14
    vector<T> t;
15
    fenwick(int _n): n(_n), t(_n+1){}
16

17
    T query(int p){
18
        T res=T{};
19
        while(p){
20
            res+=t[p];
21
            p-=(p&(-p));
22
        }
23
        return res;
24
    }
25
    T operator[](int p){
26
        return query(p);
27
    }
28
    T operator()(int l,int r){
29
        if (l>r) swap(l,r);
30
        return query(r)-query(l-1);
31
    }
32

33
    void add(int p,T x){
34
        while(p<=n){
35
            t[p]+=x;
36
            p+=(p&(-p));
37
        }
38
    }
39
};
40
void solve(){
41
    int n;
42
    cin>>n;
43
    vector a(n+1,0);
44
    fenwick l={2*n+1},r={2*n+1};
45
    int base=0;
46
    up(i,1,n){
47
        cin>>a[i];
48
        base+=r[2*n]-r[a[i]];
49
        r.add(a[i],1);
50
    }
51
    int ans=base;
52
    up(i,1,n){
53
        r.add(a[i],-1);
54
        int cur=l[2*n]-l[a[i]]+r[a[i]-1];
55
        int nxt=l[2*n]-l[2*n-a[i]]+r[2*n-a[i]-1];
56
        if (nxt<=cur){
57
            a[i]=2*n-a[i];
58
            ans+=nxt-cur;
59
        }
60
        l.add(a[i],1);
61
    }
62
    print("{}\n",ans);
63

64
}
65
int main(){
66
    ios::sync_with_stdio(false);
67
    cin.tie(nullptr);
68
    cout.tie(nullptr);
69
    int T=1;
70
    cin>>T;
71
    while(T--) solve();
72
}

1
()**))
2
  s   f(x)
3
()())) 3
4
()(()) 4
5
())))) 1
6
())()) 2
7
  xx

1
#include <bits/stdc++.h>
2
// #ifdef LOCAL_GCC
3
#define print cout << format
4
// #endif
5
#define up(i,x,y) for (auto i=x;i<=y;i++)
6
#define upn(i,x,y) for (auto i=x;i<y;i++)
7
#define down(i,x,y) for (auto i=x;i>=y;i--)
8
#define elif else if
9
using ll=long long;
10
using namespace std;
11
void solve(){
12
    int n;
13
    cin>>n;
14
    vector<char>res(n+1);
15
    int cl=-1,cr=-1;
16
    int l=1,r=n;
17
    while (l<=r){
18
        int mid=l+r>>1;
19
        cout<<"? "<<mid<<" ";
20
        up(i,1,mid) cout<<i<<" ";
21
        cout<<endl;
22
        int x;
23
        cin>>x;
24
        if (x) r=mid-1;
25
        else l=mid+1;
26
    }
27
    if (r==n){
28
        cl=n;
29
        cr=1;
30
    }else{
31
        cl=r;
32
        cr=r+1;
33
    }
34
    for (int i=1;i<n;i+=2){
35
        cout<<"? 6 "<<cl<<" "<<cr<<" "<<i<<" "<<i+1<<" "<<cr<<" "<<cr<<endl;
36
        int x;
37
        cin>>x;
38
        if (x==1) res[i]=res[i+1]=')';
39
        elif (x==2) res[i]=')',res[i+1]='(';
40
        elif (x==3) res[i]='(',res[i+1]=')';
41
        else res[i]=res[i+1]='(';
42
    }
43
    if (n&1){
44
        cout<<"? 2 "<<cl<<" "<<n<<endl;
45
        int x;
46
        cin>>x;
47
        if (x==1) res[n]=')';
48
        else res[n]='(';
49
    }
50
    cout<<"! ";
51
    up(i,1,n) cout<<res[i];
52
    cout<<endl;
53
}
54
int main(){
55
    // ios::sync_with_stdio(false);
56
    // cin.tie(nullptr);
57
    // cout.tie(nullptr);
58
    int T=1;
59
    cin>>T;
60
    while(T--) solve();
61
}