QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#15529#791. Mousetrapdsahifodsaf100 ✓239ms161464kbC++203.4kb2021-11-09 22:07:282022-05-03 21:58:00

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-03 21:58:00]
  • 评测
  • 测评结果:100
  • 用时:239ms
  • 内存:161464kb
  • [2021-11-09 22:07:28]
  • 提交

answer

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
#define re register
struct edge {
    int to;
    edge *nx;
} e[2001000], *la[1001000], *cnt = e;
int f[1001000], q[1001000], fa[1001000], ll[1001000], rr[1001000], no[1001000], vl[1001000], d[1001000],
    xl[1001000], clnt, cmt;
inline void addE(re int a, re int b) {
    *++cnt = (edge) {
        b, la[a]
    };
    la[a] = cnt;
    *++cnt = (edge) {
        a, la[b]
    };
    la[b] = cnt;
}
void dfs(re int a, re int ff) {
    re int xx = 0, yy = 0;
    fa[a] = ff;

    for (re edge *i = la[a]; i; i = i->nx)
        if (i->to != ff) {
            dfs(i->to, a);

            if (f[i->to] > xx)
                yy = xx, xx = f[i->to];
            else if (f[i->to] > yy)
                yy = f[i->to];

            f[a]++;
            d[a]++;
        }

    f[a] += yy;
}
int qq[4001000], nn[4001000], lazy[4001000], l1, r1, m1, vis[1001000];
inline void pushup(re int i) {
    qq[i << 1] > qq[(i << 1) | 1] ? (qq[i] = qq[i << 1], nn[i] = nn[i << 1]) : (qq[i] = qq[(i << 1) | 1],
            nn[i] = nn[(i << 1) | 1]);
}
inline void pushdown(re int i) {
    lazy[i << 1] += lazy[i];
    lazy[(i << 1) | 1] += lazy[i];
    qq[i << 1] += lazy[i];
    qq[(i << 1) | 1] += lazy[i];
    lazy[i] = 0;
}
void build(re int i, re int l, re int r) {
    if (l == r) {
        qq[i] = vl[l];
        nn[i] = l;
        return;
    }

    re int mid = (l + r) >> 1;
    build(i << 1, l, mid);
    build((i << 1) | 1, mid + 1, r);
    pushup(i);
}
void add(re int i, re int l, re int r) {
    if (l >= l1 && r <= r1) {
        qq[i] += m1;
        lazy[i] += m1;
        return;
    }

    re int mid = (l + r) >> 1;

    if (lazy[i])
        pushdown(i);

    if (mid >= l1)
        add(i << 1, l, mid);

    if (mid < r1)
        add((i << 1) | 1, mid + 1, r);

    pushup(i);
}
int find(re int a) {
    return vis[a] == a ? a : vis[a] = find(vis[a]);
}
char B[1 << 26], *S = B;
int r() {
    for (; *S < '-'; S++)
        ;

    register int x = *S++ -'0';

    for (; *S >= '0'; x = (x << 3) + (x << 1) + *S++ -'0')
        ;

    return x;
}
int main() {
    fread(B, 1, 1 << 26, stdin);
    re int n = r(), t = r(), s = r(), x, y, z;
    re long long ans = 0;

    for (re int i = 1; i < n; i++)
        x = r(), y = r(), addE(x, y);

    dfs(t, 0);

    for (re int i = s; i != t; i = fa[i])
        ll[++clnt] = i;

    for (re int i = clnt; i; i--)
        xl[i] = d[ll[i]] - 1 + xl[i + 1], vis[i] = i;

    xl[1]++;

    for (re int i = 1; i <= clnt; i++) {
        for (re edge *i1 = la[ll[i]]; i1; i1 = i1->nx)
            if (i1->to != fa[ll[i]] && i1->to != ll[i - 1]) {
                no[++cmt] = i;
                vl[cmt] = xl[i] + f[i1->to];
            }

        rr[i] = cmt;
    }

    if (cmt == 0)
        puts("0"), exit(0);

    build(1, 1, cmt);

    for (re int i = 1; i <= cmt; i++) {
        x = nn[1];
        y = no[x];
        z = find(y);

        if (!z)
            printf("%lld", qq[1] + ans), exit(0);
        else {
            vis[z] = z - 1;
            ans++;
            l1 = r1 = x;
            m1 = -1 << 25;
            add(1, 1, cmt);
            l1 = 1, r1 = rr[y], m1 = -1;
            add(1, 1, cmt);
        }
    }

    printf("%lld", cmt);
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 4ms
memory: 7888kb

input:

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

output:

2

result:

ok single line: '2'

Test #2:

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

input:

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

output:

3

result:

ok single line: '3'

Test #3:

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

input:

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

output:

0

result:

ok single line: '0'

Test #4:

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

input:

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

output:

1

result:

ok single line: '1'

Test #5:

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

input:

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

output:

3

result:

ok single line: '3'

Test #6:

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

input:

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

output:

2

result:

ok single line: '2'

Test #7:

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

input:

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

output:

5

result:

ok single line: '5'

Test #8:

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

input:

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

output:

7

result:

ok single line: '7'

Test #9:

score: 0
Accepted
time: 1ms
memory: 7848kb

input:

7 1 2
2 1
3 2
4 2
5 3
6 3
7 4

output:

3

result:

ok single line: '3'

Test #10:

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

input:

2 1 2
1 2

output:

0

result:

ok single line: '0'

Subtask #2:

score: 25
Accepted

Test #11:

score: 25
Accepted
time: 37ms
memory: 65884kb

input:

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

output:

36

result:

ok single line: '36'

Test #12:

score: 0
Accepted
time: 33ms
memory: 59604kb

input:

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

output:

36

result:

ok single line: '36'

Test #13:

score: 0
Accepted
time: 225ms
memory: 67724kb

input:

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

output:

60

result:

ok single line: '60'

Test #14:

score: 0
Accepted
time: 93ms
memory: 35524kb

input:

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

output:

74

result:

ok single line: '74'

Test #15:

score: 0
Accepted
time: 239ms
memory: 67660kb

input:

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

output:

69

result:

ok single line: '69'

Test #16:

score: 0
Accepted
time: 205ms
memory: 67680kb

input:

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

output:

67

result:

ok single line: '67'

Subtask #3:

score: 20
Accepted

Dependency #1:

100%
Accepted

Test #17:

score: 20
Accepted
time: 1ms
memory: 7888kb

input:

43 2 5
1 2
1 3
3 4
4 5
5 11
11 12
11 13
4 9
6 9
9 14
9 15
9 16
4 10
10 17
10 18
10 19
10 20
8 21
8 22
8 23
8 24
8 25
8 26
8 27
8 28
8 29
8 30
1 8
7 1
7 31
7 32
7 33
7 34
7 35
7 36
7 37
7 38
7 39
7 40
9 41
10 42
10 43

output:

7

result:

ok single line: '7'

Test #18:

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

input:

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

output:

9

result:

ok single line: '9'

Test #19:

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

input:

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

output:

14

result:

ok single line: '14'

Test #20:

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

input:

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

output:

1

result:

ok single line: '1'

Test #21:

score: 0
Accepted
time: 1ms
memory: 7676kb

input:

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

output:

0

result:

ok single line: '0'

Test #22:

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

input:

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

output:

31

result:

ok single line: '31'

Test #23:

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

input:

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

output:

40

result:

ok single line: '40'

Test #24:

score: 0
Accepted
time: 1ms
memory: 7868kb

input:

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

output:

108

result:

ok single line: '108'

Test #25:

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

input:

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

output:

107

result:

ok single line: '107'

Test #26:

score: 0
Accepted
time: 1ms
memory: 7912kb

input:

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

output:

232

result:

ok single line: '232'

Test #27:

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

input:

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

output:

231

result:

ok single line: '231'

Test #28:

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

input:

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

output:

158

result:

ok single line: '158'

Subtask #4:

score: 35
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #29:

score: 35
Accepted
time: 2ms
memory: 7932kb

input:

43 2 5
1 2
1 3
3 4
4 5
5 11
11 12
11 13
4 9
6 9
9 14
9 15
9 16
4 10
10 17
10 18
10 19
10 20
8 21
8 22
8 23
8 24
8 25
8 26
8 27
8 28
8 29
8 30
1 8
7 1
7 31
7 32
7 33
7 34
7 35
7 36
7 37
7 38
7 39
7 40
9 41
10 42
10 43

output:

7

result:

ok single line: '7'

Test #30:

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

input:

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

output:

34

result:

ok single line: '34'

Test #31:

score: 0
Accepted
time: 42ms
memory: 65948kb

input:

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

output:

18

result:

ok single line: '18'

Test #32:

score: 0
Accepted
time: 59ms
memory: 161464kb

input:

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

output:

0

result:

ok single line: '0'

Test #33:

score: 0
Accepted
time: 42ms
memory: 146160kb

input:

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

output:

1

result:

ok single line: '1'

Test #34:

score: 0
Accepted
time: 213ms
memory: 67708kb

input:

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

output:

90

result:

ok single line: '90'

Test #35:

score: 0
Accepted
time: 238ms
memory: 67676kb

input:

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

output:

72

result:

ok single line: '72'

Test #36:

score: 0
Accepted
time: 192ms
memory: 82984kb

input:

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

output:

230404

result:

ok single line: '230404'

Test #37:

score: 0
Accepted
time: 234ms
memory: 82980kb

input:

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

output:

230321

result:

ok single line: '230321'

Test #38:

score: 0
Accepted
time: 176ms
memory: 76968kb

input:

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

output:

100006

result:

ok single line: '100006'

Test #39:

score: 0
Accepted
time: 194ms
memory: 77076kb

input:

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

output:

100001

result:

ok single line: '100001'

Test #40:

score: 0
Accepted
time: 184ms
memory: 76940kb

input:

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

output:

100005

result:

ok single line: '100005'