QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#46762	#2064. Bitset Master	fragment	AC ✓	1034ms	230796kb	C++	4.2kb	2022-09-01 16:29:07	2022-09-01 16:29:07

Judging History

This is the latest submission verdict.

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-09-01 16:29:07]
Judged

Verdict: AC
Time: 1034ms
Memory: 230796kb

Show

[2022-09-01 16:29:07]
Submitted

answer

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int N = 200005, Q = 600005;
int n, m;
int a[N], b[N], ans[Q];
int sz[N], son[N];
int f[N], g[N];
int fa[N], ver[N];
int bg[N], qwq[N];
bool u[N];
vector<int> to[N];
vector<pair<int, int>> qy[N];

int find(int x) {
  while (x != fa[x])
    x = fa[x] = fa[fa[x]];
  return x;
}

namespace bits{
int lm, s[Q];
int st[Q << 2], top;

void add(int x, int v) {
  st[++top] = x;
  x++;
  while (x)
    s[x] += v, x &= x - 1;
}
int query(int x) {
  int ans = 0;
  x++;
  while (x <= lm)
    ans += s[x], x += x & (-x);
  return ans;
}

void clear() {
  while (top) {
    int x = st[top--] + 1;
    while (x)
      s[x] = 0, x &= x - 1;
  }
}
}

void dfs(int i, int lt) {
  sz[i] = 1, son[i] = 0;
  f[i] = g[i] = -1;
  fa[i] = ver[i] = i;

  for (int j : to[i])
    if (j != lt && !u[j]) {
      bg[j] = lt ? bg[i] : j;
      dfs(j, i);
      sz[i] += sz[j];
      if (sz[son[i]] < sz[j])
        son[i] = j;
    }
}

void _clear(int i, int lt) {
  f[i] = g[i] = -1;
  fa[i] = ver[i] = i;
  for (int j : to[i])
    if (j != lt && !u[j])
      _clear(j, i);
}

int centroid(int x) {
  for (int i = x;; i = son[i])
    if (sz[son[i]] * 2 <= sz[x])
      return i;
}

void solve(int x) {
  u[x] = 1;
  dfs(x, 0);
  ver[x] = g[x] = f[x] = 0;
  int rt = x;

  bits::lm = qy[x].size() + 1;
  bits::add(0, 1);

  for (int i = 1; i <= (int)qy[x].size(); i++) {
    int op = qy[x][i - 1].first;
    if (op > 0) {
      int x = g[find(qy[rt][i - 1].second)], y = qy[rt][i - 1].second;
      if (x != -1)
        ans[op] += bits::query(x);
      if (y != rt)
        qy[bg[y]].push_back(qy[rt][i - 1]);
    } else {
      bits::add(f[rt], -1);
      bits::add(f[rt] = i, 1);

      int id = qy[x][i - 1].second;
      int x = a[id], y = b[id];
      if (sz[x] < sz[y])
        swap(x, y);

      if (f[x] > f[y]) {
        bits::add(f[y], -1);
        bits::add(f[y] = f[x], 1);
      }

      if (ver[y]) {
        if (x == rt)
          g[ver[y]] = i, ver[y] = 0;
        else {
          if (!ver[x])
            ver[x] = ver[y], ver[y] = 0;
          else
            fa[ver[y]] = ver[x], ver[y] = 0;
        }
      }

      qy[bg[y]].push_back(qy[rt][i - 1]);
    }
  }
  bits::clear();

  _clear(x, 0);
  for (int y : to[x])
    if (!u[y]) {
      f[x] = -1;
      bits::lm = qy[y].size() + 1;
      for (int i = 1; i <= (int)qy[y].size(); i++) {
        int op = qy[y][i - 1].first;
        if (op > 0) {
          int x = g[find(qy[y][i - 1].second)];
          if (x != -1)
            ans[op] -= bits::query(x);
        } else {
          f[rt] = i;
          int id = qy[y][i - 1].second;
          int x = a[id], y = b[id];
          if (sz[x] < sz[y])
            swap(x, y);

          if (f[x] > f[y]) {
            bits::add(f[y], -1);
            bits::add(f[y] = f[x], 1);
          }

          if (ver[y]) {
            if (x == rt)
              g[ver[y]] = i, ver[y] = 0;
            else {
              if (!ver[x])
                ver[x] = ver[y], ver[y] = 0;
              else
                fa[ver[y]] = ver[x], ver[y] = 0;
            }
          }
        }
      }
      bits::clear();
      qy[y].clear();
      qwq[y] = centroid(y);
    }

  for (auto tp : qy[x]) {
    int op = tp.first;
    if (op > 0) {
      int x = tp.second;
      if (x != rt)
        qy[qwq[bg[x]]].push_back(tp);
    } else {
      int id = tp.second;
      int x = a[id], y = b[id];
      if (sz[x] < sz[y])
        swap(x, y);

      if (x != rt)
        qy[qwq[bg[x]]].push_back(tp);
    }
  }

  for (int y : to[x])
    if (!u[y])
      solve(qwq[y]);
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  cin >> n >> m;
  for (int i = 1; i != n; i++) {
    cin >> a[i] >> b[i];
    to[a[i]].push_back(b[i]);
    to[b[i]].push_back(a[i]);
  }
  qy[1].resize(m);
  for (int i = 0; i != m; i++) {
    int x, y;
    cin >> x >> y;
    qy[1][i] = {x == 1 ? i + 1 : -i - 1, y};
  }

  solve(1);

  for (int i = 1; i <= m; i++)
    if (ans[i])
      cout << ans[i] << '\n';
}

源文件, 语言: C++

詳細信息

Test #1:

score: 100

Accepted

time: 3ms

memory: 13120kb

input:

output:

result:

ok 5 lines

