QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#513024#7677. Easy Diameter ProblempandapythonerAC ✓461ms215852kbC++236.6kb2024-08-10 16:38:492024-08-10 16:38:50

Judging History

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

  • [2024-08-10 16:38:50]
  • 评测
  • 测评结果:AC
  • 用时:461ms
  • 内存:215852kb
  • [2024-08-10 16:38:49]
  • 提交

answer

#include <bits/stdc++.h>


using namespace std;


using ll = long long;

#define rep(i, n) for(int i = 0; i < (n); i += 1)
#define rng(i, start, end, step) for(int i = start; i < end; i += step)
#define len(a) ((int)(a).size())


mt19937 rnd(234);


struct edge {
    int to;
    int i;
};

const int maxn = 300;
const ll mod = 1e9 + 7;


ll bin_pow(ll x, ll n) {
    ll rs = 1;
    for (ll i = 1; i <= n; i *= 2, x = x * x % mod)
        if (n & i) rs = rs * x % mod;
    return rs;
}


ll inv(ll x) {
    return bin_pow(x, mod - 2);
}

int n;
vector<vector<edge>> g;
vector<pair<int, int>> edges;
int dists[maxn][maxn];
int cnt[2 * maxn - 2][maxn];
int dp1[(maxn - 1) / 2 + 1][2 * maxn - 2][maxn + 1];
int dp2[(maxn - 1) / 2 + 1][2 * maxn - 2][maxn + 1];

ll f[maxn + 1], invf[maxn + 1];


ll cnk(ll n, ll k) {
    if (n < 0 or k < 0 or k > n) return 0;
    assert(n <= maxn);
    return f[n] * invf[k] % mod * invf[n - k] % mod;
}


void dfs(int v, int p, int start, int d) {
    dists[start][v] = d;
    for (auto [to, i] : g[v]) {
        if (to == p) continue;
        dfs(to, v, start, d + 1);
    }
}


void add(int& a, int b) {
    a += b;
    if (a >= mod) a -= mod;
}

void sub(int& a, int b) {
    a -= b;
    if (a < 0) a += mod;
}


