QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#387875#5357. 芒果冰加了空气cqbzly100 ✓119ms200040kbC++141.3kb2024-04-12 22:17:462024-04-12 22:17:46

Judging History

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

  • [2024-04-12 22:17:46]
  • 评测
  • 测评结果:100
  • 用时:119ms
  • 内存:200040kb
  • [2024-04-12 22:17:46]
  • 提交

answer

// 
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define db double
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int mod=1e9+7;
const int N=5005;
int n,sz[N];
ll f[N][N],fac[N],inv[N];
vector<int>G[N];
ll fpow(ll x,ll y=mod-2){
    ll z(1);
    for(;y;y>>=1){
        if(y&1)z=z*x%mod;
        x=x*x%mod;
    }return z;
}
void init(int n){
    fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
    inv[n]=fpow(fac[n]);for(int i=n;i>=1;i--)inv[i-1]=inv[i]*i%mod;
}
ll binom(int x,int y){
    if(x<0||y<0||x<y)return 0;
    return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
void dfs(int u,int topf){
    f[u][1]=1,sz[u]=1;
    for(auto v:G[u]){
        if(v==topf)continue;
        dfs(v,u);
        for(int i=sz[u];i>=1;i--){
            for(int j=sz[v];j>=1;j--){
                f[u][i+j]=(f[u][i+j]+f[u][i]*f[v][j]%mod*binom(i+j-1,j))%mod;
            }
            f[u][i]=f[u][i]*f[v][0]%mod;
        }
        sz[u]+=sz[v];
    }
    for(int i=sz[u]-1;i>=0;i--)f[u][i]=(f[u][i]+f[u][i+1])%mod;
}
int main(){
    //freopen("data.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n,init(n);
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        G[x].pb(y),G[y].pb(x);
    }
    dfs(1,0);
    cout<<(f[1][0]+mod)%mod;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 0ms
memory: 3780kb

input:

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

output:

310862

result:

ok single line: '310862'

Test #2:

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

input:

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

output:

64804

result:

ok single line: '64804'

Test #3:

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

input:

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

output:

258182

result:

ok single line: '258182'

Test #4:

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

input:

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

output:

16796

result:

ok single line: '16796'

Test #5:

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

input:

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

output:

78384

result:

ok single line: '78384'

Test #6:

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

input:

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

output:

38896

result:

ok single line: '38896'

Test #7:

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

input:

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

output:

609656

result:

ok single line: '609656'

Test #8:

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

input:

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

output:

64804

result:

ok single line: '64804'

Test #9:

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

input:

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

output:

118638

result:

ok single line: '118638'

Test #10:

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

input:

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

output:

22438

result:

ok single line: '22438'

Test #11:

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

input:

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

output:

16796

result:

ok single line: '16796'

Test #12:

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

input:

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

output:

82316

result:

ok single line: '82316'

Test #13:

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

input:

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

output:

13700

result:

ok single line: '13700'

Test #14:

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

input:

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

output:

3996

result:

ok single line: '3996'

Test #15:

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

input:

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

output:

3490

result:

ok single line: '3490'

Test #16:

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

input:

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

output:

1430

result:

ok single line: '1430'

Test #17:

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

input:

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

output:

1430

result:

ok single line: '1430'

Test #18:

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

input:

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

output:

3232

result:

ok single line: '3232'

Test #19:

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

input:

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

output:

8970

result:

ok single line: '8970'

Test #20:

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

input:

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

output:

3996

result:

ok single line: '3996'

Test #21:

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

input:

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

output:

3332

result:

ok single line: '3332'

Test #22:

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

input:

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

output:

1870

result:

ok single line: '1870'

Test #23:

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

input:

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

output:

2416

result:

ok single line: '2416'

Test #24:

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

input:

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

output:

2802

result:

ok single line: '2802'

Test #25:

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

input:

3
1 2
2 3

output:

5

result:

ok single line: '5'

Test #26:

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

input:

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

output:

78904

result:

ok single line: '78904'

Subtask #2:

score: 10
Accepted

Test #27:

score: 10
Accepted
time: 118ms
memory: 134036kb

input:

5000
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 53
...

output:

138172849

result:

ok single line: '138172849'

Test #28:

score: 0
Accepted
time: 20ms
memory: 90748kb

input:

2195
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 53
...

output:

34585647

result:

ok single line: '34585647'

Test #29:

score: 0
Accepted
time: 67ms
memory: 100120kb

input:

3927
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 53
...

output:

179814607

result:

ok single line: '179814607'

Test #30:

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

input:

857
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 53
5...

output:

997745350

result:

ok single line: '997745350'

Test #31:

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

input:

1157
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 53
...

output:

459486613

result:

ok single line: '459486613'

Test #32:

score: 0
Accepted
time: 110ms
memory: 125396kb

input:

4958
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 53
...

output:

276300910

result:

ok single line: '276300910'

Test #33:

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

input:

2758
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 53
...

output:

161112418

result:

ok single line: '161112418'

Test #34:

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

input:

2905
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 53
...

output:

501208825

result:

ok single line: '501208825'

Test #35:

score: 0
Accepted
time: 18ms
memory: 84704kb

input:

2047
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 53
...

output:

995483163

result:

ok single line: '995483163'

Test #36:

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

input:

3098
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 53
...

output:

324344238

result:

ok single line: '324344238'

Subtask #3:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #37:

score: 10
Accepted
time: 0ms
memory: 3824kb

input:

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

output:

85351498

result:

ok single line: '85351498'

Test #38:

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

input:

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

output:

469047999

result:

ok single line: '469047999'

Test #39:

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

input:

20
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
1 20

output:

564120378

result:

ok single line: '564120378'

Test #40:

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

input:

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

output:

663766512

result:

ok single line: '663766512'

Test #41:

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

input:

20
1 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
12 20

output:

476848595

result:

ok single line: '476848595'

Test #42:

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

input:

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

output:

488457335

result:

ok single line: '488457335'

Test #43:

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

input:

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

output:

752198316

result:

ok single line: '752198316'

Test #44:

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

input:

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

output:

542252149

result:

ok single line: '542252149'

Test #45:

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

input:

20
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
6 20

output:

194863442

result:

ok single line: '194863442'

Test #46:

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

input:

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

output:

23651915

result:

ok single line: '23651915'

Test #47:

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

input:

20
1 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
3 20

output:

492545226

result:

ok single line: '492545226'

Test #48:

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

input:

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

output:

351974281

result:

ok single line: '351974281'

Test #49:

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

input:

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

output:

781206475

result:

ok single line: '781206475'

Test #50:

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

input:

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

output:

859563531

result:

ok single line: '859563531'

Test #51:

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

input:

20
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
15 20

output:

376484809

result:

ok single line: '376484809'

Test #52:

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

input:

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

output:

785968691

result:

ok single line: '785968691'

Test #53:

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

input:

20
1 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
7 20

output:

931047734

result:

ok single line: '931047734'

Test #54:

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

input:

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

output:

162400297

result:

ok single line: '162400297'

Test #55:

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

input:

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

output:

250839719

result:

ok single line: '250839719'

Test #56:

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

input:

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

output:

219471148

result:

ok single line: '219471148'

Test #57:

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

input:

20
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
14 20

output:

194863442

result:

ok single line: '194863442'

Test #58:

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

input:

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

output:

493588236

result:

ok single line: '493588236'

Test #59:

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

input:

20
1 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
19 20

output:

399365910

result:

ok single line: '399365910'

Test #60:

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

input:

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

output:

24503169

result:

ok single line: '24503169'

Subtask #4:

score: 25
Accepted

Dependency #3:

100%
Accepted

Test #61:

score: 25
Accepted
time: 1ms
memory: 5876kb

input:

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

output:

207339010

result:

ok single line: '207339010'

Test #62:

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

input:

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

output:

444163693

result:

ok single line: '444163693'

Test #63:

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

input:

57
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 53
53...

output:

253999939

result:

ok single line: '253999939'

Test #64:

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

input:

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

output:

404981769

result:

ok single line: '404981769'

Test #65:

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

input:

57
1 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
27 55...

output:

454043074

result:

ok single line: '454043074'

Test #66:

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

input:

57
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
28 27
29 27
30 27
31 27
32 27
33 27
34 27
35 27
36 27
37 27
38 27
39 27
40 27
41 27
42 27
43 27
44 27
45 27
46 27
47 27
48 27
49 27
50 27
51 27
52 27
53 27
54...

output:

832905030

result:

ok single line: '832905030'

Test #67:

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

input:

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

output:

805899378

result:

ok single line: '805899378'

Test #68:

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

input:

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

output:

705490172

result:

ok single line: '705490172'

Test #69:

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

input:

57
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 53
53...

output:

634401149

result:

ok single line: '634401149'

Test #70:

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

input:

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

output:

269904773

result:

ok single line: '269904773'

Test #71:

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

input:

57
1 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
27 55...

output:

310957820

result:

ok single line: '310957820'

Test #72:

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

input:

57
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
30 29
31 29
32 29
33 29
34 29
35 29
36 29
37 29
38 29
39 29
40 29
41 29
42 29
43 29
44 29
45 29
46 29
47 29
48 29
49 29
50 29
51 29
52 29
53 29
54...

output:

529454602

result:

ok single line: '529454602'

Test #73:

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

input:

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

output:

742352534

result:

ok single line: '742352534'

Test #74:

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

input:

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

output:

570704962

result:

ok single line: '570704962'

Test #75:

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

input:

60
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 53
53...

output:

767444667

result:

ok single line: '767444667'

Test #76:

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

input:

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

output:

735270809

result:

ok single line: '735270809'

Test #77:

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

input:

60
1 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
27 55...

output:

859967454

result:

ok single line: '859967454'

Test #78:

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

input:

60
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
31 30
32 30
33 30
34 30
35 30
36 30
37 30
38 30
39 30
40 30
41 30
42 30
43 30
44 30
45 30
46 30
47 30
48 30
49 30
50 30
51 30
52 30
53 30
54...

output:

707392314

result:

ok single line: '707392314'

Test #79:

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

input:

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

output:

552215869

result:

ok single line: '552215869'

Test #80:

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

input:

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

output:

214555805

result:

ok single line: '214555805'

Test #81:

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

input:

60
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 53
53...

output:

11910602

result:

ok single line: '11910602'

Test #82:

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

input:

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

output:

234907268

result:

ok single line: '234907268'

Test #83:

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

input:

60
1 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
27 55...

output:

206263445

result:

ok single line: '206263445'

Test #84:

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

input:

60
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
29 28
30 28
31 28
32 28
33 28
34 28
35 28
36 28
37 28
38 28
39 28
40 28
41 28
42 28
43 28
44 28
45 28
46 28
47 28
48 28
49 28
50 28
51 28
52 28
53 28
54...

output:

731555292

result:

ok single line: '731555292'

Subtask #5:

score: 20
Accepted

Dependency #4:

100%
Accepted

Test #85:

score: 20
Accepted
time: 3ms
memory: 20352kb

input:

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

output:

23954621

result:

ok single line: '23954621'

Test #86:

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

input:

398
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 53
5...

output:

952035142

result:

ok single line: '952035142'

Test #87:

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

input:

398
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 53
5...

output:

875356010

result:

ok single line: '875356010'

Test #88:

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

input:

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

output:

706621405

result:

ok single line: '706621405'

Test #89:

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

input:

398
1 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
27 5...

output:

972656594

result:

ok single line: '972656594'

Test #90:

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

input:

398
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 53
5...

output:

537838315

result:

ok single line: '537838315'

Test #91:

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

input:

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

output:

967361004

result:

ok single line: '967361004'

Test #92:

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

input:

398
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 53
5...

output:

513218946

result:

ok single line: '513218946'

Test #93:

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

input:

398
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 53
5...

output:

16995876

result:

ok single line: '16995876'

Test #94:

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

input:

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

output:

471041228

result:

ok single line: '471041228'

Test #95:

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

input:

398
1 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
27 5...

output:

972656594

result:

ok single line: '972656594'

Test #96:

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

input:

398
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 53
5...

output:

500366412

result:

ok single line: '500366412'

Test #97:

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

input:

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

output:

436627764

result:

ok single line: '436627764'

Test #98:

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

input:

399
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 53
5...

output:

182295868

result:

ok single line: '182295868'

Test #99:

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

input:

399
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 53
5...

output:

566795449

result:

ok single line: '566795449'

Test #100:

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

input:

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

output:

964271954

result:

ok single line: '964271954'

Test #101:

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

input:

399
1 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
27 5...

output:

631187518

result:

ok single line: '631187518'

Test #102:

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

input:

399
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 53
5...

output:

810088955

result:

ok single line: '810088955'

Test #103:

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

input:

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

output:

690741801

result:

ok single line: '690741801'

Test #104:

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

input:

399
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 53
5...

output:

572499025

result:

ok single line: '572499025'

Test #105:

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

input:

399
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 53
5...

output:

907316692

result:

ok single line: '907316692'

Test #106:

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

input:

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

output:

960051317

result:

ok single line: '960051317'

Test #107:

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

input:

399
1 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
27 5...

output:

682235485

result:

ok single line: '682235485'

Test #108:

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

input:

399
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 53
5...

output:

728680806

result:

ok single line: '728680806'

Subtask #6:

score: 30
Accepted

Dependency #5:

100%
Accepted

Test #109:

score: 30
Accepted
time: 78ms
memory: 128332kb

input:

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

output:

796804219

result:

ok single line: '796804219'

Test #110:

score: 0
Accepted
time: 88ms
memory: 136244kb

input:

4997
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 53
...

output:

225232488

result:

ok single line: '225232488'

Test #111:

score: 0
Accepted
time: 112ms
memory: 137536kb

input:

4997
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 53
...

output:

254007764

result:

ok single line: '254007764'

Test #112:

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

input:

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

output:

57313311

result:

ok single line: '57313311'

Test #113:

score: 0
Accepted
time: 55ms
memory: 116264kb

input:

4997
1 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
27 ...

output:

412800517

result:

ok single line: '412800517'

Test #114:

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

input:

4997
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 53
...

output:

700780854

result:

ok single line: '700780854'

Test #115:

score: 0
Accepted
time: 77ms
memory: 173940kb

input:

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

output:

743222193

result:

ok single line: '743222193'

Test #116:

score: 0
Accepted
time: 99ms
memory: 151820kb

input:

4997
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 53
...

output:

348028553

result:

ok single line: '348028553'

Test #117:

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

input:

4997
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 53
...

output:

89020021

result:

ok single line: '89020021'

Test #118:

score: 0
Accepted
time: 53ms
memory: 153008kb

input:

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

output:

184832304

result:

ok single line: '184832304'

Test #119:

score: 0
Accepted
time: 66ms
memory: 175028kb

input:

4997
1 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
27 ...

output:

774236523

result:

ok single line: '774236523'

Test #120:

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

input:

4997
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 53
...

output:

711005791

result:

ok single line: '711005791'

Test #121:

score: 0
Accepted
time: 71ms
memory: 153800kb

input:

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

output:

268262891

result:

ok single line: '268262891'

Test #122:

score: 0
Accepted
time: 98ms
memory: 174484kb

input:

5000
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 53
...

output:

913953947

result:

ok single line: '913953947'

Test #123:

score: 0
Accepted
time: 119ms
memory: 159156kb

input:

5000
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 53
...

output:

19609898

result:

ok single line: '19609898'

Test #124:

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

input:

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

output:

530310194

result:

ok single line: '530310194'

Test #125:

score: 0
Accepted
time: 66ms
memory: 195116kb

input:

5000
1 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
27 ...

output:

111211564

result:

ok single line: '111211564'

Test #126:

score: 0
Accepted
time: 92ms
memory: 196600kb

input:

5000
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 53
...

output:

536050287

result:

ok single line: '536050287'

Test #127:

score: 0
Accepted
time: 78ms
memory: 197628kb

input:

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

output:

203664810

result:

ok single line: '203664810'

Test #128:

score: 0
Accepted
time: 89ms
memory: 200040kb

input:

5000
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 53
...

output:

464943202

result:

ok single line: '464943202'

Test #129:

score: 0
Accepted
time: 103ms
memory: 199736kb

input:

5000
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 53
...

output:

221495654

result:

ok single line: '221495654'

Test #130:

score: 0
Accepted
time: 60ms
memory: 198900kb

input:

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

output:

378087212

result:

ok single line: '378087212'

Test #131:

score: 0
Accepted
time: 61ms
memory: 198832kb

input:

5000
1 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
27 ...

output:

984482107

result:

ok single line: '984482107'

Test #132:

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

input:

5000
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 53
...

output:

317476245

result:

ok single line: '317476245'