Test #2:

score: 0

Accepted

time: 460ms

memory: 55076kb

input:

200000 600000
1 2
1 3
3 4
2 5
2 6
4 7
1 8
3 9
2 10
3 11
1 12
3 13
3 14
4 15
3 16
1 17
4 18
1 19
3 20
4 21
1 22
2 23
2 24
1 25
2 26
3 27
3 28
3 29
1 30
3 31
1 32
2 33
4 34
2 35
3 36
1 37
3 38
4 39
3 40
4 41
4 42
3 43
4 44
2 45
4 46
2 47
4 48
4 49
1 50
4 51
2 52
4 53
3 54
1 55
4 56
3 57
2 58
1 59
2 60...

output:

result:

ok 209757 lines

Test #3:

score: 0

Accepted

time: 574ms

memory: 64292kb

input:

200000 600000
1 2
1 3
2 4
1 5
4 6
5 7
5 8
2 9
1 10
1 11
9 12
6 13
8 14
13 15
11 16
4 17
2 18
4 19
11 20
2 21
7 22
11 23
10 24
14 25
12 26
17 27
23 28
6 29
21 30
30 31
5 32
25 33
18 34
29 35
12 36
15 37
18 38
19 39
17 40
21 41
10 42
9 43
17 44
18 45
18 46
7 47
20 48
20 49
32 50
29 51
4 52
9 53
19 54
...

output:

result:

ok 210073 lines

Test #4:

score: 0

Accepted

time: 557ms

memory: 63648kb

input:

200000 600000
1 2
2 3
2 4
3 5
3 6
6 7
2 8
7 9
1 10
4 11
2 12
4 13
2 14
9 15
4 16
9 17
2 18
1 19
5 20
8 21
11 22
7 23
6 24
10 25
2 26
10 27
10 28
7 29
8 30
9 31
10 32
10 33
3 34
10 35
2 36
5 37
4 38
3 39
9 40
9 41
8 42
2 43
9 44
1 45
9 46
11 47
8 48
6 49
3 50
7 51
7 52
4 53
7 54
4 55
3 56
7 57
2 58
7...

output:

result:

ok 210266 lines

Test #5:

score: 0

Accepted

time: 649ms

memory: 72360kb

input:

200000 600000
1 2
2 3
3 4
4 5
4 6
3 7
2 8
7 9
5 10
3 11
6 12
2 13
3 14
5 15
2 16
16 17
7 18
12 19
3 20
14 21
13 22
2 23
10 24
14 25
25 26
1 27
8 28
1 29
15 30
10 31
26 32
28 33
33 34
5 35
13 36
23 37
21 38
34 39
27 40
26 41
18 42
9 43
29 44
38 45
28 46
29 47
46 48
2 49
19 50
12 51
26 52
39 53
47 54
...

output:

result:

ok 209912 lines

Test #6:

score: 0

Accepted

time: 639ms

memory: 70660kb

input:

200000 600000
1 2
2 3
1 4
2 5
3 6
1 7
3 8
5 9
8 10
9 11
10 12
9 13
4 14
10 15
3 16
9 17
2 18
18 19
16 20
10 21
6 22
22 23
15 24
11 25
4 26
14 27
2 28
15 29
26 30
2 31
26 32
30 33
17 34
12 35
34 36
24 37
17 38
13 39
19 40
33 41
2 42
3 43
31 44
39 45
3 46
41 47
42 48
16 49
33 50
35 51
19 52
39 53
35 5...

output:

result:

ok 209688 lines

Test #7:

score: 0

Accepted

time: 565ms

memory: 66668kb

input:

200000 600000
1 2
2 3
1 4
4 5
4 6
1 7
3 8
1 9
8 10
2 11
6 12
8 13
4 14
9 15
7 16
2 17
3 18
3 19
9 20
15 21
19 22
13 23
21 24
3 25
17 26
6 27
22 28
11 29
1 30
27 31
4 32
8 33
24 34
32 35
19 36
31 37
33 38
26 39
6 40
26 41
6 42
25 43
15 44
6 45
12 46
13 47
9 48
33 49
7 50
22 51
31 52
26 53
4 54
13 55
...

output:

result:

ok 210127 lines

Test #8:

score: 0

Accepted

time: 636ms

memory: 70836kb

input:

200000 600000
1 2
2 3
1 4
2 5
4 6
5 7
2 8
5 9
8 10
8 11
3 12
12 13
4 14
3 15
6 16
12 17
11 18
6 19
11 20
4 21
14 22
14 23
1 24
7 25
24 26
5 27
6 28
5 29
5 30
11 31
5 32
18 33
28 34
16 35
14 36
5 37
34 38
3 39
16 40
35 41
13 42
24 43
41 44
26 45
1 46
19 47
8 48
46 49
13 50
50 51
27 52
19 53
33 54
32 ...

output:

result:

ok 209918 lines

Test #9:

score: 0

Accepted

time: 532ms

memory: 65540kb

input:

200000 600000
1 2
1 3
3 4
2 5
3 6
3 7
1 8
2 9
3 10
4 11
8 12
7 13
3 14
6 15
6 16
9 17
4 18
12 19
13 20
4 21
20 22
3 23
1 24
18 25
9 26
21 27
25 28
26 29
25 30
29 31
14 32
27 33
26 34
12 35
10 36
18 37
7 38
2 39
6 40
11 41
13 42
25 43
24 44
25 45
13 46
8 47
25 48
14 49
24 50
8 51
1 52
6 53
15 54
18 5...

output:

result:

ok 209781 lines

Test #10:

score: 0

Accepted

time: 656ms

memory: 73560kb

input:

200000 600000
1 2
2 3
2 4
1 5
5 6
1 7
4 8
4 9
5 10
6 11
3 12
8 13
9 14
4 15
2 16
11 17
16 18
15 19
4 20
6 21
12 22
20 23
1 24
23 25
20 26
10 27
20 28
27 29
18 30
30 31
8 32
21 33
3 34
24 35
11 36
33 37
17 38
8 39
9 40
26 41
24 42
13 43
34 44
44 45
13 46
22 47
46 48
26 49
29 50
2 51
6 52
17 53
51 54
...

output:

result:

ok 209552 lines

Test #11:

score: 0

Accepted

time: 469ms

memory: 59044kb

input:

200000 600000
1 2
1 3
3 4
2 5
1 6
3 7
4 8
4 9
4 10
5 11
10 12
10 13
8 14
9 15
8 16
5 17
6 18
8 19
4 20
3 21
9 22
10 23
6 24
6 25
10 26
1 27
8 28
4 29
8 30
9 31
9 32
8 33
4 34
5 35
6 36
1 37
7 38
3 39
6 40
2 41
8 42
8 43
1 44
5 45
6 46
3 47
7 48
10 49
5 50
9 51
9 52
9 53
8 54
8 55
6 56
3 57
6 58
3 59...

output:

result:

ok 210286 lines

Test #12:

score: 0

Accepted

time: 553ms

memory: 63392kb

input:

200000 600000
1 2
1 3
2 4
3 5
1 6
4 7
5 8
6 9
3 10
6 11
2 12
2 13
13 14
11 15
5 16
1 17
11 18
9 19
12 20
15 21
1 22
6 23
8 24
22 25
2 26
24 27
6 28
19 29
6 30
6 31
22 32
1 33
21 34
13 35
29 36
28 37
10 38
18 39
5 40
19 41
21 42
31 43
31 44
19 45
3 46
17 47
26 48
3 49
25 50
27 51
31 52
21 53
2 54
22 ...

output:

result:

ok 210525 lines

Test #13:

score: 0

Accepted

time: 618ms

memory: 68084kb

input:

200000 600000
1 2
2 3
1 4
1 5
5 6
4 7
3 8
1 9
4 10
2 11
2 12
5 13
4 14
13 15
10 16
13 17
8 18
10 19
16 20
3 21
12 22
6 23
2 24
12 25
14 26
22 27
8 28
7 29
9 30
5 31
13 32
5 33
9 34
20 35
9 36
16 37
23 38
28 39
30 40
5 41
6 42
30 43
41 44
29 45
31 46
4 47
26 48
23 49
16 50
45 51
16 52
48 53
23 54
36 ...

output:

result:

ok 210125 lines

Test #14:

score: 0

Accepted

time: 577ms

memory: 64744kb

input:

200000 600000
1 2
1 3
1 4
2 5
5 6
2 7
6 8
1 9
9 10
2 11
10 12
5 13
3 14
14 15
15 16
3 17
17 18
15 19
19 20
1 21
2 22
6 23
17 24
13 25
20 26
15 27
14 28
1 29
21 30
1 31
23 32
7 33
8 34
6 35
13 36
4 37
22 38
26 39
11 40
22 41
22 42
23 43
3 44
15 45
11 46
7 47
1 48
2 49
11 50
22 51
21 52
7 53
28 54
16 ...

output:

result:

ok 210125 lines

Test #15:

score: 0

Accepted

time: 569ms

memory: 65844kb

input:

200000 600000
1 2
2 3
2 4
3 5
5 6
2 7
2 8
2 9
4 10
2 11
8 12
9 13
12 14
2 15
6 16
1 17
10 18
18 19
2 20
1 21
16 22
14 23
11 24
3 25
13 26
13 27
27 28
8 29
2 30
26 31
7 32
8 33
29 34
29 35
24 36
19 37
1 38
11 39
25 40
31 41
38 42
14 43
28 44
25 45
37 46
18 47
31 48
29 49
10 50
37 51
35 52
27 53
24 54...

output:

result:

ok 210079 lines

Test #16:

score: 0

Accepted

time: 561ms

memory: 67208kb

input:

200000 600000
1 2
1 3
1 4
2 5
4 6
1 7
2 8
6 9
7 10
10 11
3 12
12 13
3 14
8 15
7 16
5 17
2 18
9 19
2 20
6 21
7 22
22 23
16 24
11 25
14 26
14 27
1 28
2 29
23 30
8 31
10 32
32 33
30 34
15 35
30 36
20 37
3 38
20 39
30 40
39 41
31 42
15 43
43 44
11 45
3 46
14 47
37 48
48 49
44 50
5 51
33 52
20 53
41 54
4...

output:

result:

ok 209525 lines

Test #17:

score: 0

Accepted

time: 608ms

memory: 70844kb

input:

200000 600000
1 2
2 3
3 4
2 5
1 6
6 7
7 8
6 9
3 10
7 11
7 12
9 13
1 14
2 15
5 16
7 17
2 18
7 19
9 20
5 21
20 22
6 23
2 24
8 25
5 26
26 27
14 28
27 29
16 30
24 31
30 32
12 33
15 34
9 35
12 36
35 37
18 38
12 39
24 40
11 41
27 42
27 43
24 44
30 45
17 46
17 47
20 48
45 49
6 50
32 51
28 52
38 53
31 54
41...

output:

result:

ok 210271 lines

Test #18:

score: 0

Accepted

time: 563ms

memory: 64808kb

input:

200000 600000
1 2
1 3
1 4
2 5
3 6
3 7
4 8
3 9
4 10
4 11
5 12
2 13
4 14
7 15
1 16
15 17
10 18
12 19
4 20
20 21
7 22
21 23
6 24
1 25
6 26
25 27
21 28
18 29
26 30
22 31
10 32
5 33
28 34
6 35
31 36
9 37
26 38
2 39
35 40
16 41
8 42
12 43
29 44
6 45
44 46
7 47
16 48
40 49
11 50
44 51
6 52
7 53
31 54
2 55
...