ll solve() {
    if (n == 1) {
        return 1;
    }
    f[0] = invf[0] = 1;
    for (int i = 1; i <= maxn; i += 1) {
        f[i] = f[i - 1] * i % mod;
        invf[i] = inv(f[i]);
    }
    memset(dists, 0, sizeof(dists));
    rep(v, n) dfs(v, -1, v, 0);
    memset(cnt, 0, sizeof(cnt));
    rep(e, 2 * n - 2) {
        auto [u, v] = edges[e];
        rep(x, n) if (dists[u][x] == dists[v][x] + 1) cnt[e][dists[v][x]] += 1;
    }

    int diam = -1;
    int du = -1;
    int dv = -1;
    rep(u, n) rep(v, n)
        if (dists[u][v] > diam) {
            diam = dists[u][v];
            du = u;
            dv = v;
        }
    int maxd = diam / 2;
    memset(dp1, 0, sizeof(dp1));
    memset(dp2, 0, sizeof(dp2));
    rep(e, 2 * n - 2) dp1[0][e][0] = 1;
    rep(e, 2 * n - 2) dp2[0][e][0] = 2;
    for (int d = 1; d <= maxd; d += 1) {
        rep(e, 2 * n - 2) {
            auto [u, v] = edges[e];
            if (cnt[e][d] == 0 or cnt[e ^ 1][d - 1] == 0) continue;
            rep(rest, cnt[e ^ 1][d - 1]) {
                for (auto [to, ne] : g[v]) {
                    if (to == u) continue;
                    if (cnt[ne][d - 1] == 0) continue;
                    int drest = cnt[ne ^ 1][d] - cnt[e ^ 1][d - 1];
                    assert(drest >= 0);
                    for (int take = 0; take <= rest + drest; take += 1) {
                        ll coeff = cnt[ne][d - 1] * f[cnt[ne][d - 1] - 1 + take] % mod;
                        coeff = coeff * cnk(rest + drest, take) % mod;
                        add(dp1[d][ne][rest + drest - take],
                            dp2[d - 1][e][rest] * coeff % mod);
                    }
                    if (drest == 0) continue;
                    for (int take = 0; take <= rest + drest - 1; take += 1) {
                        ll coeff = drest * f[cnt[ne][d - 1] + take] % mod;
                        coeff = coeff * cnk(rest + drest - 1, take) % mod;
                        add(dp1[d][ne][rest + drest - 1 - take],
                            dp2[d - 1][e][rest] * coeff % mod);
                    }
                }
                int can_take = cnt[e][d];
                assert(can_take > 0);
                for (int take = 1; take <= can_take; take += 1) {
                    ll coeff = can_take * f[rest + take - 1] % mod;
                    coeff = coeff * cnk(can_take - 1, take - 1) % mod;
                    add(dp1[d][e ^ 1][can_take - take],
                        dp2[d - 1][e][rest] * coeff % mod);
                }
            }
        }
        rep(e, 2 * n - 2) {
            auto [u, v] = edges[e];
            if (cnt[e][d] == 0 or cnt[e ^ 1][d] == 0) continue;
            rep(rest, cnt[e ^ 1][d]) {
                for (int take = 0; take <= rest; take += 1) {
                    ll coeff = cnt[e][d] * f[cnt[e][d] - 1 + take] % mod;
                    coeff = coeff * cnk(rest, take) % mod;
                    add(dp2[d][e][rest - take],
                        dp1[d][e][rest] * coeff % mod);
                }
                for (int take = 1; take <= cnt[e][d]; take += 1) {
                    ll coeff = cnt[e][d] * f[take - 1 + rest] % mod;
                    coeff = coeff * cnk(cnt[e][d] - 1, take - 1) % mod;
                    add(dp2[d][e ^ 1][cnt[e][d] - take],
                        dp1[d][e][rest] * coeff % mod);
                }
            }
        }
    }
    int result = 0;
    if (diam % 2 == 1) {
        int ce = -1;
        rep(e, 2 * n - 2) {
            auto [u, v] = edges[e];
            if (dists[du][u] + 1 != dists[du][v]) continue;
            if (dists[u][dv] != dists[v][dv] + 1) continue;
            if (dists[u][du] != diam / 2) continue;
            if (dists[v][dv] != diam / 2) continue;
            ce = e;
            break;
        }
        assert(ce != -1);
        int d = diam / 2;
        for (auto e : { ce, ce ^ 1 }) {
            rep(rest, cnt[e ^ 1][d]) {
                ll coeff = cnt[e][d] * f[cnt[e][d] - 1 + rest] % mod;
                add(result, dp1[d][e][rest] * coeff % mod);
            }
        }
    } else {
        int cv = -1;
        rep(v, n) {
            if (dists[v][du] != diam / 2) continue;
            if (dists[v][dv] != diam / 2) continue;
            cv = v;
            break;
        }
        assert(cv != -1);
        int d = diam / 2 - 1;
        for (auto [_, xe] : g[cv]) {
            int e = xe ^ 1;
            rep(rest, cnt[e ^ 1][d]) {
                if (cnt[e][d + 1] == 0) continue;
                ll coeff = cnt[e][d + 1] * f[cnt[e][d + 1] - 1 + rest] % mod;
                add(result, dp2[d][e][rest] * coeff % mod);
            }
        }
    }
    return result;
}


int32_t main() {
    // cerr << (sizeof(dp1) + sizeof(dp2)) / 1e6 << "\n";
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n;
    g.assign(n, vector<edge>());
    edges.resize(2 * n - 2);
    rep(i, n - 1) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        edges[2 * i] = { u, v };
        edges[2 * i + 1] = { v, u };
        g[u].push_back(edge{ v, 2 * i });
        g[v].push_back(edge{ u, 2 * i + 1 });
    }
    ll result = solve();
    cout << result << "\n";
    return 0;
}

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

详细

Test #1:

score: 100
Accepted
time: 7ms
memory: 215544kb

input:

3
1 2
3 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

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

input:

5
4 1
4 5
1 2
1 3

output:

28

result:

ok 1 number(s): "28"

Test #3:

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

input:

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

output:

116

result:

ok 1 number(s): "116"

Test #4:

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

input:

100
89 60
66 37
59 74
63 49
69 37
9 44
94 22
70 30
79 14
25 33
23 4
78 43
63 30
95 7
6 59
56 31
21 56
58 43
95 28
81 19
63 40
58 87
81 38
100 55
78 23
37 78
86 70
33 11
52 17
42 19
19 13
70 100
97 79
66 67
66 27
82 55
15 27
68 33
97 26
46 20
70 93
1 10
69 79
81 45
58 95
24 63
79 51
85 11
12 43
41 64...

output:

748786623

result:

ok 1 number(s): "748786623"

Test #5:

score: 0
Accepted
time: 36ms
memory: 215552kb

input:

300
109 123
221 101
229 22
114 101
110 258
50 79
26 1
238 47
140 271
77 213
140 125
19 179
111 96
194 114
57 101
1 251
19 13
92 238
114 116
193 140
153 238
1 173
252 220
1 22
124 197
196 214
196 224
1 138
201 90
184 56
266 154
71 184
46 15
256 27
1 69
1 32
22 182
237 196
111 1
279 91
139 196
114 80
...

output:

47013557

result:

ok 1 number(s): "47013557"

Test #6:

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

input:

300
1 77
259 130
51 79
130 1
104 58
196 26
48 112
106 22
285 30
263 252
79 196
247 134
1 41
15 133
285 100
105 72
40 217
48 62
61 183
217 261
48 86
284 12
10 106
270 230
211 285
103 27
234 16
105 288
263 68
106 194
36 130
283 88
263 217
285 21
24 27
79 75
133 153
285 157
65 293
37 133
1 56
226 152
1...

output:

160857944

result:

ok 1 number(s): "160857944"

Test #7:

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

input:

300
242 149
291 91
233 192
228 231
286 224
184 156
108 138
125 50
86 223
216 209
88 1
148 264
3 72
253 164
267 87
253 35
49 150
220 232
134 110
1 149
253 132
228 9
279 150
144 138
102 39
142 1
286 66
268 219
150 91
286 15
144 153
300 286
203 3
1 275
290 149
124 298
220 48
1 225
111 136
182 133
280 1...

output:

930240562

result:

ok 1 number(s): "930240562"

Test #8:

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

input:

300
1 236
187 186
155 44
272 1
40 47
204 39
285 197
26 243
285 59
185 77
42 209
69 220
76 55
179 173
175 238
209 18
204 277
69 147
250 44
239 1
109 15
72 185
69 131
285 127
194 112
1 285
199 299
90 35
113 42
180 256
196 209
126 292
187 56
202 286
165 204
109 1
204 20
40 209
216 201
112 79
187 176
20...

output:

881450286

result:

ok 1 number(s): "881450286"

Test #9:

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

input:

300
190 298
234 90
232 25
216 110
285 102
246 234
294 171
57 18
279 163
246 188
70 47
164 94
95 101
245 58
126 70
196 58
223 285
202 245
77 1
217 25
48 51
32 270
273 99
18 27
190 83
194 79
22 108
1 25
150 209
55 18
29 164
65 1
58 12
79 80
54 154
235 268
229 49
93 51
117 257
1 3
246 228
1 177
225 33
...

output:

41667252

result:

ok 1 number(s): "41667252"

Test #10:

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

input:

300
17 92
109 88
8 268
274 122
67 19
67 280
82 226
107 76
67 178
193 256
278 208
185 102
104 182
27 172
26 27
97 244
243 164
38 192
210 67
224 300
153 47
29 293
56 1
44 145
278 207
102 70
267 58
34 288
249 20
66 1
1 58
72 102
153 250
29 186
200 19
148 75
276 146
18 1
9 1
142 193
278 266
58 33
131 27...

output:

766720402

result:

ok 1 number(s): "766720402"

Test #11:

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

input:

300
91 264
183 296
84 43
37 244
187 89
85 243
66 230
64 57
71 172
32 283
176 190
176 269
255 18
159 283
66 232
9 202
66 222
60 172
172 290
107 208
89 290
137 239
218 47
81 29
161 110
109 171
221 67
14 236
25 155
48 298
39 254
176 280
180 66
192 113
276 155
56 273
290 43
29 289
194 124
234 266
68 35
...

output:

50070976

result:

ok 1 number(s): "50070976"

Test #12:

