QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#385581#2830. Data Structureucup-team1209AC ✓292ms36624kbC++143.4kb2024-04-10 21:25:182024-04-10 21:25:18

Judging History

你现在查看的是最新测评结果

  • [2024-04-10 21:25:18]
  • 评测
  • 测评结果:AC
  • 用时:292ms
  • 内存:36624kb
  • [2024-04-10 21:25:18]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,y,x) for (int i=(y);i>=(x);i--)
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
void file() {
    #ifdef zqj
    freopen("a.in","r",stdin);
    #endif
}
typedef long long ll;
#define sz 202020

int n,m;
vector<int>st[sz];
vector<int>pos[sz];
set<int>num[3];

vector<pii>ans;
void output() {
    cout<<ans.size()<<'\n';
    for (auto [x,y]:ans) cout<<x<<' '<<y<<'\n';
}
void mov(int f,int t) {
    assert(f!=t);
    assert(st[f].size());
    assert(st[t].size()==0u||(st[t].size()==1u&&st[t][0]==st[f].back()));
    for (auto p:{f,t}) num[st[p].size()].erase(p);
    ans.push_back({f,t});
    int x=st[f].back();
    st[t].push_back(x),st[f].pop_back();
    rep(i,0,1) if (pos[x][i]==f) {pos[x][i]=t; break;}
    num[st[f].size()].insert(f);
    if (st[t].size()!=1u) num[st[t].size()].insert(t);
}
int ok(int x){return pos[x][0]==pos[x][1];}

void check(int x) {
    assert(!ok(x));
    int p0=pos[x][0],p1=pos[x][1];
    if (st[p1].size()==1u) swap(p0,p1);
    if (st[p0].size()==1u) {
        if (st[p1].size()==1u||st[p1][1]==x) {
            mov(p1,p0);
            if (st[p1].size()) check(st[p1][0]);
            return;
        }
        if (num[0].size()) {
            int pp=*(num[0].begin()),t=p1;
            while (233) {
                int y=st[t][1];
                t^=pos[y][0]^pos[y][1];
                if (st[t].size()==1u) return check(st[t][0]);
                if (st[t][1]==y) {
                    int yy=st[t][0];
                    mov(t,pp);
                    check(y);
                    check(yy);
                    return;
                }
            }
        }
    }
}

void work() {
    #define NO return cout<<"-1\n",void()
    rep(i,1,m) st[i].clear();
    rep(i,1,n) pos[i].clear();
    rep(i,0,2) num[i].clear();
    ans.clear();
    rep(i,1,m) {
        int k,x; cin>>k;
        rep(_,1,k) cin>>x,st[i].push_back(x),pos[x].push_back(i);
        if (k!=2||(k==2&&st[i][0]!=st[i][1])) num[k].insert(i);
    }
    if (n==m) {
        if (num[2].size()) NO;
        output();
        return;
    }
    rep(i,1,n) if (!ok(i)) check(i);
    if (num[1].size()||num[2].size()) {
        if (!num[0].size()) NO;
        while (num[1].size()) {
            int p=*(num[1].begin());
            check(st[p][0]);
        }
        assert(num[0].size());
        rep(i,1,n) if (!ok(i)&&st[pos[i][0]][1]==i&&st[pos[i][1]][1]==i) {
            int pp=*(num[0].begin()),p0=pos[i][0],p1=pos[i][1];
            mov(p0,pp),mov(p1,pp);
            check(st[p0].back());
            if (st[p1].size()&&!ok(st[p1][0])) check(st[p1].back());
            if (!num[0].size()) {
                assert(m==n+1);
                NO;
            }
        }
        rep(i,1,n) if (!ok(i)) {
            int pp=*(num[0].begin()),p0=pos[i][0],p1=pos[i][1];
            if (st[p0][1]!=i) swap(p0,p1);
            mov(p0,pp);
            check(st[p0].back());
            assert(num[0].size());
        }
        rep(i,1,n) assert(ok(i));
    }
    output();
}