output:

result:

ok 210069 lines

Test #19:

score: 0

Accepted

time: 557ms

memory: 61584kb

input:

200000 600000
1 2
1 3
3 4
1 5
2 6
5 7
3 8
1 9
9 10
10 11
4 12
1 13
4 14
3 15
8 16
10 17
7 18
8 19
8 20
9 21
14 22
7 23
4 24
8 25
18 26
1 27
2 28
14 29
2 30
25 31
23 32
10 33
28 34
5 35
2 36
8 37
5 38
10 39
10 40
13 41
9 42
1 43
6 44
22 45
9 46
8 47
4 48
8 49
5 50
3 51
17 52
19 53
27 54
26 55
4 56
2 ...

output:

result:

ok 209766 lines

Test #20:

score: 0

Accepted

time: 584ms

memory: 69112kb

input:

200000 600000
1 2
2 3
3 4
4 5
1 6
3 7
1 8
8 9
3 10
9 11
7 12
7 13
2 14
10 15
7 16
15 17
7 18
18 19
9 20
1 21
4 22
9 23
17 24
14 25
12 26
5 27
2 28
27 29
2 30
9 31
10 32
15 33
22 34
30 35
14 36
16 37
1 38
6 39
19 40
1 41
1 42
6 43
28 44
18 45
15 46
26 47
31 48
38 49
45 50
39 51
32 52
44 53
47 54
30 5...

output:

result:

ok 210320 lines

Test #21:

score: 0

Accepted

time: 604ms

memory: 68400kb

input:

200000 600000
1 2
1 3
1 4
3 5
5 6
6 7
3 8
5 9
6 10
9 11
9 12
6 13
6 14
7 15
6 16
6 17
13 18
15 19
14 20
4 21
3 22
12 23
7 24
10 25
18 26
8 27
20 28
24 29
17 30
1 31
17 32
18 33
4 34
24 35
24 36
25 37
16 38
32 39
27 40
34 41
15 42
15 43
30 44
1 45
17 46
5 47
32 48
25 49
11 50
14 51
24 52
18 53
32 54
...

output:

result:

ok 209755 lines

Test #22:

score: 0

Accepted

time: 863ms

memory: 217144kb

input:

200000 600000
1 2
1 3
2 4
3 5
5 6
4 7
4 8
5 9
7 10
10 11
9 12
11 13
7 14
10 15
12 16
12 17
12 18
14 19
16 20
15 21
20 22
17 23
20 24
24 25
25 26
23 27
23 28
26 29
26 30
25 31
25 32
32 33
29 34
29 35
32 36
34 37
33 38
38 39
38 40
37 41
36 42
42 43
39 44
39 45
42 46
45 47
45 48
47 49
44 50
44 51
46 52...

output:

result:

ok 261233 lines

Test #23:

score: 0

Accepted

time: 844ms

memory: 226308kb

input:

200000 600000
1 2
1 3
3 4
3 5
4 6
3 7
6 8
6 9
8 10
7 11
10 12
10 13
12 14
12 15
12 16
13 17
16 18
17 19
19 20
18 21
18 22
20 23
22 24
21 25
24 26
26 27
24 28
27 29
29 30
27 31
28 32
31 33
32 34
32 35
34 36
35 37
37 38
36 39
36 40
37 41
38 42
40 43
42 44
42 45
44 46
46 47
46 48
46 49
47 50
50 51
49 5...

output:

result:

ok 154121 lines

Test #24:

score: 0

Accepted

time: 868ms

memory: 214228kb

input:

200000 600000
1 2
1 3
3 4
2 5
5 6
6 7
6 8
7 9
6 10
9 11
11 12
9 13
13 14
8 15
14 16
11 17
17 18
14 19
17 20
18 21
15 22
22 23
17 24
24 25
23 26
22 27
21 28
22 29
25 30
25 31
28 32
31 33
31 34
32 35
35 36
35 37
36 38
37 39
34 40
39 41
38 42
38 43
39 44
41 45
41 46
43 47
46 48
47 49
48 50
45 51
47 52
...

output:

result:

ok 121812 lines

Test #25:

score: 0

Accepted

time: 897ms

memory: 213668kb

input:

200000 600000
1 2
1 3
2 4
3 5
5 6
5 7
6 8
4 9
4 10
9 11
4 12
10 13
11 14
14 15
10 16
10 17
15 18
13 19
15 20
18 21
20 22
20 23
16 24
22 25
25 26
25 27
22 28
26 29
25 30
27 31
30 32
25 33
27 34
31 35
33 36
33 37
35 38
36 39
36 40
37 41
38 42
39 43
41 44
42 45
42 46
40 47
45 48
42 49
44 50
43 51
48 52...

output:

result:

ok 157203 lines

Test #26:

score: 0

Accepted

time: 871ms

memory: 213332kb

input:

200000 600000
1 2
1 3
3 4
1 5
3 6
1 7
7 8
3 9
5 10
3 11
8 12
6 13
12 14
13 15
14 16
11 17
12 18
15 19
18 20
17 21
15 22
19 23
17 24
19 25
22 26
22 27
22 28
23 29
22 30
24 31
31 32
25 33
31 34
32 35
30 36
33 37
35 38
38 39
33 40
40 41
37 42
40 43
42 44
40 45
39 46
45 47
47 48
41 49
42 50
45 51
51 52
...

output:

result:

ok 192140 lines

Test #27:

score: 0

Accepted

time: 861ms

memory: 209296kb

input:

200000 600000
1 2
1 3
2 4
3 5
1 6
6 7
2 8
6 9
5 10
10 11
9 12
9 13
13 14
8 15
14 16
8 17
9 18
13 19
13 20
20 21
19 22
18 23
16 24
19 25
20 26
23 27
23 28
19 29
27 30
29 31
24 32
31 33
31 34
34 35
30 36
28 37
32 38
33 39
32 40
34 41
40 42
37 43
42 44
37 45
37 46
39 47
39 48
41 49
49 50
49 51
47 52
47...

output:

result:

ok 250960 lines

Test #28:

score: 0

Accepted

time: 869ms

memory: 209800kb

input:

200000 600000
1 2
1 3
1 4
3 5
1 6
1 7
4 8
5 9
2 10
9 11
4 12
7 13
12 14
14 15
9 16
14 17
12 18
14 19
15 20
12 21
19 22
19 23
23 24
21 25
19 26
24 27
25 28
20 29
29 30
23 31
25 32
26 33
28 34
29 35
28 36
31 37
31 38
37 39
31 40
34 41
36 42
37 43
41 44
38 45
44 46
39 47
46 48
46 49
46 50
45 51
43 52
5...

output:

result:

ok 188697 lines

Test #29:

score: 0

Accepted

time: 853ms

memory: 222036kb

input:

200000 600000
1 2
2 3
1 4
1 5
2 6
5 7
7 8
7 9
6 10
7 11
9 12
9 13
12 14
12 15
12 16
14 17
16 18
17 19
19 20
17 21
19 22
20 23
20 24
23 25
24 26
26 27
26 28
26 29
29 30
29 31
28 32
30 33
31 34
31 35
32 36
36 37
34 38
37 39
37 40
38 41
39 42
41 43
41 44
41 45
45 46
45 47
44 48
47 49
47 50
50 51
51 52
...

output:

result:

ok 196173 lines

Test #30:

score: 0

Accepted

time: 844ms

memory: 223420kb

input:

200000 600000
1 2
2 3
1 4
3 5
4 6
3 7
4 8
5 9
9 10
9 11
10 12
9 13
10 14
13 15
13 16
13 17
14 18
15 19
19 20
18 21
20 22
22 23
23 24
22 25
22 26
23 27
27 28
27 29
28 30
29 31
30 32
30 33
31 34
32 35
34 36
36 37
35 38
38 39
39 40
40 41
38 42
40 43
42 44
44 45
42 46
46 47
47 48
48 49
47 50
47 51
48 52...

output:

result:

ok 221200 lines

Test #31:

score: 0

Accepted

time: 807ms

memory: 220796kb

input:

200000 600000
1 2
1 3
3 4
2 5
5 6
4 7
7 8
6 9
7 10
10 11
8 12
9 13
12 14
11 15
14 16
16 17
17 18
18 19
17 20
17 21
21 22
19 23
21 24
21 25
25 26
25 27
26 28
25 29
28 30
30 31
29 32
29 33
32 34
31 35
32 36
36 37
35 38
38 39
38 40
37 41
39 42
42 43
41 44
43 45
42 46
46 47
45 48
47 49
46 50
50 51
48 52...

output:

result:

ok 258649 lines

Test #32:

score: 0

Accepted

time: 876ms

memory: 219260kb

input:

200000 600000
1 2
1 3
2 4
2 5
1 6
5 7
6 8
7 9
5 10
6 11
10 12
12 13
13 14
11 15
13 16
13 17
13 18
17 19
18 20
20 21
18 22
19 23
19 24
21 25
23 26
26 27
26 28
24 29
26 30
27 31
29 32
31 33
30 34
33 35
32 36
35 37
37 38
37 39
39 40
38 41
40 42
42 43
40 44
42 45
45 46
46 47
45 48
46 49
47 50
49 51
50 5...

output:

result:

ok 145154 lines

Test #33:

score: 0

Accepted

time: 848ms

memory: 218100kb

input:

200000 600000
1 2
2 3
3 4
2 5
1 6
2 7
4 8
8 9
5 10
9 11
8 12
10 13
11 14
11 15
13 16
13 17
13 18
15 19
16 20
18 21
20 22
20 23
23 24
23 25
25 26
22 27
26 28
28 29
29 30
30 31
30 32
30 33
30 34
33 35
35 36
34 37
37 38
35 39
37 40
36 41
41 42
40 43
43 44
44 45
42 46
46 47
47 48
46 49
46 50
49 51
47 52...

output:

result:

ok 221874 lines

Test #34:

score: 0

Accepted

time: 883ms

memory: 221632kb

input:

200000 600000
1 2
2 3
2 4
2 5
4 6
6 7
5 8
5 9
6 10
9 11
11 12
10 13
12 14
11 15
14 16
13 17
16 18
16 19
16 20
17 21
19 22
19 23
23 24
21 25
25 26
23 27
27 28
28 29
26 30
28 31
31 32
30 33
30 34
32 35
32 36
33 37
34 38
38 39
38 40
37 41
41 42
42 43
41 44
44 45
44 46
43 47
45 48
46 49
46 50
47 51
50 5...

output:

result:

ok 197390 lines

Test #35:

score: 0

Accepted

time: 868ms

memory: 213400kb

input:

200000 600000
1 2
2 3
1 4
4 5
3 6
1 7
2 8
7 9
8 10
9 11
9 12
8 13
9 14
11 15
12 16
13 17
12 18
17 19
16 20
18 21
16 22
17 23
19 24
19 25
22 26
23 27
27 28
23 29
25 30
27 31
31 32
32 33
28 34
30 35
31 36
35 37
37 38
33 39
34 40
35 41
41 42
38 43
39 44
40 45
40 46
43 47
42 48
44 49
49 50
47 51
49 52
5...

output:

result:

ok 214980 lines

Test #36:

score: 0

Accepted