score: 0
Accepted
time: 19ms
memory: 215512kb

input:

300
15 7
281 65
183 284
99 55
151 93
93 29
213 183
197 155
157 76
174 226
33 143
167 36
11 176
72 262
157 237
123 262
225 151
1 151
207 225
225 265
205 281
157 251
226 117
224 290
20 218
264 278
220 69
242 195
191 253
267 99
138 11
275 115
132 242
226 270
91 248
292 226
125 11
76 38
33 159
43 281
36...

output:

832705434

result:

ok 1 number(s): "832705434"

Test #13:

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

input:

300
164 116
141 294
26 3
135 275
28 211
287 11
217 41
162 182
238 260
53 1
242 243
205 287
1 118
155 286
41 256
199 183
42 30
235 263
45 268
22 72
228 8
98 1
5 18
119 182
16 279
4 224
64 274
152 98
90 230
299 155
1 220
134 150
219 227
151 118
70 31
70 222
27 131
217 170
57 58
253 129
118 177
121 68
...

output:

101629452

result:

ok 1 number(s): "101629452"

Test #14:

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

input:

300
79 268
294 220
21 292
246 212
7 240
92 101
83 218
56 211
10 122
100 145
87 267
127 145
262 72
28 46
16 137
48 263
139 21
5 53
183 26
60 238
201 221
121 179
28 119
35 121
80 25
264 280
91 160
134 242
125 7
172 240
225 104
135 146
17 213
1 86
14 116
242 50
83 109
265 84
119 61
47 83
111 109
40 256...

output:

310258321

result:

ok 1 number(s): "310258321"

Test #15:

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

input:

300
192 25
131 179
181 92
56 148
237 182
117 243
67 191
124 276
109 246
74 105
78 266
240 29
20 40
223 230
8 19
179 162
273 272
212 72
27 208
235 26
226 48
273 267
136 277
210 132
231 242
172 177
18 231
33 67
22 133
189 167
239 41
68 165
67 38
280 101
233 230
88 203
61 117
54 226
274 74
118 290
185 ...

output:

453258233

result:

ok 1 number(s): "453258233"

Test #16:

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

input:

300
156 77
182 179
92 97
131 205
62 56
229 300
133 183
17 28
18 254
261 71
20 8
76 229
277 21
79 208
15 69
258 215
33 60
139 268
23 155
215 139
13 295
29 73
113 277
170 93
120 256
45 14
240 63
126 194
91 79
130 285
178 55
160 250
239 217
205 116
168 112
177 270
102 285
271 203
204 11
49 38
22 226
23...

output:

958129789

result:

ok 1 number(s): "958129789"

Test #17:

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

input:

300
119 249
283 2
56 179
44 78
151 230
192 268
97 190
113 211
63 98
208 268
280 103
138 69
129 292
201 224
272 298
164 35
122 184
252 132
195 182
109 94
209 165
35 201
247 267
107 112
210 86
112 235
72 211
257 10
141 274
217 297
272 290
286 219
8 59
118 170
276 214
127 193
203 41
256 115
27 96
185 7...

output:

140875750

result:

ok 1 number(s): "140875750"

Test #18:

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

input:

300
138 126
25 96
142 206
227 85
236 89
240 201
192 65
223 185
225 6
78 174
294 72
138 118
1 64
151 118
263 33
53 213
74 127
170 285
286 31
95 205
135 191
185 152
243 178
287 22
279 238
225 295
258 237
165 134
220 269
277 135
56 52
253 150
34 122
202 7
9 109
242 278
40 247
129 168
159 24
88 57
66 17...

output:

525372192

result:

ok 1 number(s): "525372192"

Test #19:

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

input:

300
282 97
194 58
153 187
281 262
160 224
179 25
127 123
68 63
75 156
260 163
177 101
158 255
238 56
267 96
132 122
123 265
282 29
162 58
73 59
166 116
185 9
157 191
141 81
297 255
228 216
269 177
190 175
10 114
125 244
66 79
241 30
33 176
182 44
36 128
207 241
65 124
39 38
227 68
90 291
152 268
17 ...

output:

866098103

result:

ok 1 number(s): "866098103"

Test #20:

score: 0
Accepted
time: 8ms
memory: 215636kb

