QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#303600#5367. 递增树列yllcm100 ✓581ms3968kbC++144.0kb2024-01-12 19:55:042024-01-12 19:55:04

Judging History

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

  • [2024-01-12 19:55:04]
  • 评测
  • 测评结果:100
  • 用时:581ms
  • 内存:3968kb
  • [2024-01-12 19:55:04]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define FR first
#define SE second
using namespace std;
inline int read() {
  int x = 0; bool op = false;
  char c = getchar();
  while(!isdigit(c))op |= (c == '-'), c = getchar();
  while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return op ? -x : x;
}
const int N = 110;
const int P = 1e9 + 7;
void add(int &a, int b) {a += b; a >= P ? a -= P : 0;}
void sub(int &a, int b) {a -= b; a < 0 ? a += P : 0;}
int ksm(int x, int k) {
  int res = 1;
  for(int pw = x; k; (k & 1) ? res = 1ll * res * pw % P : 0, pw = 1ll * pw * pw % P, k >>= 1);
  return res;
}
int fac[N], ifac[N];
void init() {
  fac[0] = ifac[0] = 1;
  for(int i = 1; i < N; i++)fac[i] = 1ll * fac[i - 1] * i % P;
  ifac[N - 1] = ksm(fac[N - 1], P - 2);
  for(int i = N - 2; i; i--)ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
  return ;
}
int com(int n, int m) {return n < m || m < 0 ? 0 : 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P;}
int n, ans;
vector<int> G[N];
int sz[N];
void dfs1(int u, int fa) {
  sz[u] = 1;
  for(int v : G[u])if(v != fa)
    dfs1(v, u), sz[u] += sz[v];
  return ;
}
int g[N][N], f[N][N];
int calc(int u, int fa, int tar) {
  int sum = 0;
  g[0][1] = g[1][0] = 1; sum = 1;
  for(int v : G[u]) {
    if(v == fa || v == tar)continue;
    for(int i = sum; ~i; i--) {
      for(int j = sum; ~j; j--) {
        int val = g[i][j]; g[i][j] = 0;
        for(int x = 0; x <= sz[v]; x++) {
          int t = sz[v] - x;
          for(int y = 0; y < max(1, t); y++) {
            int c = t - y, sgn = (y & 1) ? P - 1 : 1;
            int coef = 1ll * com(sz[v], x) * fac[t] % P * ifac[c] % P * com(max(0, t - 1), y) % P;
            add(g[i + x][j + c], 1ll * sgn * coef % P * val % P);
            // if(val)cout << "trans:" << i << ' ' << j << ' ' << x << ' ' << v << ' ' << y << ' ' << sz[v] << ' ' << x << endl;
          }
        }
      }
    }
    sum += sz[v];
    // if(tar == 0) {
    //   printf("e:%d %d\n", u, v);
    //   for(int i = 0; i <= sum; i++) {
    //     for(int j = 0; j <= sum; j++) {
    //       printf("%d %d %d\n", i, j, g[i][j]);
    //     }
    //   }
    // }
  }
  return sum;
}
void init(int sum) {
  for(int i = 0; i <= sum; i++) {
    for(int j = 0; j <= sum; j++) {
      g[i][j] = 0;
    }
  }
  return ;
}
void DP(int u, int fa, int tar) {
  int sum = calc(u, fa, tar);
  for(int i = 0; i <= sum; i++) {
    for(int j = 0; j <= sum; j++) {
      for(int x = 0; x <= sz[tar]; x++) {
        for(int y = x; y <= sz[tar] - 2; y++) {
          int t = y - x;
          for(int z = 0; z <= t; z++) {
            int v = t - z, sgn = (z & 1) ? P - 1 : 1;
            int coef = 1ll * com(max(t - 1, 0), z) * ifac[v] % P * fac[j + v] % P;
            if(v)sub(coef, 1ll * com(max(t - 1, 0), z) * ifac[v - 1] % P * fac[j + v - 1] % P);
            coef = 1ll * coef * fac[i] % P * com(i + x, x) % P;
            add(f[tar][y], 1ll * sgn * coef % P * f[u][i + x] % P * g[i][j] % P);
          }
        }
      }
    }
  }
  init(sum);
  return ;
}
void calc_ans(int u, int fa) {
  // puts("calc_ans");
  int sum = calc(u, fa, 0);
  // puts("calc_ans");
  // printf("calc_ans:%d\n", u);
  for(int i = 0; i <= sum; i++) {
    for(int j = 0; j <= sum; j++) {
      // if(f[u][i])printf("g:%d %d %d\n", i, j, 1ll * g[i][j] * fac[i] % P * fac[j] % P);
      add(ans, 1ll * g[i][j] * f[u][i] % P * fac[i] % P * fac[j] % P);
    }
  }
  init(sum);
  return ;
}
void dfs2(int u, int fa) {
  calc_ans(u, fa);
  // printf("%d %d\n", u, ans);
  // for(int i = 0; i <= sz[u]; i++)printf("%d ", f[u][i]); putchar('\n');
  for(int v : G[u])if(v != fa)DP(u, fa, v);
  for(int v : G[u])if(v != fa)dfs2(v, u);
  return ;
}
int main() {
  init();
  n = read();
  for(int i = 1; i < n; i++) {
    int u = read(), v = read();
    G[u].pb(v); G[v].pb(u);
  }
  f[1][0] = 1;
  dfs1(1, 0); dfs2(1, 0);
  printf("%d\n", ans);
  return 0;
}