time: 876ms

memory: 210792kb

input:

200000 600000
1 2
1 3
3 4
2 5
2 6
1 7
4 8
8 9
6 10
9 11
6 12
9 13
13 14
13 15
15 16
10 17
13 18
13 19
19 20
19 21
21 22
18 23
17 24
20 25
19 26
21 27
23 28
22 29
26 30
24 31
26 32
27 33
28 34
30 35
32 36
31 37
36 38
33 39
35 40
36 41
39 42
39 43
38 44
41 45
39 46
46 47
42 48
44 49
43 50
48 51
50 52
...

output:

result:

ok 163076 lines

Test #37:

score: 0

Accepted

time: 920ms

memory: 213580kb

input:

200000 600000
1 2
2 3
1 4
3 5
1 6
5 7
4 8
8 9
5 10
7 11
11 12
10 13
13 14
12 15
11 16
16 17
15 18
15 19
16 20
18 21
17 22
19 23
21 24
20 25
21 26
24 27
27 28
25 29
25 30
28 31
30 32
28 33
33 34
34 35
31 36
32 37
36 38
35 39
38 40
39 41
39 42
41 43
43 44
40 45
43 46
43 47
46 48
45 49
48 50
50 51
50 5...

output:

result:

ok 163935 lines

Test #38:

score: 0

Accepted

time: 948ms

memory: 202456kb

input:

200000 600000
1 2
2 3
2 4
2 5
1 6
5 7
5 8
1 9
4 10
6 11
8 12
11 13
12 14
7 15
15 16
10 17
9 18
13 19
12 20
16 21
14 22
16 23
22 24
24 25
24 26
21 27
22 28
23 29
21 30
26 31
23 32
27 33
33 34
28 35
28 36
34 37
31 38
33 39
34 40
39 41
35 42
42 43
37 44
43 45
45 46
44 47
44 48
40 49
48 50
43 51
50 52
5...

output:

result:

ok 152772 lines

Test #39:

score: 0

Accepted

time: 876ms

memory: 204892kb

input:

200000 600000
1 2
2 3
2 4
2 5
3 6
5 7
3 8
7 9
8 10
3 11
2 12
9 13
9 14
9 15
9 16
12 17
11 18
11 19
13 20
20 21
20 22
16 23
18 24
21 25
18 26
26 27
25 28
23 29
27 30
27 31
30 32
30 33
26 34
30 35
29 36
35 37
29 38
33 39
32 40
39 41
37 42
33 43
41 44
44 45
45 46
37 47
44 48
41 49
49 50
41 51
44 52
46 ...

output:

result:

ok 211851 lines

Test #40:

score: 0

Accepted

time: 853ms

memory: 230796kb

input:

200000 600000
1 2
2 3
2 4
4 5
4 6
5 7
6 8
7 9
9 10
10 11
10 12
11 13
13 14
13 15
14 16
16 17
17 18
18 19
18 20
19 21
21 22
22 23
22 24
24 25
24 26
26 27
27 28
28 29
28 30
30 31
31 32
32 33
32 34
33 35
35 36
35 37
36 38
37 39
39 40
39 41
40 42
42 43
43 44
43 45
44 46
45 47
46 48
47 49
48 50
49 51
51 ...

output:

result:

ok 225574 lines

Test #41:

score: 0

Accepted

time: 982ms

memory: 217856kb

input:

200000 600000
1 2
1 3
1 4
1 5
2 6
5 7
6 8
5 9
8 10
10 11
10 12
10 13
12 14
14 15
12 16
15 17
17 18
16 19
18 20
19 21
21 22
19 23
20 24
21 25
25 26
24 27
24 28
26 29
26 30
28 31
29 32
30 33
32 34
32 35
35 36
35 37
34 38
35 39
37 40
40 41
39 42
40 43
40 44
44 45
43 46
45 47
45 48
48 49
47 50
49 51
51 ...

output:

result:

ok 130135 lines

Test #42:

score: 0

Accepted

time: 886ms

memory: 224056kb

input:

200000 600000
1 2
2 3
1 4
3 5
5 6
6 7
6 8
7 9
8 10
9 11
11 12
11 13
12 14
13 15
13 16
14 17
16 18
18 19
18 20
20 21
20 22
22 23
22 24
23 25
24 26
26 27
26 28
28 29
27 30
30 31
31 32
30 33
32 34
34 35
34 36
35 37
37 38
37 39
37 40
39 41
39 42
42 43
42 44
43 45
43 46
44 47
47 48
48 49
48 50
49 51
51 5...

output:

result:

ok 202561 lines

Test #43:

score: 0

Accepted

time: 871ms

memory: 229544kb

input:

200000 600000
1 2
1 3
3 4
4 5
5 6
6 7
7 8
8 9
8 10
9 11
10 12
12 13
12 14
14 15
15 16
16 17
17 18
17 19
19 20
20 21
20 22
22 23
22 24
24 25
24 26
25 27
26 28
28 29
28 30
29 31
30 32
31 33
32 34
34 35
34 36
35 37
37 38
38 39
38 40
39 41
41 42
42 43
43 44
43 45
44 46
45 47
46 48
47 49
49 50
50 51
51 5...

output:

result:

ok 179892 lines

Test #44:

score: 0

Accepted

time: 904ms

memory: 212076kb

input:

200000 600000
1 2
2 3
1 4
3 5
1 6
1 7
2 8
3 9
6 10
6 11
9 12
12 13
11 14
9 15
14 16
13 17
15 18
18 19
14 20
16 21
18 22
20 23
19 24
24 25
23 26
25 27
27 28
26 29
25 30
28 31
31 32
32 33
28 34
30 35
30 36
32 37
33 38
36 39
37 40
39 41
38 42
40 43
42 44
41 45
42 46
46 47
45 48
44 49
45 50
46 51
49 52
...