input:

300
114 226
54 208
213 253
131 192
187 58
71 128
64 281
56 130
238 78
230 228
227 276
248 208
126 183
89 33
200 271
72 264
168 204
102 245
293 36
92 246
157 57
142 215
266 77
123 30
219 88
107 286
210 116
165 279
28 43
272 49
152 187
285 25
59 180
259 75
267 265
206 175
216 226
73 291
96 122
235 148...

output:

448016477

result:

ok 1 number(s): "448016477"

Test #21:

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

input:

300
200 109
91 267
131 106
186 52
216 131
277 227
80 239
86 149
222 90
220 112
219 16
48 150
69 249
82 138
42 1
209 5
195 235
291 146
56 261
141 70
12 66
244 37
55 122
33 241
174 172
295 78
288 151
254 270
298 132
60 146
97 281
12 246
144 28
8 292
121 163
242 197
261 10
278 100
120 211
278 35
28 290...

output:

997878224

result:

ok 1 number(s): "997878224"

Test #22:

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

input:

300
288 36
131 175
283 62
218 82
153 286
243 30
234 76
138 129
215 154
172 146
52 161
202 253
300 29
60 73
293 299
290 104
128 96
237 210
175 40
163 282
150 153
80 8
92 243
247 231
206 110
217 95
159 171
48 277
153 122
230 206
12 183
198 190
117 47
77 211
195 258
23 248
136 211
155 209
72 116
55 202...

output:

120554047

result:

ok 1 number(s): "120554047"

Test #23:

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

input:

300
47 46
292 281
41 8
211 141
62 272
109 265
12 217
156 294
272 298
90 73
131 244
69 149
138 45
90 46
77 67
43 246
55 108
128 148
27 20
30 210
88 121
109 143
289 42
35 4
264 131
38 111
134 239
164 241
101 141
256 68
179 135
262 127
79 31
266 251
30 157
282 77
198 115
112 10
27 250
2 298
183 184
8 2...

output:

684841907

result:

ok 1 number(s): "684841907"

Test #24:

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

input:

300
112 92
68 170
52 166
147 13
283 150
151 13
128 18
158 250
3 6
140 118
300 207
171 168
77 135
38 247
291 125
222 253
138 204
70 152
3 153
91 24
89 87
165 77
41 69
184 36
163 242
137 218
101 78
87 259
226 290
272 156
85 45
107 179
148 11
148 166
212 1
105 26
285 198
173 286
104 144
75 36
130 221
2...

output:

505448774

result:

ok 1 number(s): "505448774"

Test #25:

score: 0
Accepted
time: 8ms
memory: 215564kb

input:

300
223 291
260 121
235 126
290 285
184 99
266 294
20 85
65 208
18 125
127 146
80 118
82 169
248 66
35 160
295 171
103 91
235 238
289 29
239 81
225 23
255 140
84 71
38 224
202 181
54 72
53 300
272 258
261 139
196 15
58 46
297 204
291 237
86 43
228 206
98 185
187 123
12 65
16 97
203 113
25 104
1 184
...

output:

727627477

result:

ok 1 number(s): "727627477"

Test #26:

score: 0
Accepted
time: 8ms
memory: 215616kb

input:

300
159 130
18 130
7 159
84 159
26 18
13 18
140 7
143 7
265 84
181 84
123 26
241 26
94 13
76 13
281 140
2 140
14 143
1 143
260 265
72 265
4 181
96 181
51 123
121 123
193 241
191 241
197 94
20 94
226 76
208 76
161 281
27 281
199 2
217 2
45 14
63 14
223 1
240 1
196 260
32 260
236 72
5 72
214 4
255 4
1...

output:

314246397

result:

ok 1 number(s): "314246397"

Test #27:

score: 0
Accepted
time: 79ms
memory: 215580kb

input:

300
32 172
32 33
32 187
32 193
32 194
32 294
32 86
32 24
32 218
32 266
32 147
32 199
32 137
32 114
32 123
32 126
32 188
32 168
32 281
32 175
32 221
32 48
32 288
32 254
32 212
32 81
32 278
32 75
32 64
32 141
32 245
32 215
32 255
32 185
32 277
32 92
32 236
32 182
32 161
32 227
32 54
32 35
32 184
32 79...

