QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#223929#2830. Data Structureucup-team1004AC ✓122ms27188kbC++142.7kb2023-10-22 21:05:492023-10-22 21:05:49

Judging History

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

  • [2023-10-22 21:05:49]
  • 评测
  • 测评结果:AC
  • 用时:122ms
  • 内存:27188kb
  • [2023-10-22 21:05:49]
  • 提交

answer

#include <cstdio>
#include <vector>
using namespace std;

int n, m;

vector<vector<int>> s;
vector<vector<pair<int, int>>> pos;
vector<pair<int, int>> ans;
vector<int> empty;

void move(int i, int j) {
  int c = s[i].back();
  s[j].push_back(c);
  s[i].pop_back();
  if (s[i].size() == 0) {
    empty.push_back(i);
  }
  int id = i == pos[c][1].second ? 1 : 0;
  pos[c][id].first = s[j].size() - 1;
  pos[c][id].second = j;
  ans.push_back(make_pair(i + 1, j + 1));
}

bool solve_chain(int start) {
  int ci = start, ch = 0;
  while (true) {
    int cc = s[ci][ch], id = ci == pos[cc][1].second ? 1 : 0,
        chp = pos[cc][1 - id].first, cip = pos[cc][1 - id].second;
    if (s[cip].size() == 1) {
      if (s[ci].size() == 1) {
        move(ci, cip);
        return true;
      } else {
        return solve_chain(cip);
      }
    } else {
      if (s[ci].size() == 1 && chp == 1) {
        move(cip, ci);
      }
      if (ch == 0 || chp == 0) {
        ci = cip;
        ch = 1 - chp;
      } else {
        if (empty.size() == 0) {
          return false;
        } else {
          int tmp = empty.back();
          empty.pop_back();
          move(ci, tmp);
          solve_chain(ci);
          return solve_chain(tmp);
        }
      }
    }
  }
}