int main() {
    file();
    ios::sync_with_stdio(false),cin.tie(0);
    while (cin>>n>>m) work();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 13164kb

input:

2 3
2 1 2
2 1 2
0
1 1
2 1 1
3 4
2 1 3
2 2 3
1 1
1 2

output:

3
1 3
2 3
1 2
0
-1

result:

ok 3 cases passed. max #moves/#balls = 1.500000000

Test #2:

score: 0
Accepted
time: 3ms
memory: 13196kb

input:

1 2
1 1
1 1
1 3
1 1
0
1 1
1 4
1 1
1 1
0
0
1 1
2 1 1
1 2
2 1 1
0
1 3
0
0
2 1 1

output:

1
1 2
1
1 3
1
1 2
0
0
0

result:

ok 6 cases passed. max #moves/#balls = 1.000000000

Test #3:

score: 0
Accepted
time: 0ms
memory: 13204kb

input:

2 4
1 1
1 2
1 2
1 1
2 5
1 1
1 2
0
1 1
1 2
2 6
0
1 1
0
1 1
1 2
1 2
2 4
1 2
1 1
1 1
1 2
2 5
1 1
0
1 2
1 2
1 1
2 6
1 2
0
1 1
0
1 1
1 2
2 4
1 1
1 2
1 2
1 1
2 5
0
1 2
1 1
1 1
1 2
2 6
1 1
0
1 2
1 2
0
1 1
2 3
2 2 1
1 1
1 2
2 4
2 2 1
1 1
0
1 2
2 5
1 1
0
1 2
2 1 2
0
2 3
1 2
2 1 2
1 1
2 4
1 1
2 2 1
1 2
0
2 5
...

output:

2
1 4
2 3
2
1 4
2 5
2
2 4
5 6
2
2 3
1 4
2
1 5
3 4
2
3 5
1 6
2
1 4
2 3
2
3 4
2 5
2
1 6
3 4
2
1 2
1 3
2
1 2
1 4
2
4 3
1 4
2
2 1
2 3
2
2 1
2 3
2
1 3
1 4
-1
3
2 1
3 1
2 3
3
2 1
4 1
2 4
-1
3
2 3
1 2
1 3
3
1 3
2 1
3 2
1
2 3
1
3 4
1
1 4
0
0
0

result:

ok 27 cases passed. max #moves/#balls = 1.500000000

Test #4:

score: 0
Accepted
time: 2ms
memory: 13152kb

input:

3 6
1 1
1 2
1 2
1 3
1 3
1 1
3 7
1 3
0
1 2
1 2
1 1
1 1
1 3
3 8
0
1 3
1 2
0
1 1
1 1
1 2
1 3
3 6
1 3
1 3
1 2
1 1
1 1
1 2
3 7
1 1
1 3
1 1
1 2
1 2
1 3
0
3 8
1 1
1 2
0
1 3
1 2
0
1 3
1 1
3 6
1 3
1 1
1 2
1 3
1 2
1 1
3 7
1 1
1 2
0
1 1
1 3
1 3
1 2
3 8
1 2
1 1
1 3
1 2
0
1 3
0
1 1
3 6
1 2
1 2
1 3
1 1
1 1
1 3
3 ...

output:

3
1 6
2 3
4 5
3
5 6
3 4
1 7
3
5 6
3 7
2 8
3
4 5
3 6
1 2
3
1 3
4 5
2 6
3
1 8
2 5
4 7
3
2 6
3 5
1 4
3
1 4
2 7
5 6
3
2 8
1 4
3 6
3
4 5
1 2
3 6
3
2 5
4 7
3 6
3
3 4
1 2
5 8
3
1 6
2 5
3 4
3
5 6
1 3
4 7
3
6 7
2 5
4 8
3
1 2
3 6
4 5
3
1 3
5 6
2 7
3
3 7
2 4
6 8
3
1 5
4 6
2 3
3
4 7
1 5
2 3
3
1 6
5 7
4 8
3
4 6
...

result:

ok 180 cases passed. max #moves/#balls = 1.333333333

Test #5:

score: 0
Accepted
time: 4ms
memory: 13212kb

input:

4 8
1 3
1 3
1 4
1 1
1 2
1 1
1 4
1 2
4 9
1 3
0
1 2
1 1
1 4
1 1
1 4
1 2
1 3
4 10
1 1
1 3
1 3
1 2
1 2
0
1 1
1 4
1 4
0
4 8
1 4
1 3
1 2
1 2
1 1
1 4
1 1
1 3
4 9
1 4
1 3
1 1
1 3
1 4
1 2
1 1
1 2
0
4 10
1 4
1 1
1 2
1 3
0
0
1 2
1 1
1 3
1 4
4 8
1 2
1 4
1 3
1 4
1 2
1 3
1 1
1 1
4 9
1 1
1 4
1 3
1 2
1 3
1 2
0
1 4
...

output:

4
4 6
5 8
1 2
3 7
4
4 6
3 8
1 9
5 7
4
1 7
4 5
2 3
8 9
4
5 7
3 4
2 8
1 6
4
3 7
6 8
2 4
1 5
4
2 8
3 7
4 9
1 10
4
7 8
1 5
3 6
2 4
4
1 9
4 6
3 5
2 8
4
4 7
2 3
8 10
5 6
4
1 3
4 7
2 8
5 6
4
2 9
1 7
5 6
3 4
4
2 10
1 9
4 5
3 8
4
2 5
1 3
4 8
6 7
4
1 5
3 8
4 9
2 7
4
3 6
2 9
5 7
1 8
4
2 8
6 7
1 5
3 4
4
2 8
6 7...

result:

ok 1575 cases passed. max #moves/#balls = 1.500000000

Test #6:

score: 0
Accepted
time: 32ms
memory: 13100kb

input:

5 10
1 1
1 4
1 2
1 4
1 5
1 2
1 3
1 5
1 1
1 3
5 11
1 1
1 3
1 1
1 2
1 5
1 2
0
1 5
1 4
1 3
1 4
5 12
1 2
0
1 1
1 5
1 2
1 4
1 3
1 4
0
1 5
1 3
1 1
5 10
1 3
1 5
1 1
1 1
1 2
1 4
1 4
1 5
1 2
1 3
5 11
1 3
1 5
1 2
1 2
1 4
1 3
1 1
1 1
0
1 4
1 5
5 12
1 3
1 4
1 2
0
1 5
1 1
1 2
1 1
1 4
1 5
0
1 3
5 10
1 4
1 5
1 3
1...

output:

5
1 9
3 6
7 10
2 4
5 8
5
1 3
4 6
2 10
9 11
5 8
5
3 12
1 5
7 11
6 8
4 10
5
3 4
5 9
1 10
6 7
2 8
5
7 8
3 4
1 6
5 10
2 11
5
6 8
3 7
1 12
2 9
5 10
5
4 7
8 9
3 10
1 5
2 6
5
2 4
1 6
5 7
8 9
3 11
5
1 7
2 3
10 11
8 9
4 5
5
8 10
4 5
6 7
2 9
1 3
5
6 7
1 11
4 5
2 3
8 9
5
2 6
4 11
8 9
1 7
3 10
5
7 8
1 10
4 5
3 ...

result:

ok 17010 cases passed. max #moves/#balls = 1.400000000

Test #7:

score: 0
Accepted
time: 38ms
memory: 13148kb

input:

6 11
1 5
1 6
1 2
1 4
1 1
1 5
1 4
1 3
1 6
2 2 3
1 1
6 9
1 6
2 1 1
2 4 4
1 2
2 6 2
0
2 5 3
0
2 5 3
6 6
2 4 4
2 5 6
2 3 6
2 2 2
2 3 5
2 1 1
6 8
2 2 1
2 3 4
1 6
2 1 2
2 3 5
0
1 6
2 4 5
6 9
1 6
1 4
1 3
1 5
2 3 1
2 4 2
2 2 1
1 6
1 5
6 7
1 4
2 2 3
2 1 6
2 1 4
2 6 2
2 5 5
1 3
6 8
1 2
2 3 5
1 1
2 4 4
0
2 5 1...

output:

6
5 11
10 8
3 10
4 7
1 6
2 9
5
5 4
1 5
7 1
9 1
7 9
-1
8
3 7
5 3
8 3
2 8
2 5
1 2
4 1
2 4
7
4 9
1 8
5 1
7 1
6 7
2 6
3 5
5
2 7
5 2
3 5
4 1
3 4
5
6 3
2 6
7 1
8 7
2 8
5
1 9
2 6
3 10
5 7
8 11
6
1 6
1 5
3 1
4 1
2 4
2 3
-1
6
7 12
2 3
1 11
5 10
6 8
4 9
3
7 6
5 7
3 5
8
7 2
1 2
1 9
4 7
3 4
5 1
8 1
5 8
6
5 9
2 ...

result:

ok 14285 cases passed. max #moves/#balls = 1.500000000

Test #8:

score: 0
Accepted
time: 39ms
memory: 13144kb

input:

7 10
2 4 3
1 1
2 2 2
2 4 3
2 7 7
2 6 6
2 5 5
0
1 1
0
7 12
1 2
1 6
1 6
1 5
2 4 1
1 1
2 4 3
1 7
1 5
1 3
1 2
1 7
7 15
1 4
1 6
1 2
1 4
1 6
1 5
1 7
1 1
1 3
0
1 7
1 5
1 1
1 3
1 2
7 7
2 7 3
2 2 3
2 5 7
2 1 1
2 6 6
2 2 5
2 4 4
7 12
2 3 2
1 7
2 6 3
1 4
1 2
1 5
1 1
1 4
1 5
1 1
1 6
1 7
7 14
2 3 5
0
1 2
1 6
1 4...

output:

4
2 9
1 2
4 2
1 4
7
5 6
1 11
7 10
5 7
4 9
2 3
8 12
7
8 13
3 15
9 14
1 4
6 12
2 5
7 11
-1
7
7 10
1 5
3 1
3 11
4 8
6 9
2 12
7
10 13
3 14
1 7
1 6
5 8
4 12
9 11
7
1 6
3 1
10 1
7 3
8 10
4 8
4 7
7
5 12
7 10
8 9
2 11
6 2
3 6
1 4
7
2 10
5 11
7 1
3 1
3 5
7 9
4 6
7
4 1
4 6
2 7
5 9
8 2
10 2
8 10
7
4 5
3 8
14 1...

result:

ok 12500 cases passed. max #moves/#balls = 1.428571429

Test #9:

score: 0
Accepted
time: 37ms
memory: 13092kb

input:

8 16
1 2
0
1 5
1 8
1 1
1 5
2 4 4
1 8
1 6
1 1
1 2
0
2 7 7
1 3
1 6
1 3
8 13
1 8
1 4
1 2
1 6
2 1 3
2 1 3
1 7
1 2
1 5
1 6
1 8
2 4 5
1 7
8 9
2 1 3
2 4 5
2 7 2
2 7 8
2 4 8
2 1 6
2 5 2
2 6 3
0
8 17
1 1
1 4
1 3
1 7
1 2
1 2
1 7
1 5
1 3
1 4
1 6
1 8
1 5
1 6
1 8
1 1
0
8 15
1 6
1 4
0
1 5
1 7
1 3
1 2
1 8
1 6
1 7
...

output:

6
5 10
1 11
14 16
3 6
9 15
4 8
9
3 8
12 9
2 12
4 10
7 13
1 11
5 1
6 1
5 6
-1
8
1 16
5 6
3 9
2 10
8 13
11 14
4 7
12 15
9
7 15
6 14
13 3
11 3
2 11
4 13
1 9
5 10
8 12
9
8 1
9 1
2 8
2 9
3 2
7 2
4 3
5 7
4 5
7
2 6
1 2
8 2
10 1
4 10
5 8
4 5
8
7 9
2 11
4 16
3 8
10 12
5 13
1 6
14 15
10
5 8
3 5
7 5
4 3
4 7
1 ...

result:

ok 11111 cases passed. max #moves/#balls = 1.500000000

Test #10:

score: 0
Accepted
time: 40ms
memory: 13168kb

input:

9 13
1 2
2 4 5
2 5 4
2 2 9
1 8
1 3
1 1
1 3
1 1
2 7 6
1 9
1 8
2 7 6
9 13
1 4
2 5 6
2 7 5
2 9 3
1 4
2 9 7
0
2 8 6
2 1 3
0
1 2
1 2
2 8 1
9 18
1 4
1 7
1 7
1 9
1 8
1 8
1 2
1 3
1 6
1 2
1 1
1 3
1 5
1 1
1 6
1 5
1 4
1 9
9 13
0
2 6 7
2 2 2
1 3
2 6 8
2 9 1
2 1 4
1 9
2 8 7
0
1 4
1 3
2 5 5
9 17
1 9
2 1 3
1 2
1 5...

output:

11
7 9
4 11
1 4
6 8
5 12
10 1
13 1
10 13
3 5
2 3
2 5
11
11 12
1 5
4 1
9 1
8 7
2 7
3 2
6 3
4 6
13 9
8 13
9
11 14
7 10
8 12
1 17
13 16
9 15
2 3
5 6
4 18
8
4 12
7 11
6 7
6 8
2 1
9 1
5 9
2 5
9
3 11
2 7
6 12
2 6
4 10
9 17
15 16
5 14
1 13
13
1 3
10 3
1 10
5 1
6 1
9 6
5 9
11 4
7 11
7 4
8 5
2 8
2 5
8
5 12
1...

result:

ok 10000 cases passed. max #moves/#balls = 1.444444444

Test #11:

score: 0
Accepted
time: 38ms
memory: 13156kb

input:

10 19
1 1
1 3
1 10
1 8
1 1
1 4
1 2
1 2
1 5
1 7
1 5
2 6 6
1 7
1 3
1 4
1 9
1 10
1 8
1 9
10 19
1 8
1 10
2 7 7
1 2
1 5
1 9
1 1
0
1 6
1 9
1 1
1 6
1 5
0
1 2
1 10
2 4 4
2 3 3
1 8
10 10
2 5 5
2 2 3
2 8 4
2 2 7
2 6 9
2 3 10
2 10 1
2 6 4
2 7 8
2 9 1
10 19
1 4
1 5
1 4
1 9
2 3 9
1 10
1 1
1 7
1 6
1 8
1 10
1 5
1 ...

output:

9
1 5
7 8
2 14
6 15
9 11
10 13
4 18
16 19
3 17
7
7 11
4 15
5 13
9 12
1 19
6 10
2 16
-1
10
7 17
13 16
5 4
5 19
1 3
2 12
9 14
8 18
10 15
6 11
11
4 19
5 6
5 13
10 12
15 16
3 17
1 9
8 14
18 1
7 18
7 1
7
8 16
12 18
6 13
10 14
1 3
17 19
5 9
10
9 16
4 6
8 12
7 14
10 17
3 13
5 3
1 5
2 15
11 18
10
8 12
10 13...

result:

ok 9090 cases passed. max #moves/#balls = 1.500000000

Test #12:

score: 0
Accepted
time: 39ms
memory: 13156kb

input:

11 15
2 11 11
2 3 3
1 2
0
2 8 5
1 2
2 6 4
2 4 5
1 1
1 1
1 9
1 10
2 8 6
2 7 7
2 9 10
11 17
2 4 8
1 11
2 6 7
1 9
1 9
1 5
1 2
1 2
1 5
1 10
1 3
1 1
1 11
2 10 8
1 1
2 3 7
2 4 6
11 21
1 10
1 6
1 3
1 9
1 8
1 1
1 5
1 10
1 5
1 4
1 8
1 9
1 11
1 6
1 11
1 7
1 1
1 4
2 2 2
1 7
1 3
11 15
1 5
1 1
1 2
2 3 3
2 10 7
0...

output:

9
9 10
3 6
15 12
11 15
5 3
8 3
7 8
13 7
5 13
13
12 15
7 8
3 7
16 7
11 16
17 3
14 11
1 11
1 17
10 14
6 9
4 5
2 13
10
6 17
3 21
10 18
7 9
2 14
16 20
5 11
4 12
1 8
13 15
11
2 9
15 3
12 11
8 12
8 15
1 10
13 1
14 1
7 14
5 7
5 13
10
16 8
7 10
5 11
5 16
14 18
3 6
12 17
4 15
2 19
9 13
11
7 10
7 12
1 7
4 7
3...

result:

ok 8333 cases passed. max #moves/#balls = 1.363636364

Test #13:

score: 0
Accepted
time: 44ms
memory: 13224kb

input:

12 25
1 9
1 10
1 4
1 7
1 5
1 3
1 6
1 1
1 12
1 3
1 2
1 9
1 11
1 2
0
1 10
1 7
1 12
1 11
1 4
1 6
1 5
1 1
1 8
1 8
12 19
1 2
1 12
2 8 8
2 1 3
0
2 3 4
1 5
2 11 11
2 1 5
2 9 6
1 12
1 7
1 7
2 6 9
1 2
1 4
1 10
1 10
0
12 14
2 2 4
2 8 8
2 1 3
2 9 9
2 6 12
2 6 1
0
2 10 10
2 5 5
2 3 12
0
2 4 7
2 7 2
2 11 11
12 1...

output:

12
8 23
11 14
6 10
3 20
5 22
7 21
4 17
24 25
1 12
2 16
13 19
9 18
11
1 15
6 16
4 6
9 7
4 9
12 13
17 18
2 11
10 1
14 10
1 14
9
5 7
10 7
3 10
6 3
5 6
13 5
12 13
1 12
1 5
10
8 5
14 5
3 8
1 3
12 13
7 13
1 7
4 12
6 4
6 14
12
11 24
7 14
5 19
1 10
12 21
16 25
2 6
4 20
8 22
9 17
3 13
15 18
11
2 12
4 5
8 2
1...

result:

ok 7692 cases passed. max #moves/#balls = 1.416666667

Test #14:

score: 0
Accepted
time: 41ms
memory: 13216kb

input:

13 15
2 8 8
2 6 6
2 1 1
2 3 3
2 11 11
2 2 5
2 5 13
1 4
1 12
2 2 13
1 12
2 10 10
1 4
2 9 9
2 7 7
13 21
2 11 11
1 9
1 2
1 9
1 13
1 1
1 13
1 5
2 12 8
2 7 7
1 5
1 6
1 6
2 4 3
1 1
0
2 10 10
1 2
2 4 3
0
2 8 12
13 24
1 8
1 7
1 6
1 3
1 5
1 9
1 2
1 13
1 2
1 12
2 10 10
1 3
1 1
1 8
1 4
1 12
1 6
1 5
1 7
1 4
2 1...

output:

6
8 13
9 11
7 8
10 8
6 7
6 10
12
6 15
3 18
8 11
12 13
2 4
5 7
14 2
19 2
14 19
9 3
21 9
3 21
11
13 23
7 9
4 12
15 20
5 18
3 17
2 19
1 14
6 24
10 16
8 22
12
8 15
10 6
9 7
9 10
13 20
3 17
4 16
1 11
2 14
5 1
19 1
5 19
12
10 16
1 27
9 18
12 26
4 20
5 23
8 14
3 6
7 17
11 19
2 25
21 22
13
3 17
11 15
2 9
5 ...

result:

ok 7142 cases passed. max #moves/#balls = 1.384615385

Test #15:

score: 0
Accepted
time: 45ms
memory: 13228kb

input:

14 24
1 3
1 11
1 2
1 7
1 5
0
1 11
2 4 8
2 12 5
2 9 4
1 3
1 10
2 12 9
1 1
0
2 13 13
1 2
1 7
1 6
1 10
1 14
1 1
1 6
2 8 14
14 27
1 8
1 10
1 1
1 1
1 12
1 14
1 6
1 11
1 5
1 12
1 7
1 4
1 10
1 14
1 7
1 9
1 2
1 6
1 11
1 9
2 3 3
1 2
1 4
1 13
1 8
1 5
1 13
14 22
1 14
2 7 5
1 3
1 10
1 9
1 9
2 13 5
2 12 2
2 6 6
...

output:

13
14 22
3 17
1 11
9 5
24 21
8 24
10 8
13 10
9 13
19 23
4 18
12 20
2 7
13
3 4
17 22
12 23
9 26
7 18
11 15
1 25
16 20
2 13
8 19
5 10
24 27
6 14
12
19 22
8 13
8 11
3 15
5 6
4 21
14 20
1 17
2 1
7 1
10 2
7 10
13
4 15
16 25
6 21
7 12
11 18
2 19
14 17
1 3
9 10
8 20
13 1
23 1
13 23
14
8 19
4 9
7 23
3 28
22...

result:

ok 6666 cases passed. max #moves/#balls = 1.357142857

Test #16:

score: 0
Accepted
time: 45ms
memory: 13156kb

input:

15 22
0
2 6 13
1 13
1 4
1 8
1 8
0
2 10 3
2 11 15
2 15 7
1 5
2 2 12
2 11 12
1 6
1 7
2 9 9
1 5
2 1 1
2 3 10
2 14 14
1 4
1 2
15 24
1 2
1 4
2 8 11
1 9
0
1 1
2 5 5
1 9
2 6 6
1 12
1 3
1 3
2 7 13
2 11 10
1 14
1 12
2 10 4
1 15
2 8 7
1 2
0
1 1
1 15
2 13 14
15 24
0
1 14
1 14
2 1 1
1 10
1 12
1 5
2 10 6
1 13
1 ...

output:

14
13 1
12 1
12 22
10 15
9 10
9 13
4 21
11 17
2 3
2 14
5 6
8 2
19 8
2 19
13
6 22
1 20
11 12
17 2
14 17
3 14
24 15
13 24
19 13
3 19
4 8
10 16
18 23
12
10 13
7 12
8 18
5 8
15 16
23 24
6 22
9 14
2 3
17 1
19 1
17 19
15
6 17
2 3
14 3
10 6
16 6
5 16
2 5
11 2
15 2
10 15
12 14
11 12
7 10
13 10
7 13
16
15 19...

result:

ok 6250 cases passed. max #moves/#balls = 1.400000000

Test #17:

score: 0
Accepted
time: 43ms
memory: 13216kb

input:

16 23
1 3
1 9
0
1 9
1 14
1 4
2 5 14
1 10
2 16 5
2 6 6
2 1 1
2 16 11
2 12 12
1 2
1 4
0
2 8 8
2 11 13
1 7
1 10
2 2 15
2 3 15
2 7 13
16 29
0
1 6
1 3
1 7
1 14
1 12
1 9
1 3
1 10
1 14
1 13
1 2
2 6 9
1 4
1 2
2 5 1
1 8
1 16
1 4
2 1 5
1 11
1 7
2 8 10
1 15
1 12
1 11
1 15
1 16
1 13
16 28
1 13
1 8
1 9
1 12
2 15...

output:

14
22 3
21 3
14 21
1 22
6 15
18 1
23 1
19 23
12 18
7 5
9 7
9 12
2 4
8 20
17
12 15
3 8
14 19
13 7
2 13
4 22
23 9
17 23
21 26
6 25
11 29
5 10
24 27
18 28
16 1
20 16
1 20
16
13 20
7 25
16 27
6 28
19 26
12 23
9 22
2 14
24 3
15 24
10 21
4 17
1 11
5 1
18 1
5 18
15
15 21
10 19
8 14
12 18
1 13
7 23
9 1
17 1...

result:

ok 5882 cases passed. max #moves/#balls = 1.375000000

Test #18:

score: 0
Accepted
time: 47ms
memory: 13160kb

input:

17 33
1 12
2 15 4
1 5
1 13
0
1 6
1 17
1 16
1 7
1 11
1 13
1 17
1 1
1 11
1 12
1 9
1 3
1 7
1 5
1 3
1 2
1 9
1 14
2 15 4
1 1
1 10
1 10
1 8
1 2
1 16
1 14
1 8
1 6
17 23
1 9
2 13 17
1 3
1 13
1 10
2 15 16
2 12 12
2 14 4
2 5 15
1 9
1 7
1 6
2 8 8
1 2
2 4 11
1 11
2 16 5
2 2 10
1 3
1 6
2 1 1
2 14 17
1 7
17 20
2 ...

output:

18
13 25
21 29
17 20
3 19
6 33
9 18
28 32
16 22
26 27
10 14
1 15
4 11
23 31
8 30
7 12
2 1
24 1
2 24
16
3 19
12 20
11 23
1 10
18 5
14 18
15 16
8 15
2 1
22 1
8 22
2 4
17 2
6 17
9 6
9 2
15
6 17
11 6
20 6
5 11
16 5
14 16
9 14
9 20
4 7
13 7
4 13
2 4
18 2
10 18
4 10
18
30 1
7 1
7 27
26 30
25 28
9 21
5 11
...

result:

ok 5555 cases passed. max #moves/#balls = 1.352941176

Test #19:

score: 0
Accepted
time: 47ms
memory: 13100kb

input:

18 19
2 8 5
2 7 11
2 1 13
2 2 2
0
2 17 11
2 14 6
2 18 18
2 3 12
2 4 3
2 8 12
2 6 14
2 9 16
2 13 1
2 15 15
2 9 16
2 10 10
2 5 4
2 7 17
18 26
2 16 4
2 10 15
1 7
1 13
1 11
1 11
2 15 10
1 14
1 5
1 8
2 9 3
2 2 9
2 4 12
1 13
1 1
1 1
1 17
1 5
2 16 6
1 7
1 8
2 12 6
1 17
2 18 3
1 14
2 2 18
18 23
2 16 16
2 18...

output:

19
2 5
6 5
19 6
2 19
9 2
11 2
10 9
18 10
1 18
1 11
13 1
16 1
13 16
14 13
3 14
3 13
7 3
12 7
3 12
21
15 16
9 18
3 20
10 21
5 6
4 14
8 25
17 23
11 3
24 3
12 11
26 24
12 26
19 4
22 4
13 22
1 13
1 19
7 1
2 7
2 1
14
10 12
6 13
16 23
11 6
15 6
2 11
19 2
7 19
4 15
20 4
7 20
17 7
14 17
14 7
-1
16
5 16
2 5
1...

result:

ok 5263 cases passed. max #moves/#balls = 1.388888889

Test #20:

score: 0
Accepted
time: 47ms
memory: 13224kb

input:

19 25
2 8 13
0
1 16
1 5
2 18 13
2 4 7
0
2 17 1
2 12 16
2 12 4
2 19 15
2 1 8
1 3
1 7
2 6 2
2 2 9
2 18 14
1 11
2 10 10
2 15 17
2 6 14
1 5
2 9 19
1 11
1 3
19 34
1 12
1 16
1 16
1 7
1 6
2 4 4
1 8
1 18
2 9 19
1 11
1 13
1 14
1 7
1 6
1 3
1 14
2 9 5
1 11
1 15
1 1
1 3
2 19 1
1 17
1 17
1 13
1 2
1 12
1 8
1 15
1...

output:

20
13 25
4 22
6 14
10 6
9 3
9 10
18 24
1 2
5 2
12 1
8 12
20 8
11 20
23 11
16 23
15 16
17 4
21 4
15 21
5 17
18
22 20
9 22
26 32
15 21
17 33
9 17
5 14
4 13
7 28
30 34
10 18
1 27
11 25
12 16
19 29
2 3
23 24
8 31
-1
21
24 25
5 7
17 23
14 19
18 21
2 9
11 27
1 2
4 2
15 1
8 3
6 3
6 15
20 4
8 20
13 5
22 5
1...

result:

ok 5000 cases passed. max #moves/#balls = 1.368421053

Test #21:

score: 0
Accepted
time: 44ms
memory: 13172kb

input:

20 36
1 3
1 19
1 18
1 19
1 2
1 4
1 17
2 5 6
1 1
1 12
1 14
1 20
1 11
1 13
1 7
1 15
1 16
1 3
1 1
1 16
1 11
1 4
1 8
1 15
2 9 5
1 8
1 13
1 7
1 12
1 2
2 10 10
1 17
1 18
1 14
1 20
2 6 9
20 27
2 7 13
2 6 10
0
2 11 8
2 11 2
0
1 17
2 1 1
1 15
1 19
1 19
1 14
2 4 5
1 14
2 12 8
2 7 6
2 2 12
2 3 20
2 18 20
2 3 4...

output:

20
9 19
5 30
1 18
6 22
15 28
23 26
13 21
10 29
14 27
11 34
16 24
17 20
7 32
3 33
2 4
12 35
25 1
36 25
8 36
8 1
22
12 14
9 22
26 27
7 25
10 11
13 3
24 3
20 13
19 6
18 6
18 20
19 24
4 7
15 7
17 15
5 17
4 5
1 4
23 4
2 23
16 2
1 16
21
12 16
21 28
7 13
14 24
2 10
20 22
9 17
18 26
4 11
8 29
23 30
3 2
19 2...

result:

ok 4761 cases passed. max #moves/#balls = 1.300000000

Test #22:

score: 0
Accepted
time: 24ms
memory: 13172kb

input:

70 79
2 13 14
2 49 46
1 43
2 27 27
2 5 5
2 63 50
2 63 15
2 61 25
2 17 39
2 44 26
2 15 45
2 65 2
2 64 6
2 2 28
2 55 60
2 13 68
1 40
2 30 30
1 62
2 41 60
2 16 25
1 69
1 62
2 28 23
2 46 49
2 26 57
1 35
2 66 66
2 10 69
2 33 55
1 10
2 54 9
1 32
2 11 12
1 40
1 7
1 29
2 33 54
2 12 11
2 22 1
1 29
2 6 64
2 2...

output:

79
36 45
29 22
29 31
37 41
33 75
27 62
17 35
3 47
44 50
19 23
40 3
52 3
63 40
9 63
60 17
26 17
10 26
72 10
9 72
52 60
32 9
61 9
38 32
20 19
15 19
30 15
30 38
79 27
68 27
20 68
78 61
78 79
1 20
65 20
16 65
1 16
8 1
21 1
69 8
67 29
55 29
55 69
54 67
21 54
11 21
74 21
7 11
73 30
6 30
6 7
76 74
51 76
48...

result:

ok 1000 cases passed. max #moves/#balls = 1.500000000

Test #23:

score: 0
Accepted
time: 34ms
memory: 13404kb

input:

89 125
2 6 86
1 11
1 43
1 77
1 27
2 72 88
1 52
2 26 75
1 77
2 89 86
1 60
1 18
2 20 20
1 25
2 57 75
1 3
1 55
2 38 19
2 76 2
2 22 24
1 3
2 61 61
2 39 59
2 42 74
1 56
2 71 71
1 68
2 79 87
2 81 67
1 25
2 66 21
1 37
1 70
2 40 83
1 60
1 48
1 52
2 22 24
2 62 62
1 84
2 41 23
1 69
2 32 26
1 36
1 15
2 88 72
1...

output:

88
16 21
48 92
54 93
2 105
79 88
59 96
57 107
45 114
85 91
12 108
14 30
5 47
73 116
51 78
56 112
44 87
32 117
19 2
67 2
34 67
34 77
70 19
63 106
63 70
3 75
110 113
82 118
61 98
36 94
62 76
7 37
17 123
25 90
95 109
11 35
27 122
42 52
33 115
83 119
4 9
40 64
49 3
102 3
80 102
49 80
55 4
60 4
58 55
58 ...

result:

ok 100 cases passed. max #moves/#balls = 1.169811321

Test #24:

score: 0
Accepted
time: 260ms
memory: 36624kb

input:

199990 199994
2 112787 58235
2 74630 28941
2 167642 28933
2 133872 119903
2 134119 187247
2 12074 126849
2 172463 191232
2 69306 129651
2 85342 121061
2 31874 148765
2 6567 39825
2 70847 178127
2 161417 173942
2 60884 49005
2 10700 112396
2 134185 131889
2 62930 176558
2 153356 48329
2 88968 136672
...

output:

249866
33532 199993
149868 199993
55718 149868
55718 174021
40140 55718
154492 55718
98071 154492
33532 98071
3409 40140
127577 3409
183763 33532
146781 33532
127577 146781
177569 183763
39870 177569
128051 39870
40416 128051
47653 40416
24457 47653
139428 24457
94458 139428
3940 127577
78541 127577...

result:

ok 1 cases passed. max #moves/#balls = 1.249392470

Test #25:

score: 0
Accepted
time: 273ms
memory: 36576kb

input:

199900 199939
2 159852 65847
2 26090 50275
2 87513 124862
2 86896 171149
2 108960 21092
2 60944 176432
2 64408 168417
2 110938 48609
2 30886 178149
2 180183 52005
2 185615 173446
2 91034 36919
2 121714 75547
2 97679 89549
2 161524 190571
2 129781 26065
2 726 162459
2 28052 166745
2 193665 65435
2 45...

output:

249613
106581 195508
61879 106581
58652 199938
173762 199938
61879 173762
10636 58652
101776 61879
53630 61879
160710 53630
38522 160710
10636 38522
183655 10636
154767 10636
42645 154767
36502 42645
36502 101776
139484 183655
148363 36502
17420 36502
98577 17420
145079 98577
139484 145079
65955 148...

result:

ok 1 cases passed. max #moves/#balls = 1.248689345

Test #26:

score: 0
Accepted
time: 282ms
memory: 36500kb

input:

199000 199158
2 87128 180318
2 51427 22755
2 151883 144846
2 86404 42933
2 86031 56171
2 97601 190366
2 100929 91717
2 10606 53797
2 151688 90226
2 65599 83910
2 159670 153323
2 98395 126956
2 104190 188119
2 134860 5110
2 82527 59574
2 185228 58544
2 131591 9348
2 88390 99580
2 79913 120984
2 12854...

output:

248620
83406 199157
84174 199157
26569 84174
26569 188145
51106 83406
52620 26569
39533 26569
39533 51106
146489 39533
5736 39533
105904 5736
87709 105904
52620 87709
154600 146489
101799 154600
140533 101799
170499 140533
61933 52620
37206 52620
37206 170499
175514 37206
147032 37206
116054 147032
...

result:

ok 1 cases passed. max #moves/#balls = 1.249346734

Test #27:

score: 0
Accepted
time: 292ms
memory: 36032kb

input:

190000 195490
2 57925 137657
2 115225 31941
2 113825 126389
2 86640 44883
2 54487 34585
2 118366 61471
2 120619 96922
1 140665
2 42131 138488
2 115971 83797
2 79814 139047
2 182772 4122
2 134485 135722
2 83056 53620
2 4840 71513
2 58767 175090
2 55378 47553
2 158331 65564
2 2231 167672
2 45248 44008...

output:

234894
171028 51311
63100 852
126434 852
126434 171028
148807 1964
166960 1964
63100 166960
100765 2210
1365 2210
1365 148807
87660 1365
94533 1365
30322 94533
30322 100765
148727 2559
86374 2559
152516 86374
87660 152516
65549 148727
57090 3305
149132 3305
65549 149132
68780 57090
78644 3407
128694...

result:

ok 1 cases passed. max #moves/#balls = 1.236284211

Test #28:

score: 0
Accepted
time: 157ms
memory: 28060kb

input:

100000 150784
1 11363
2 48695 10015
1 45261
0
0
2 59469 34868
2 37754 54971
2 1159 2258
2 36656 7427
1 86418
0
2 58664 20429
1 53392
1 61881
2 17499 14399
1 31182
1 7141
0
2 58765 17577
1 21750
2 55759 24096
0
0
2 68221 45178
1 34307
1 952
0
1 37862
1 31349
2 79909 53730
2 61993 40470
0
1 8272
2 824...

output:

111036
111937 43798
56855 111937
27095 32591
27095 103272
131140 4
150754 4
78320 150754
92422 131480
92422 131140
23954 65389
18074 5
145511 5
23954 145511
118111 18074
118111 139104
56699 110128
145196 56699
46437 145196
75012 132794
7207 75012
25486 7207
68460 11
50840 11
19502 50840
109500 19502...

result:

ok 1 cases passed. max #moves/#balls = 1.110360000

Test #29:

score: 0
Accepted
time: 249ms
memory: 36596kb

input:

199998 200000
2 197320 165241
2 136684 67821
2 38136 196111
2 36675 168634
2 193814 85383
2 188893 178378
2 107377 34791
2 77322 157440
2 51337 91683
2 141729 123337
2 88834 166216
2 172041 99918
2 81678 190214
2 145905 79139
2 184733 143722
2 20662 175460
2 73374 152647
2 111949 12058
2 7347 64349
...

output:

250095
171410 199999
181365 199999
97712 171410
52612 97712
119503 52612
138016 119503
28740 138016
91173 200000
21514 200000
169576 21514
36185 169576
8836 36185
74434 8836
28740 74434
77064 91173
11747 28740
130769 28740
77064 130769
185560 11747
193153 77064
72711 77064
77786 72711
77786 185560
1...

result:

ok 1 cases passed. max #moves/#balls = 1.250487505