output:

78513551

result:

ok 1 number(s): "78513551"

Test #28:

score: 0
Accepted
time: 63ms
memory: 215776kb

input:

300
228 245
228 207
228 125
228 241
228 300
228 80
228 213
228 175
228 119
228 78
228 53
228 129
228 83
228 204
228 212
228 217
228 214
228 225
228 188
228 206
228 132
228 221
228 244
228 167
228 103
228 169
228 73
228 190
228 177
228 231
228 23
228 147
228 286
228 63
228 293
228 261
228 243
228 267...

output:

32972061

result:

ok 1 number(s): "32972061"

Test #29:

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

input:

300
280 296
280 141
280 114
280 179
280 292
280 39
280 96
280 17
280 160
280 89
280 192
280 126
280 119
280 217
280 109
280 208
280 205
280 135
280 249
280 255
280 261
280 4
280 220
280 289
280 270
280 138
280 184
217 207
280 66
280 72
280 165
109 288
280 252
280 23
280 284
280 260
280 212
280 53
28...

output:

622080990

result:

ok 1 number(s): "622080990"

Test #30:

score: 0
Accepted
time: 54ms
memory: 215504kb

input:

300
66 279
66 156
66 72
66 225
66 231
66 47
72 148
66 89
225 222
66 135
66 240
66 81
66 19
66 157
66 107
66 262
66 76
240 20
66 133
156 69
66 118
66 82
156 121
66 189
66 211
66 206
66 233
66 38
66 166
66 163
189 86
66 187
66 144
66 173
66 197
66 212
66 271
66 247
66 87
66 248
66 73
240 6
66 37
66 59...

output:

610429360

result:

ok 1 number(s): "610429360"

Test #31:

score: 0
Accepted
time: 44ms
memory: 215552kb

input:

300
54 88
54 138
54 126
54 14
54 21
54 50
54 81
88 69
14 59
54 128
126 198
54 70
54 208
54 71
54 260
54 109
54 199
109 4
54 121
54 145
54 264
54 214
54 209
81 226
54 190
54 212
54 62
54 113
54 245
54 118
145 135
260 7
54 247
54 165
54 3
54 235
165 219
54 246
54 146
54 170
54 272
54 297
54 8
54 230
5...

output:

118463559

result:

ok 1 number(s): "118463559"

Test #32:

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

input:

1

output:

1

result:

ok 1 number(s): "1"

Test #33:

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

input:

2
2 1

output:

2

result:

ok 1 number(s): "2"

Test #34:

score: 0
Accepted
time: 461ms
memory: 215584kb

input:

300
96 1
1 91
1 279
1 90
30 1
210 1
1 220
140 1
1 229
52 1
66 1
1 287
1 276
92 1
1 225
1 249
1 70
71 1
1 31
193 1
144 1
289 1
1 223
180 1
103 1
201 1
1 10
1 149
145 1
1 224
11 1
1 95
221 1
118 1
1 113
1 251
134 1
203 1
54 1
1 192
1 215
1 267
24 1
1 37
39 1
1 35
9 1
1 115
1 236
1 241
1 242
1 280
1 13...

output:

56129785

result:

ok 1 number(s): "56129785"

Test #35:

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

input:

300
67 70
101 222
228 281
165 260
208 197
224 7
176 211
220 177
196 38
282 145
113 13
231 56
254 300
273 50
67 10
291 226
95 169
159 112
19 169
51 3
281 252
103 34
91 81
156 26
181 83
48 158
270 201
199 79
152 217
223 179
187 32
290 224
220 134
190 34
216 266
122 294
154 44
4 175
268 244
78 23
140 1...

output:

661025383

result:

ok 1 number(s): "661025383"

Test #36:

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

input:

4
4 3
4 1
4 2

output:

12

result:

ok 1 number(s): "12"

Test #37:

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

input:

300
158 35
140 196
291 247
187 219
114 11
56 176
100 258
231 204
88 85
257 40
126 209
31 208
286 171
46 18
278 47
220 156
180 161
145 150
107 227
111 236
10 164
227 283
10 207
273 274
267 164
27 239
171 216
272 102
241 84
145 147
55 183
160 54
121 45
112 99
121 109
131 74
66 187
3 163
288 192
205 63...