int main() {
  while (scanf("%d%d", &n, &m) != -1) {
    s.resize(m);
    for (int i = 0; i < m; ++i) {
      s[i].clear();
    }
    pos.resize(n);
    for (int i = 0; i < n; ++i) {
      pos[i].clear();
    }
    empty.clear();
    ans.clear();
    for (int i = 0; i < m; ++i) {
      int sz;
      scanf("%d", &sz);
      if (sz == 0) {
        empty.push_back(i);
      }
      for (int j = 0; j < sz; ++j) {
        int c;
        scanf("%d", &c);
        --c;
        s[i].push_back(c);
        pos[c].push_back(make_pair(j, i));
      }
    }
    for (int r = 0; r < 2; ++r) {
      for (int i = 0; i < m; ++i) {
        if (s[i].size() == 1) {
          solve_chain(i);
        }
      }
    }
    bool valid = true;
    for (int r = 0; r < 2; ++r) {
      for (int i = 0; i < n; ++i) {
        if ((r == 0 && pos[i][0].first == 1 && pos[i][1].first == 1) ||
            (r == 1 && pos[i][0].second != pos[i][1].second)) {
          if (empty.size() > 0) {
            int ti = pos[i][0].second, tmp = empty.back();
            empty.pop_back();
            move(ti, tmp);
            solve_chain(ti);
          } else {
            valid = false;
          }
        }
      }
    }
    if (!valid) {
      printf("-1\n");
    } else {
      printf("%d\n", (int)ans.size());
      for (int i = 0; i < (int)ans.size(); ++i) {
        printf("%d %d\n", ans[i].first, ans[i].second);
      }
    }
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3924kb

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
2 1
0
-1

result:

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

Test #2:

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

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: 3916kb

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
1 4
2 3
2
1 5
3 4
2
1 6
3 5
2
1 4
2 3
2
2 5
3 4
2
1 6
3 4
2
1 2
1 3
2
1 2
1 4
2
4 3
4 1
2
2 1
2 3
2
2 1
2 3
2
1 3
1 4
-1
3
2 1
3 1
3 2
3
2 3
4 3
4 2
-1
3
1 3
2 1
2 3
3
1 4
2 1
2 4
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: 1ms
memory: 3792kb

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
1 7
3 4
5 6
3
2 8
3 7
5 6
3
1 2
3 6
4 5
3
1 3
2 6
4 5
3
1 8
2 5
4 7
3
1 4
2 6
3 5
3
1 4
2 7
5 6
3
1 4
2 8
3 6
3
1 2
3 6
4 5
3
2 5
3 6
4 7
3
1 2
3 4
5 8
3
1 6
2 5
3 4
3
1 3
4 7
5 6
3
2 5
4 8
6 7
3
1 2
3 6
4 5
3
1 3
2 7
5 6
3
2 4
3 7
6 8
3
1 5
2 3
4 6
3
1 5
2 3
4 7
3
1 6
4 8
5 7
3
1 5
...

result:

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

Test #5:

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

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
1 2
3 7
4 6
5 8
4
1 9
3 8
4 6
5 7
4
1 7
2 3
4 5
8 9
4
1 6
2 8
3 4
5 7
4
1 5
2 4
3 7
6 8
4
1 10
2 8
3 7
4 9
4
1 5
2 4
3 6
7 8
4
1 9
2 8
3 5
4 6
4
2 3
4 7
5 6
8 10
4
1 3
2 8
4 7
5 6
4
1 7
2 9
3 4
5 6
4
1 9
2 10
3 8
4 5
4
1 3
2 5
4 8
6 7
4
1 5
2 7
3 8
4 9
4
1 8
2 9
3 6
5 7
4
1 5
2 8
3 4
6 7
4
1 5
2 8...

result:

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

Test #6:

score: 0
Accepted
time: 27ms
memory: 3912kb

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
2 4
3 6
5 8
7 10
5
1 3
2 10
4 6
5 8
9 11
5
1 5
3 12
4 10
6 8
7 11
5
1 10
2 8
3 4
5 9
6 7
5
1 6
2 11
3 4
5 10
7 8
5
1 12
2 9
3 7
5 10
6 8
5
1 5
2 6
3 10
4 7
8 9
5
1 6
2 4
3 11
5 7
8 9
5
1 7
2 3
4 5
8 9
10 11
5
1 3
2 9
4 5
6 7
8 10
5
1 11
2 3
4 5
6 7
8 9
5
1 7
2 6
3 10
4 11
8 9
5
1 10
2 6
3 9
4 ...

result:

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

Test #7:

score: 0
Accepted
time: 26ms
memory: 3936kb

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
1 6
2 9
10 8
10 3
4 7
5 11
5
5 4
5 1
7 5
9 5
9 7
-1
8
3 7
5 3
8 3
2 8
2 5
1 2
4 1
4 2
7
1 8
7 1
6 7
6 2
5 1
5 3
4 9
5
4 1
2 7
5 2
3 5
3 4
5
7 1
8 7
6 3
2 6
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
1 11
2 3
4 9
5 10
6 8
7 12
3
7 6
5 7
5 3
8
7 6
4 7
4 3
1 6
1 9
5 1
8 1
8 5
6
1 3
2 ...

result:

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

Test #8:

score: 0
Accepted
time: 26ms
memory: 3924kb

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
4 1
7
1 11
2 3
4 9
5 6
7 10
7 5
8 12
7
1 4
2 5
3 15
6 12
7 11
8 13
9 14
-1
7
2 12
4 8
1 5
3 1
3 11
6 9
7 10
7
3 14
4 12
5 8
1 7
1 6
9 11
10 13
7
1 6
3 1
7 3
10 1
8 10
4 8
4 7
7
1 4
2 11
6 2
6 3
5 12
7 10
8 9
7
2 10
4 6
7 4
7 9
3 4
5 11
5 3
7
4 1
4 6
2 7
5 9
8 5
10 5
10 8
7
1 13
2 9
3 8...

result:

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

Test #9:

score: 0
Accepted
time: 26ms
memory: 3856kb

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
1 11
3 6
4 8
5 10
9 15
14 16
9
1 11
12 9
12 2
3 8
4 10
7 13
5 7
6 7
6 5
-1
8
1 16
2 10
3 9
4 7
5 6
8 13
11 14
12 15
9
1 9
11 1
11 2
13 1
13 4
5 10
6 14
7 15
8 12
9
8 1
2 8
9 1
9 2
3 9
4 3
7 9
5 7
5 4
7
2 6
1 2
10 1
4 10
8 2
5 8
5 4
8
1 6
2 11
3 8
4 16
5 13
7 9
10 12
14 15
10
5 8
3 5
4 3
7 5
7 4
1 ...

result:

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

Test #10:

score: 0
Accepted
time: 27ms
memory: 3936kb

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
4 11
4 1
5 12
6 8
7 9
10 7
13 7
13 10
2 13
3 2
3 13
11
1 5
11 12
4 11
2 1
3 2
6 3
6 4
8 1
9 11
13 9
13 8
9
1 17
2 3
4 18
5 6
7 10
8 12
9 15
11 14
13 16
8
4 12
7 11
6 7
6 8
2 6
9 6
5 9
5 2
9
1 13
3 11
4 10
5 14
2 7
6 12
6 2
9 17
15 16
13
1 4
10 4
10 1
5 10
6 10
9 6
9 5
7 9
11 7
11 9
2 11
8 2
8 11
...

result:

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

Test #11:

score: 0
Accepted
time: 28ms
memory: 3844kb

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
2 14
3 17
4 18
6 15
7 8
9 11
10 13
16 19
7
1 19
2 16
4 15
5 13
6 10
7 11
9 12
-1
10
1 3
2 12
5 4
5 19
6 11
7 17
8 18
9 14
10 15
13 16
11
1 9
3 17
4 19
5 6
5 13
8 14
10 12
15 16
7 15
18 7
18 15
7
1 3
5 9
6 13
8 16
10 14
12 18
17 19
10
3 13
5 3
5 1
2 15
4 6
7 14
8 12
9 16
10 17
11 18
10
1 2
3 19...

result:

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

Test #12:

score: 0
Accepted
time: 23ms
memory: 3856kb

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
3 6
9 10
15 12
15 11
5 15
8 15
7 8
13 7
13 5
13
2 13
4 5
6 9
7 8
14 7
14 10
1 7
3 14
17 3
17 1
16 14
16 11
12 15
10
1 8
2 14
3 21
4 12
5 11
6 17
7 9
10 18
13 15
16 20
11
1 10
2 9
15 3
12 11
8 12
8 15
13 8
14 8
7 14
5 7
5 13
10
2 19
3 6
4 15
7 10
16 8
5 11
5 16
9 13
12 17
14 18
11
7 10
7 12
1 7
4 7...

result:

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

Test #13:

score: 0
Accepted
time: 28ms
memory: 3988kb

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
1 12
2 16
3 20
4 17
5 22
6 10
7 21
8 23
9 18
11 14
13 19
24 25
11
1 15
2 11
9 7
6 16
4 6
4 9
12 13
17 18
10 17
14 10
14 17
9
5 11
10 11
3 10
6 3
6 5
1 6
13 1
12 13
12 6
10
8 13
3 8
1 3
7 5
7 1
12 5
4 12
6 4
14 13
14 6
12
1 10
2 6
3 13
4 20
5 19
7 14
8 22
9 17
11 24
12 21
15 18
16 25
11
2 12
4 5
8...

result:

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

Test #14:

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

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

result:

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

Test #15:

score: 0
Accepted
time: 28ms
memory: 3980kb

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

result:

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

Test #16:

score: 0
Accepted
time: 28ms
memory: 3848kb

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
2 3
2 14
4 21
5 6
11 17
10 15
9 10
13 11
13 9
12 11
12 22
8 12
19 8
19 12
13
1 20
17 2
14 17
3 14
24 15
13 24
19 13
19 3
4 8
6 22
10 16
11 12
18 23
12
2 3
8 18
8 5
6 22
7 12
9 14
10 13
15 16
23 24
17 23
19 23
19 17
15
6 17
2 6
16 3
5 16
5 2
10 3
15 5
15 10
11 5
14 6
12 14
12 11
7 12
13 12
13 7
16...

result:

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

Test #17:

score: 0
Accepted
time: 28ms
memory: 3984kb

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

result:

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

Test #18:

score: 0
Accepted
time: 28ms
memory: 3940kb

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

result:

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

Test #19:

score: 0
Accepted
time: 28ms
memory: 3804kb

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

result:

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

Test #20:

score: 0
Accepted
time: 29ms
memory: 3940kb

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

result:

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

Test #21:

score: 0
Accepted
time: 28ms
memory: 3804kb

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

result:

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

Test #22:

score: 0
Accepted
time: 16ms
memory: 4004kb

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

result:

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

Test #23:

score: 0
Accepted
time: 16ms
memory: 4128kb

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

result:

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

Test #24:

score: 0
Accepted
time: 117ms
memory: 27188kb

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
47930 39403
120612 199994
45526 120612
45526 47930
82791 199994
8600 82791
73469 8600
121113 73469
130069 45526
100144 130069
146839 100144
146839 121113
69274 45526
192298 146839
192298 69274
48529 146839
72878 192298
72878 48529
133198 192298
61006 133198
49920 72878
19140 49920
111450 1914...

result:

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

Test #25:

score: 0
Accepted
time: 122ms
memory: 27060kb

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
87499 466
1886 87499
41252 1886
159869 41252
15716 199939
14654 15716
23686 14654
23686 159869
79718 199939
34240 79718
37452 34240
159098 23686
164285 159098
164285 37452
166588 23686
26215 166588
47492 26215
75168 164285
58350 75168
58350 47492
54982 164285
79811 58350
91593 79811
199135 91...

result:

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

Test #26:

score: 0
Accepted
time: 106ms
memory: 27100kb

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
159225 2791
130502 199158
130502 159225
130400 199158
116378 130400
5219 116378
193254 5219
59594 193254
13400 59594
59402 130502
169530 59402
169530 13400
134704 130502
23501 134704
195483 169530
136282 195483
136282 23501
194296 169530
163027 194296
29741 136282
29741 163027
161399 136282
1...

result:

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

Test #27:

score: 0
Accepted
time: 113ms
memory: 26372kb

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
53513 195490
53513 8
66763 195490
81301 66763
81301 90130
145277 166931
88452 145277
30681 88452
30681 36
187794 38
177176 140533
177176 187794
33449 177176
33449 50
32589 177176
25968 33449
181763 25968
190609 181763
190609 32589
164372 33449
19442 164372
194690 19442
172263 190609
37722 172...

result:

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

Test #28:

score: 0
Accepted
time: 58ms
memory: 17568kb

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
1 19200
127536 17700
127536 3
41165 10
146008 127536
146008 41165
21234 127536
13283 146008
13283 21234
5949 146008
5949 66955
52406 70095
52406 13
14 54179
97745 17288
97745 16
66806 104779
66806 17
82619 20
94208 66806
94208 82619
87896 66806
87896 134836
25 43922
26 145724
51683 28
13132 5...

result:

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

Test #29:

score: 0
Accepted
time: 101ms
memory: 27124kb

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 200000
97712 171410
52612 97712
119503 52612
138016 119503
28740 138016
21514 199999
169576 21514
36185 169576
8836 36185
74434 8836
74434 28740
91173 199999
77064 91173
130769 74434
130769 77064
11747 74434
185560 11747
72711 130769
77786 72711
77786 185560
193153 130769
99645 77786
9...

result:

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