output:

result:

ok 169350 lines

Test #45:

score: 0

Accepted

time: 912ms

memory: 215888kb

input:

200000 600000
1 2
2 3
3 4
2 5
2 6
5 7
6 8
8 9
7 10
9 11
10 12
9 13
10 14
12 15
15 16
16 17
14 18
17 19
16 20
17 21
21 22
21 23
20 24
21 25
25 26
24 27
27 28
27 29
26 30
27 31
30 32
29 33
33 34
33 35
34 36
33 37
36 38
35 39
38 40
40 41
39 42
39 43
41 44
42 45
45 46
45 47
45 48
48 49
49 50
49 51
51 52...

output:

result:

ok 192612 lines

Test #46:

score: 0

Accepted

time: 910ms

memory: 218228kb

input:

200000 600000
1 2
2 3
3 4
4 5
3 6
6 7
7 8
7 9
9 10
9 11
10 12
10 13
12 14
12 15
14 16
16 17
15 18
17 19
17 20
20 21
20 22
22 23
23 24
24 25
25 26
24 27
27 28
27 29
28 30
28 31
31 32
30 33
33 34
32 35
35 36
36 37
36 38
37 39
37 40
40 41
40 42
41 43
42 44
42 45
45 46
45 47
46 48
47 49
49 50
50 51
49 5...

output:

result:

ok 179389 lines

Test #47:

score: 0

Accepted

time: 882ms

memory: 214556kb

input:

200000 600000
1 2
1 3
2 4
3 5
4 6
4 7
7 8
8 9
6 10
10 11
6 12
12 13
12 14
9 15
14 16
13 17
16 18
17 19
17 20
15 21
17 22
21 23
18 24
19 25
22 26
23 27
24 28
24 29
28 30
30 31
27 32
29 33
31 34
34 35
35 36
35 37
37 38
33 39
39 40
38 41
38 42
40 43
39 44
44 45
42 46
41 47
42 48
45 49
47 50
49 51
51 52...

output:

result:

ok 156907 lines

Test #48:

score: 0

Accepted

time: 891ms

memory: 203912kb

input:

200000 600000
1 2
2 3
2 4
1 5
3 6
1 7
2 8
6 9
5 10
6 11
8 12
5 13
13 14
8 15
11 16
14 17
10 18
14 19
15 20
19 21
17 22
19 23
23 24
15 25
16 26
21 27
21 28
25 29
22 30
27 31
25 32
29 33
25 34
34 35
34 36
29 37
34 38
35 39
31 40
36 41
33 42
36 43
39 44
36 45
41 46
44 47
47 48
42 49
41 50
47 51
46 52
4...

output:

result:

ok 141905 lines

Test #49:

score: 0

Accepted

time: 869ms

memory: 209328kb

input:

200000 600000
1 2
1 3
1 4
3 5
1 6
2 7
4 8
7 9
9 10
7 11
11 12
12 13
8 14
14 15
11 16
14 17
14 18
18 19
14 20
18 21
19 22
18 23
23 24
20 25
23 26
23 27
22 28
28 29
25 30
29 31
27 32
29 33
28 34
29 35
34 36
33 37
36 38
36 39
34 40
39 41
38 42
42 43
41 44
42 45
44 46
43 47
42 48
47 49
48 50
49 51
48 52...

output:

result:

ok 259892 lines

Test #50:

score: 0

Accepted

time: 888ms

memory: 207308kb

input:

200000 600000
1 2
2 3
3 4
4 5
4 6
5 7
7 8
6 9
3 10
5 11
7 12
4 13
10 14
13 15
8 16
10 17
15 18
16 19
12 20
20 21
16 22
14 23
22 24
16 25
21 26
20 27
22 28
25 29
28 30
30 31
26 32
25 33
26 34
28 35
35 36
32 37
30 38
34 39
36 40
40 41
39 42
37 43
39 44
42 45
38 46
39 47
39 48
43 49
46 50
43 51
47 52
4...

output:

result:

ok 162703 lines

Test #51:

score: 0

Accepted

time: 911ms

memory: 216588kb

input:

200000 600000
1 2
1 3
3 4
2 5
5 6
4 7
3 8
6 9
6 10
8 11
8 12
8 13
8 14
11 15
10 16
14 17
17 18
18 19
19 20
17 21
21 22
18 23
18 24
20 25
22 26
21 27
26 28
24 29
26 30
26 31
30 32
31 33
33 34
32 35
30 36
33 37
37 38
33 39
35 40
35 41
39 42
37 43
41 44
39 45
40 46
43 47
45 48
48 49
46 50
48 51
49 52
4...

output:

result:

ok 126309 lines

Test #52:

score: 0

Accepted

time: 984ms

memory: 95808kb

input:

200000 600000
1 2
2 3
3 4
2 5
5 6
2 7
4 8
2 9
1 10
3 11
1 12
2 13
1 14
7 15
11 16
10 17
7 18
10 19
13 20
8 21
18 22
13 23
18 24
3 25
24 26
4 27
10 28
16 29
23 30
5 31
26 32
9 33
12 34
33 35
7 36
9 37
11 38
30 39
36 40
1 41
16 42
20 43
31 44
22 45
12 46
43 47
7 48
32 49
33 50
29 51
17 52
17 53
52 54
...

output:

result:

ok 208246 lines

Test #53:

score: 0

Accepted

time: 931ms

memory: 93392kb

input:

200000 600000
1 2
1 3
1 4
2 5
4 6
2 7
3 8
1 9
4 10
4 11
8 12
2 13
3 14
1 15
7 16
8 17
17 18
9 19
3 20
9 21
3 22
3 23
7 24
6 25
20 26
10 27
6 28
23 29
26 30
9 31
11 32
5 33
23 34
34 35
25 36
19 37
36 38
38 39
18 40
22 41
1 42
1 43
33 44
28 45
11 46
28 47
19 48
24 49
27 50
15 51
21 52
28 53
38 54
50 5...

output:

result:

ok 196535 lines

Test #54:

score: 0

Accepted

time: 1034ms

memory: 91476kb

input:

200000 600000
1 2
1 3
2 4
3 5
3 6
3 7
3 8
1 9
5 10
1 11
4 12
12 13
6 14
12 15
1 16
1 17
2 18
5 19
16 20
17 21
19 22
12 23
20 24
9 25
17 26
5 27
2 28
17 29
16 30
26 31
16 32
22 33
13 34
24 35
11 36
8 37
32 38
15 39
20 40
36 41
1 42
16 43
13 44
7 45
9 46
7 47
13 48
2 49
29 50
41 51
24 52
4 53
17 54
43...

output:

result:

ok 138389 lines

Test #55:

score: 0

Accepted

time: 1034ms

memory: 94176kb

input:

200000 600000
1 2
1 3
3 4
1 5
5 6
4 7
6 8
6 9
6 10
6 11
9 12
7 13
2 14
6 15
9 16
9 17
12 18
2 19
9 20
16 21
20 22
3 23
23 24
15 25
17 26
16 27
17 28
22 29
22 30
16 31
15 32
27 33
31 34
15 35
2 36
26 37
15 38
1 39
1 40
28 41
21 42
38 43
9 44
39 45
24 46
30 47
9 48
36 49
28 50
8 51
13 52
16 53
34 54
5...

output:

result:

ok 148291 lines

Test #56:

score: 0

Accepted

time: 1027ms

memory: 97760kb

input:

200000 600000
1 2
1 3
1 4
3 5
3 6
6 7
6 8
7 9
8 10
7 11
6 12
1 13
5 14
6 15
4 16
6 17
9 18
5 19
11 20
6 21
1 22
1 23
16 24
6 25
24 26
7 27
20 28
26 29
28 30
21 31
9 32
12 33
30 34
27 35
7 36
16 37
33 38
10 39
11 40
6 41
38 42
17 43
27 44
11 45
30 46
43 47
11 48
15 49
46 50
12 51
42 52
32 53
26 54
44...

output:

result:

ok 151864 lines

Test #57:

score: 0

Accepted

time: 967ms

memory: 96164kb

input:

200000 600000
1 2
1 3
1 4
2 5
3 6
4 7
2 8
3 9
7 10
1 11
7 12
12 13
3 14
10 15
1 16
15 17
14 18
9 19
17 20
9 21
13 22
15 23
19 24
22 25
24 26
15 27
21 28
26 29
4 30
25 31
26 32
1 33
13 34
32 35
8 36
24 37
37 38
33 39
15 40
9 41
3 42
1 43
37 44
39 45
33 46
32 47
18 48
8 49
48 50
44 51
18 52
38 53
46 5...

output:

result:

ok 149993 lines

Test #58:

score: 0

Accepted

time: 903ms

memory: 93436kb

input:

200000 600000
1 2
1 3
1 4
4 5
3 6
4 7
1 8
2 9
1 10
9 11
4 12
2 13
7 14
11 15
10 16
11 17
1 18
8 19
18 20
13 21
2 22
19 23
13 24
8 25
13 26
19 27
3 28
3 29
22 30
16 31
4 32
13 33
14 34
27 35
31 36
8 37
22 38
14 39
29 40
9 41
14 42
16 43
31 44
13 45
17 46
11 47
19 48
39 49
9 50
39 51
1 52
43 53
43 54
...

output:

result:

ok 263806 lines

Test #59:

score: 0

Accepted

time: 914ms

memory: 96016kb

input:

200000 600000
1 2
1 3
1 4
1 5
2 6
2 7
6 8
7 9
4 10
5 11
11 12
11 13
3 14
7 15
10 16
10 17
11 18
9 19
4 20
8 21
6 22
11 23
23 24
10 25
18 26
5 27
14 28
27 29
12 30
20 31
27 32
27 33
3 34
5 35
30 36
19 37
32 38
12 39
19 40
18 41
21 42
40 43
33 44
23 45
29 46
29 47
3 48
21 49
6 50
14 51
36 52
6 53
42 5...

output:

result:

ok 264360 lines

Test #60:

score: 0

Accepted

time: 990ms

memory: 95940kb

input:

200000 600000
1 2
2 3
3 4
4 5
3 6
6 7
7 8
1 9
9 10
10 11
10 12
9 13
12 14
13 15
8 16
11 17
1 18
18 19
10 20
3 21
9 22
3 23
21 24
15 25
9 26
2 27
13 28
27 29
25 30
20 31
7 32
21 33
20 34
23 35
35 36
18 37
13 38
15 39
16 40
39 41
2 42
18 43
16 44
5 45
16 46
35 47
2 48
30 49
40 50
19 51
25 52
29 53
18 ...

output:

result:

ok 141118 lines

Test #61:

score: 0

Accepted

time: 999ms

memory: 99532kb

input:

200000 600000
1 2
2 3
2 4
3 5
1 6
4 7
2 8
1 9
1 10
9 11
9 12
5 13
6 14
7 15
9 16
7 17
13 18
5 19
4 20
7 21
18 22
21 23
1 24
17 25
18 26
11 27
15 28
19 29
16 30
20 31
14 32
10 33
4 34
10 35
8 36
13 37
34 38
17 39
1 40
34 41
5 42
28 43
6 44
43 45
19 46
28 47
19 48
26 49
10 50
4 51
33 52
45 53
6 54
30 ...

output:

result:

ok 191873 lines