output:

383103120

result:

ok 1 number(s): "383103120"

Test #38:

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

input:

300
196 173
57 145
273 59
261 42
233 154
93 291
216 247
169 260
125 83
170 67
23 162
47 84
288 100
236 78
95 265
1 130
153 145
122 230
25 81
296 289
254 83
289 259
19 108
202 264
19 105
27 13
208 151
2 255
13 194
97 279
193 297
48 228
232 24
235 31
50 153
56 83
136 246
210 299
163 130
250 48
27 138
...

output:

825678633

result:

ok 1 number(s): "825678633"

Test #39:

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

input:

300
74 266
142 19
2 42
195 115
137 159
152 147
219 134
266 72
250 233
248 281
120 144
97 178
185 27
241 71
263 31
124 158
112 239
239 88
243 273
78 169
138 214
268 153
164 238
181 194
23 143
236 193
128 64
207 267
27 157
145 171
187 175
96 221
16 118
289 206
127 151
110 267
156 130
133 237
265 85
22...

output:

759158504

result:

ok 1 number(s): "759158504"

Test #40:

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

input:

300
238 116
265 274
178 192
198 134
172 252
130 90
186 145
210 29
225 203
13 261
139 98
154 235
185 39
300 233
149 83
181 5
241 271
41 65
289 138
127 109
16 174
275 183
217 205
256 299
49 34
18 198
263 119
17 114
108 224
28 185
226 245
171 23
39 140
148 97
53 148
142 70
210 45
54 88
48 249
249 248
1...

output:

929120317

result:

ok 1 number(s): "929120317"

Test #41:

score: 0
Accepted
time: 8ms
memory: 215552kb

input:

300
1 204
2 17
6 283
8 72
9 281
15 266
16 13
13 108
17 109
21 207
28 145
29 104
30 206
33 166
35 124
39 95
40 69
41 297
44 112
48 151
52 257
55 43
56 190
57 143
62 262
63 264
64 108
65 77
66 207
67 104
69 232
72 209
77 84
78 36
36 43
79 257
81 49
82 117
85 232
86 139
87 101
89 223
94 47
96 114
98 28...

output:

370276398

result:

ok 1 number(s): "370276398"

Test #42:

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

input:

299
2 91
3 22
6 267
10 52
11 218
12 81
14 282
16 105
18 170
23 257
24 271
25 148
29 116
31 85
32 168
34 262
35 133
36 71
40 132
43 205
44 223
45 107
46 101
51 108
54 140
55 262
57 145
62 153
64 282
71 173
72 155
75 98
76 179
81 111
85 238
86 282
90 52
93 5
94 19
95 103
99 116
101 271
102 58
58 116
1...

output:

772189998

result:

ok 1 number(s): "772189998"

Test #43:

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

input:

298
2 147
11 176
13 91
14 273
17 44
21 99
22 84
24 85
27 231
29 227
31 19
33 184
37 62
39 295
40 260
44 250
47 195
48 140
49 274
50 232
54 298
57 199
58 68
59 9
62 61
64 179
66 253
68 43
73 146
74 274
78 190
86 152
87 214
88 153
98 25
100 233
107 99
108 219
109 171
117 188
122 273
124 51
126 160
127...

output:

349212574

result:

ok 1 number(s): "349212574"

Test #44:

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

input:

297
2 295
4 177
5 276
6 73
7 223
8 232
9 105
17 114
20 192
21 100
25 198
26 265
27 117
29 160
30 119
38 261
39 68
40 53
42 191
45 141
47 264
50 258
51 262
53 35
55 202
57 105
59 37
60 259
62 48
66 78
69 228
70 81
73 56
80 119
82 22
83 107
85 68
90 88
88 74
74 78
91 71
71 35
35 67
98 44
99 266
100 78...

output:

71492179

result:

ok 1 number(s): "71492179"

Test #45:

score: 0
Accepted
time: 300ms
memory: 215636kb

input:

300
10 249
10 230
10 22
10 150
10 55
10 116
10 111
10 27
10 57
10 95
10 251
10 81
10 54
10 261
10 294
10 126
10 232
10 247
10 46
10 19
10 122
10 229
10 108
10 33
10 137
10 164
10 24
10 100
10 228
10 35
10 103
10 263
10 93
10 156
10 177
10 217
10 181
10 7
10 243
10 292
10 158
10 1
10 23
10 192
10 31
...

output:

968900539

result:

ok 1 number(s): "968900539"

Test #46:

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

input:

300
49 203
49 293
49 272
49 257
49 232
49 23
49 64
49 147
49 57
49 146
49 1
49 168
143 49
66 143
184 66
256 184
250 256
42 250
132 42
187 132
18 187
74 18
75 74
129 75
131 129
87 131
217 87
292 217
255 292
25 255
189 25
218 189
186 218
273 186
32 273
269 32
24 269
22 24
252 22
169 252
207 169
36 207...

output:

176674340

result:

ok 1 number(s): "176674340"

Test #47:

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

input:

300
18 182
18 66
18 84
18 58
18 245
18 195
18 212
18 6
18 149
18 168
18 56
18 59
18 26
18 72
18 175
18 11
42 18
181 42
45 181
109 45
278 109
284 278
271 284
275 271
48 275
126 48
143 126
172 143
156 172
264 156
22 264
34 22
289 34
108 289
115 108
293 115
162 293
167 162
101 167
231 101
106 231
75 10...

output:

275021705

result:

ok 1 number(s): "275021705"

Test #48:

score: 0
Accepted
time: 19ms
memory: 215640kb

input:

300
281 82
281 23
281 98
281 198
281 208
281 249
281 8
281 237
281 209
281 222
281 296
281 73
281 176
281 133
281 169
281 32
281 154
281 260
281 62
281 231
281 221
281 49
281 205
281 216
281 15
281 280
281 220
281 111
281 93
281 77
281 89
281 116
281 295
281 270
281 255
281 120
281 28
281 244
281 17...

output:

182485685

result:

ok 1 number(s): "182485685"

Test #49:

score: 0
Accepted
time: 72ms
memory: 215572kb

input:

300
280 287
280 114
280 136
280 110
280 24
280 107
280 131
280 41
280 224
280 141
280 248
280 72
280 50
280 68
280 226
280 65
280 74
280 288
280 123
280 171
280 193
280 137
280 33
280 71
280 286
280 270
280 103
280 94
280 267
280 164
280 5
280 161
280 79
280 16
280 292
280 51
280 30
280 272
280 158
...

output:

204507006

result:

ok 1 number(s): "204507006"

Test #50:

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

input:

300
40 13
40 178
40 267
40 296
40 227
40 80
40 107
40 170
40 34
40 291
40 55
40 33
40 38
40 46
40 145
40 265
40 272
40 120
40 96
40 71
40 64
40 257
40 252
40 300
40 122
40 256
40 133
40 208
40 155
40 193
40 180
40 73
40 51
40 32
40 126
40 31
68 40
151 68
41 151
144 41
84 144
63 84
214 63
269 214
102...

output:

712410154

result:

ok 1 number(s): "712410154"

Test #51:

score: 0
Accepted
time: 136ms
memory: 215552kb

input:

300
259 254
259 32
259 299
259 46
259 75
259 284
259 286
259 51
259 111
259 83
259 123
259 132
259 268
259 225
259 199
259 275
259 124
259 40
259 62
259 230
259 89
259 295
259 194
259 61
259 60
259 43
259 48
259 223
259 196
259 176
259 17
259 276
259 195
259 269
259 297
259 228
259 160
259 247
259 2...

output:

566236596

result:

ok 1 number(s): "566236596"

Test #52:

score: 0
Accepted
time: 36ms
memory: 215504kb

input:

300
88 222
88 251
88 26
88 99
88 107
88 23
88 81
88 299
88 283
88 19
88 9
88 261
88 16
88 65
88 92
88 244
88 160
88 157
88 228
88 121
88 63
88 171
88 86
88 97
88 211
88 122
88 37
88 264
88 124
88 226
88 208
88 183
88 116
88 52
88 281
88 2
88 139
88 108
88 138
88 7
88 15
88 165
88 155
88 131
88 296
8...

output:

685903222

result:

ok 1 number(s): "685903222"

Extra Test:

score: 0
Extra Test Passed