详细

Subtask #1:

score: 9
Accepted

Test #1:

score: 9
Accepted
time: 0ms
memory: 3660kb

input:

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

output:

712

result:

ok single line: '712'

Test #2:

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

input:

5
1 2
1 3
3 4
4 5

output:

44

result:

ok single line: '44'

Test #3:

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

input:

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

output:

576

result:

ok single line: '576'

Test #4:

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

input:

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

output:

6912

result:

ok single line: '6912'

Test #5:

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

input:

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

output:

3360

result:

ok single line: '3360'

Subtask #2:

score: 11
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 11
Accepted
time: 0ms
memory: 3676kb

input:

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

output:

389151297

result:

ok single line: '389151297'

Test #7:

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

input:

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

output:

17381952

result:

ok single line: '17381952'

Test #8:

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

input:

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

output:

4993920

result:

ok single line: '4993920'

Test #9:

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

input:

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

output:

818474475

result:

ok single line: '818474475'

Test #10:

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

input:

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

output:

16041048

result:

ok single line: '16041048'

Subtask #3:

score: 15
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #11:

score: 15
Accepted
time: 3ms
memory: 3572kb

input:

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

output:

179142361

result:

ok single line: '179142361'

Test #12:

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

input:

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

output:

680835791

result:

ok single line: '680835791'

Test #13:

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

input:

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

output:

613299173

result:

ok single line: '613299173'

Test #14:

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

input:

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

output:

990332459

result:

ok single line: '990332459'

Test #15:

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

input:

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

output:

254905851

result:

ok single line: '254905851'

Test #16:

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

input:

28
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

output:

245512165

result:

ok single line: '245512165'

Test #17:

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

input:

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

output:

440732388

result:

ok single line: '440732388'

Test #18:

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

input:

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

output:

222462817

result:

ok single line: '222462817'

Test #19:

score: 0
Accepted
time: 7ms
memory: 3628kb

input:

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

output:

915280502

result:

ok single line: '915280502'

Test #20:

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

input:

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

output:

847984210

result:

ok single line: '847984210'

Test #21:

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

input:

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

output:

203499669

result:

ok single line: '203499669'

Test #22:

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

input:

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

output:

673029660

result:

ok single line: '673029660'

Test #23:

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

input:

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

output:

463358446

result:

ok single line: '463358446'

Test #24:

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

input:

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

output:

2581770

result:

ok single line: '2581770'

Subtask #4:

score: 25
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #25:

score: 25
Accepted
time: 23ms
memory: 3636kb

input:

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

output:

475818143

result:

ok single line: '475818143'

Test #26:

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

input:

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

output:

574349748

result:

ok single line: '574349748'

Test #27:

score: 0
Accepted
time: 56ms
memory: 3632kb

input:

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

output:

284808122

result:

ok single line: '284808122'

Test #28:

score: 0
Accepted
time: 56ms
memory: 3692kb

input:

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

output:

728582173

result:

ok single line: '728582173'

Test #29:

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

input:

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

output:

830913254

result:

ok single line: '830913254'

Test #30:

score: 0
Accepted
time: 12ms
memory: 3544kb

input:

42
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

output:

118430285

result:

ok single line: '118430285'

Test #31:

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

input:

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

output:

10503098

result:

ok single line: '10503098'

Test #32:

score: 0
Accepted
time: 25ms
memory: 3876kb

input:

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

output:

236779386

result:

ok single line: '236779386'

Test #33:

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

input:

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

output:

472278844

result:

ok single line: '472278844'

Test #34:

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

input:

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

output:

918870657

result:

ok single line: '918870657'

Test #35:

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

input:

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

output:

85610243

result:

ok single line: '85610243'

Test #36:

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

input:

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

output:

773530270

result:

ok single line: '773530270'

Test #37:

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

input:

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

output:

600462689

result:

ok single line: '600462689'

Test #38:

score: 0
Accepted
time: 30ms
memory: 3684kb

input:

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

output:

563685126

result:

ok single line: '563685126'

Subtask #5:

score: 40
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #39:

score: 40
Accepted
time: 325ms
memory: 3892kb

input:

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

output:

518761011

result:

ok single line: '518761011'

Test #40:

score: 0
Accepted
time: 581ms
memory: 3620kb

input:

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

output:

908706975

result:

ok single line: '908706975'

Test #41:

score: 0
Accepted
time: 407ms
memory: 3596kb

input:

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

output:

471949293

result:

ok single line: '471949293'

Test #42:

score: 0
Accepted
time: 542ms
memory: 3736kb

input:

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

output:

112450382

result:

ok single line: '112450382'

Test #43:

score: 0
Accepted
time: 460ms
memory: 3664kb

input:

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

output:

815118641

result:

ok single line: '815118641'

Test #44:

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

input:

74
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:

367159086

result:

ok single line: '367159086'

Test #45:

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

input:

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

output:

715534167

result:

ok single line: '715534167'

Test #46:

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

input:

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

output:

192185403

result:

ok single line: '192185403'

Test #47:

score: 0
Accepted
time: 211ms
memory: 3968kb

input:

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

output:

275960320

result:

ok single line: '275960320'

Test #48:

score: 0
Accepted
time: 242ms
memory: 3720kb

input:

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

output:

79692172

result:

ok single line: '79692172'

Test #49:

score: 0
Accepted
time: 330ms
memory: 3724kb

input:

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

output:

155298272

result:

ok single line: '155298272'

Test #50:

score: 0
Accepted
time: 218ms
memory: 3716kb

input:

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

output:

347869842

result:

ok single line: '347869842'

Test #51:

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

input:

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

output:

320963094

result:

ok single line: '320963094'

Test #52:

score: 0
Accepted
time: 151ms
memory: 3724kb

input:

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

output:

203034247

result:

ok single line: '203034247'

Test #53:

score: 0
Accepted
time: 351ms
memory: 3956kb

input:

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

output:

917400836

result:

ok single line: '917400836'

Test #54:

score: 0
Accepted
time: 480ms
memory: 3716kb

input:

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

output:

716634289

result:

ok single line: '716634289'

Test #55:

score: 0
Accepted
time: 446ms
memory: 3660kb

input:

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

output:

920487193

result:

ok single line: '920487193'

Test #56:

score: 0
Accepted
time: 321ms
memory: 3660kb

input:

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

output:

689277044

result:

ok single line: '689277044'

Test #57:

score: 0
Accepted
time: 279ms
memory: 3648kb

input:

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

output:

358090698

result:

ok single line: '358090698'

Test #58:

score: 0
Accepted
time: 372ms
memory: 3656kb

input:

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

output:

959769486

result:

ok single line: '959769486'

Test #59:

score: 0
Accepted
time: 410ms
memory: 3604kb

input:

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

output:

513471410

result:

ok single line: '513471410'

Test #60:

score: 0
Accepted
time: 418ms
memory: 3724kb

input:

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

output:

632208880

result:

ok single line: '632208880'

Test #61:

score: 0
Accepted
time: 263ms
memory: 3952kb

input:

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

output:

139851470

result:

ok single line: '139851470'

Test #62:

score: 0
Accepted
time: 336ms
memory: 3724kb

input:

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

output:

248495359

result:

ok single line: '248495359'