QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#714753#8001. 公交线路hos_lyric#100 ✓283ms4932kbC++1413.9kb2024-11-06 05:28:272024-11-06 05:28:28

Judging History

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

  • [2024-11-06 05:28:28]
  • 评测
  • 测评结果:100
  • 用时:283ms
  • 内存:4932kb
  • [2024-11-06 05:28:27]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")

////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
  static constexpr unsigned M = M_;
  unsigned x;
  constexpr ModInt() : x(0U) {}
  constexpr ModInt(unsigned x_) : x(x_ % M) {}
  constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
  constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
  constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
  ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
  ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
  ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
  ModInt pow(long long e) const {
    if (e < 0) return inv().pow(-e);
    ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
  }
  ModInt inv() const {
    unsigned a = M, b = x; int y = 0, z = 1;
    for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
    assert(a == 1U); return ModInt(y);
  }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
  ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
  ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
  ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
  ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
  template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
  template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
  template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
  template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
  explicit operator bool() const { return x; }
  bool operator==(const ModInt &a) const { return (x == a.x); }
  bool operator!=(const ModInt &a) const { return (x != a.x); }
  friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
constexpr unsigned MO = 998244353U;
constexpr unsigned MO2 = 2U * MO;
constexpr int FFT_MAX = 23;
using Mint = ModInt<MO>;
constexpr Mint FFT_ROOTS[FFT_MAX + 1] = {1U, 998244352U, 911660635U, 372528824U, 929031873U, 452798380U, 922799308U, 781712469U, 476477967U, 166035806U, 258648936U, 584193783U, 63912897U, 350007156U, 666702199U, 968855178U, 629671588U, 24514907U, 996173970U, 363395222U, 565042129U, 733596141U, 267099868U, 15311432U};
constexpr Mint INV_FFT_ROOTS[FFT_MAX + 1] = {1U, 998244352U, 86583718U, 509520358U, 337190230U, 87557064U, 609441965U, 135236158U, 304459705U, 685443576U, 381598368U, 335559352U, 129292727U, 358024708U, 814576206U, 708402881U, 283043518U, 3707709U, 121392023U, 704923114U, 950391366U, 428961804U, 382752275U, 469870224U};
constexpr Mint FFT_RATIOS[FFT_MAX] = {911660635U, 509520358U, 369330050U, 332049552U, 983190778U, 123842337U, 238493703U, 975955924U, 603855026U, 856644456U, 131300601U, 842657263U, 730768835U, 942482514U, 806263778U, 151565301U, 510815449U, 503497456U, 743006876U, 741047443U, 56250497U, 867605899U};
constexpr Mint INV_FFT_RATIOS[FFT_MAX] = {86583718U, 372528824U, 373294451U, 645684063U, 112220581U, 692852209U, 155456985U, 797128860U, 90816748U, 860285882U, 927414960U, 354738543U, 109331171U, 293255632U, 535113200U, 308540755U, 121186627U, 608385704U, 438932459U, 359477183U, 824071951U, 103369235U};

// as[rev(i)] <- \sum_j \zeta^(ij) as[j]
void fft(Mint *as, int n) {
  assert(!(n & (n - 1))); assert(1 <= n); assert(n <= 1 << FFT_MAX);
  int m = n;
  if (m >>= 1) {
    for (int i = 0; i < m; ++i) {
      const unsigned x = as[i + m].x;  // < MO
      as[i + m].x = as[i].x + MO - x;  // < 2 MO
      as[i].x += x;  // < 2 MO
    }
  }
  if (m >>= 1) {
    Mint prod = 1U;
    for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
      for (int i = i0; i < i0 + m; ++i) {
        const unsigned x = (prod * as[i + m]).x;  // < MO
        as[i + m].x = as[i].x + MO - x;  // < 3 MO
        as[i].x += x;  // < 3 MO
      }
      prod *= FFT_RATIOS[__builtin_ctz(++h)];
    }
  }
  for (; m; ) {
    if (m >>= 1) {
      Mint prod = 1U;
      for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
        for (int i = i0; i < i0 + m; ++i) {
          const unsigned x = (prod * as[i + m]).x;  // < MO
          as[i + m].x = as[i].x + MO - x;  // < 4 MO
          as[i].x += x;  // < 4 MO
        }
        prod *= FFT_RATIOS[__builtin_ctz(++h)];
      }
    }
    if (m >>= 1) {
      Mint prod = 1U;
      for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
        for (int i = i0; i < i0 + m; ++i) {
          const unsigned x = (prod * as[i + m]).x;  // < MO
          as[i].x = (as[i].x >= MO2) ? (as[i].x - MO2) : as[i].x;  // < 2 MO
          as[i + m].x = as[i].x + MO - x;  // < 3 MO
          as[i].x += x;  // < 3 MO
        }
        prod *= FFT_RATIOS[__builtin_ctz(++h)];
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    as[i].x = (as[i].x >= MO2) ? (as[i].x - MO2) : as[i].x;  // < 2 MO
    as[i].x = (as[i].x >= MO) ? (as[i].x - MO) : as[i].x;  // < MO
  }
}

// as[i] <- (1/n) \sum_j \zeta^(-ij) as[rev(j)]
void invFft(Mint *as, int n) {
  assert(!(n & (n - 1))); assert(1 <= n); assert(n <= 1 << FFT_MAX);
  int m = 1;
  if (m < n >> 1) {
    Mint prod = 1U;
    for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
      for (int i = i0; i < i0 + m; ++i) {
        const unsigned long long y = as[i].x + MO - as[i + m].x;  // < 2 MO
        as[i].x += as[i + m].x;  // < 2 MO
        as[i + m].x = (prod.x * y) % MO;  // < MO
      }
      prod *= INV_FFT_RATIOS[__builtin_ctz(++h)];
    }
    m <<= 1;
  }
  for (; m < n >> 1; m <<= 1) {
    Mint prod = 1U;
    for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
      for (int i = i0; i < i0 + (m >> 1); ++i) {
        const unsigned long long y = as[i].x + MO2 - as[i + m].x;  // < 4 MO
        as[i].x += as[i + m].x;  // < 4 MO
        as[i].x = (as[i].x >= MO2) ? (as[i].x - MO2) : as[i].x;  // < 2 MO
        as[i + m].x = (prod.x * y) % MO;  // < MO
      }
      for (int i = i0 + (m >> 1); i < i0 + m; ++i) {
        const unsigned long long y = as[i].x + MO - as[i + m].x;  // < 2 MO
        as[i].x += as[i + m].x;  // < 2 MO
        as[i + m].x = (prod.x * y) % MO;  // < MO
      }
      prod *= INV_FFT_RATIOS[__builtin_ctz(++h)];
    }
  }
  if (m < n) {
    for (int i = 0; i < m; ++i) {
      const unsigned y = as[i].x + MO2 - as[i + m].x;  // < 4 MO
      as[i].x += as[i + m].x;  // < 4 MO
      as[i + m].x = y;  // < 4 MO
    }
  }
  const Mint invN = Mint(n).inv();
  for (int i = 0; i < n; ++i) {
    as[i] *= invN;
  }
}

void fft(vector<Mint> &as) {
  fft(as.data(), as.size());
}
void invFft(vector<Mint> &as) {
  invFft(as.data(), as.size());
}

vector<Mint> convolve(vector<Mint> as, vector<Mint> bs) {
  if (as.empty() || bs.empty()) return {};
  const int len = as.size() + bs.size() - 1;

  if (as.size() <= 16 || bs.size() <= 16) {
    vector<Mint> cs(len, 0);
    for (int i = 0; i < (int)as.size(); ++i) for (int j = 0; j < (int)bs.size(); ++j) {
      cs[i + j] += as[i] * bs[j];
    }
    return cs;
  }

  int n = 1;
  for (; n < len; n <<= 1) {}
  as.resize(n); fft(as);
  bs.resize(n); fft(bs);
  for (int i = 0; i < n; ++i) as[i] *= bs[i];
  invFft(as);
  as.resize(len);
  return as;
}
vector<Mint> square(vector<Mint> as) {
  if (as.empty()) return {};
  const int len = as.size() + as.size() - 1;
  int n = 1;
  for (; n < len; n <<= 1) {}
  as.resize(n); fft(as);
  for (int i = 0; i < n; ++i) as[i] *= as[i];
  invFft(as);
  as.resize(len);
  return as;
}
// m := |as|, n := |bs|
// cs[k] = \sum[i-j=k] as[i] bs[j]  (0 <= k <= m-n)
// transpose of ((multiply by bs): K^[0,m-n] -> K^[0,m-1])
vector<Mint> middle(vector<Mint> as, vector<Mint> bs) {
  const int m = as.size(), n = bs.size();
  assert(m >= n); assert(n >= 1);
  int len = 1;
  for (; len < m; len <<= 1) {}
  as.resize(len, 0);
  fft(as);
  std::reverse(bs.begin(), bs.end());
  bs.resize(len, 0);
  fft(bs);
  for (int i = 0; i < len; ++i) as[i] *= bs[i];
  invFft(as);
  as.resize(m);
  as.erase(as.begin(), as.begin() + (n - 1));
  return as;
}
////////////////////////////////////////////////////////////////////////////////


constexpr int LIM_INV = 6010;
Mint inv[LIM_INV], fac[LIM_INV], invFac[LIM_INV];

void prepare() {
  inv[1] = 1;
  for (int i = 2; i < LIM_INV; ++i) {
    inv[i] = -((Mint::M / i) * inv[Mint::M % i]);
  }
  fac[0] = invFac[0] = 1;
  for (int i = 1; i < LIM_INV; ++i) {
    fac[i] = fac[i - 1] * i;
    invFac[i] = invFac[i - 1] * inv[i];
  }
}
Mint binom(Int n, Int k) {
  if (n < 0) {
    if (k >= 0) {
      return ((k & 1) ? -1 : +1) * binom(-n + k - 1, k);
    } else if (n - k >= 0) {
      return (((n - k) & 1) ? -1 : +1) * binom(-k - 1, n - k);
    } else {
      return 0;
    }
  } else {
    if (0 <= k && k <= n) {
      assert(n < LIM_INV);
      return fac[n] * invFac[k] * invFac[n - k];
    } else {
      return 0;
    }
  }
}

////////////////////////////////////////////////////////////////////////////////


// a^e,  0 <= e < 2^32
struct Power {
  static constexpr int E = 16;
  vector<Mint> baby, giant;
  Power() {}
  explicit Power(Mint a) : baby((1 << E) + 1), giant(1 << E) {
    baby[0] = 1;
    for (int i = 1; i <= 1 << E; ++i) baby[i] = baby[i - 1] * a;
    giant[0] = 1;
    for (int i = 1; i < 1 << E; ++i) giant[i] = giant[i - 1] * baby[1 << E];
  }
  Mint operator()(unsigned e) const {
    return giant[e >> E] * baby[e & ((1 << E) - 1)];
  }
} two(2), invTwo(Mint(2).inv());


int N;
vector<int> A, B;

vector<vector<int>> graph;
vector<int> par, sz, leaf;

void dfs(int u, int p) {
  par[u] = p;
  sz[u] += 1;
  if (graph[u].size() == 1) leaf[u] += 1;
  for (const int v : graph[u]) if (p != v) {
    dfs(v, u);
    sz[u] += sz[v];
    leaf[u] += leaf[v];
  }
}

/*
  no leaf is within its region
  
  (a, b)
    a: sz
    b: # leaf
  
  PIE 0 <= c <= b
  forbidden path:
    - from different region
    - at least 1 endpoint is PIEed
  (1/2)^((binom(\sum a, 2) - \sum binom(a, 2)) - (binom(\sum (a-c), 2) - \sum binom(a-c, 2)))
*/
int c2(int a) {
  return a*(a-1)/2;
}
Mint calc(vector<pair<int, int>> fs) {
  for (auto &f : fs) swap(f.first, f.second);
  sort(fs.begin(), fs.end());
  for (auto &f : fs) swap(f.first, f.second);
  
  int sumA = 0, sumB = 0;
  int sumA2 = 0;
  vector<Mint> prod{1};
  for (const auto &f : fs) {
    const int a = f.first;
    const int b = f.second;
    sumA += a;
    sumB += b;
    sumA2 += c2(a);
    vector<Mint> gs(b + 1);
    for (int c = 0; c <= b; ++c) {
      gs[c] = binom(b, c) * invTwo(c2(a-c));
    }
    prod = convolve(prod, gs);
  }
  Mint ret = 0;
  for (int sumC = 0; sumC <= sumB; ++sumC) {
    ret += (sumC&1?-1:+1) * two(c2(sumA-sumC)) * prod[sumC];
  }
  ret *= invTwo(c2(sumA) - sumA2);
// cerr<<"fs = "<<fs<<": ret = "<<(ret*Mint(2).pow(c2(N)))<<"/2^"<<c2(N)<<endl;
  return ret;
}

int main() {
  prepare();
  
  for (; ~scanf("%d", &N); ) {
    A.resize(N - 1);
    B.resize(N - 1);
    for (int i = 0; i < N - 1; ++i) {
      scanf("%d%d", &A[i], &B[i]);
      --A[i];
      --B[i];
    }
    
    graph.assign(N, {});
    for (int i = 0; i < N - 1; ++i) {
      graph[A[i]].push_back(B[i]);
      graph[B[i]].push_back(A[i]);
    }
    par.assign(N, -1);
    sz.assign(N, 0);
    leaf.assign(N, 0);
    const int r = 0;
    dfs(r, -1);
    
    Mint ans = 0;
    for (int u = 0; u < N; ++u) {
      // each leaf can reach u
      vector<pair<int, int>> fs;
      fs.emplace_back(1, 0);
      if (r != u) {
        fs.emplace_back(sz[r] - sz[u], leaf[r] - leaf[u]);
      }
      for (const int v : graph[u]) if (par[u] != v) {
        fs.emplace_back(sz[v], leaf[v]);
      }
      ans += calc(fs);
    }
    for (int u = 0; u < N; ++u) if (r != u) {
      // each leaf can reach both par[u] and u
      vector<pair<int, int>> fs;
      fs.emplace_back(sz[r] - sz[u], leaf[r] - leaf[u]);
      fs.emplace_back(sz[u], leaf[u]);
      ans -= calc(fs);
    }
    ans *= two(c2(N));
    printf("%u\n", ans.x);
  }
  return 0;
}

详细


Pretests


Final Tests

Test #1:

score: 5
Accepted
time: 2ms
memory: 4292kb

input:

6
2 3
6 4
3 6
5 1
2 1

output:

29696

result:

ok 1 number(s): "29696"

Test #2:

score: 5
Accepted
time: 2ms
memory: 4248kb

input:

6
2 5
5 6
4 5
3 5
1 3

output:

28300

result:

ok 1 number(s): "28300"

Test #3:

score: 5
Accepted
time: 2ms
memory: 4416kb

input:

6
5 6
1 3
1 6
6 2
4 6

output:

28300

result:

ok 1 number(s): "28300"

Test #4:

score: 5
Accepted
time: 2ms
memory: 4292kb

input:

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

output:

289372450

result:

ok 1 number(s): "289372450"

Test #5:

score: 5
Accepted
time: 2ms
memory: 4480kb

input:

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

output:

49248931

result:

ok 1 number(s): "49248931"

Test #6:

score: 5
Accepted
time: 2ms
memory: 4296kb

input:

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

output:

988134025

result:

ok 1 number(s): "988134025"

Test #7:

score: 5
Accepted
time: 2ms
memory: 4308kb

input:

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

output:

715692613

result:

ok 1 number(s): "715692613"

Test #8:

score: 5
Accepted
time: 4ms
memory: 4724kb

input:

2875
2669 435
473 838
1040 343
857 2027
1983 764
2420 719
1042 1284
239 1269
546 2305
2203 927
2827 972
242 262
2528 1885
1106 2457
690 1843
2282 697
1538 1937
2315 1817
2720 928
381 568
2288 2058
1715 2080
752 987
1262 348
2181 270
609 214
2377 55
870 1970
1532 1310
1522 1536
1274 1051
646 1135
196...

output:

120122964

result:

ok 1 number(s): "120122964"

Test #9:

score: 5
Accepted
time: 4ms
memory: 4784kb

input:

2923
383 1614
1665 1544
2468 2163
257 1400
1093 214
2721 2083
1115 2684
2572 1557
1888 2045
1889 1742
85 2467
92 2598
61 1846
1709 322
1634 2396
217 1178
362 1595
1361 147
2736 16
218 2589
1800 2704
1242 1913
2295 2859
2668 818
1763 2132
465 2860
207 1494
494 805
616 1670
1647 1436
790 828
321 1206
...

output:

298819672

result:

ok 1 number(s): "298819672"

Test #10:

score: 5
Accepted
time: 4ms
memory: 4688kb

input:

2886
1887 1647
1190 1165
2764 2269
1411 2213
706 507
2403 434
1419 1939
2786 963
69 1513
2815 2212
2749 593
1440 1759
359 1220
1873 2835
2021 728
1781 1558
797 2554
1405 1924
2136 1826
2024 1262
65 2682
2640 128
2853 1362
109 1548
1603 897
17 660
1705 2434
1512 1762
2594 2797
1515 279
43 1605
87 967...

output:

881424206

result:

ok 1 number(s): "881424206"

Test #11:

score: 5
Accepted
time: 2ms
memory: 4312kb

input:

97
73 35
15 53
60 45
35 18
23 50
8 25
73 66
29 79
86 16
69 32
90 51
52 41
82 68
16 46
32 46
87 76
13 12
84 28
84 74
15 73
55 23
22 69
39 95
51 91
2 42
37 24
88 70
5 41
16 27
55 39
1 24
74 22
97 38
67 96
48 59
53 2
97 21
14 33
93 2
59 85
44 18
4 65
81 70
20 87
97 91
89 55
68 10
82 26
30 5
2 3
6 9
80 ...

output:

327375684

result:

ok 1 number(s): "327375684"

Test #12:

score: 5
Accepted
time: 2ms
memory: 4372kb

input:

100
73 46
74 32
37 91
52 94
40 33
39 8
6 8
53 41
72 74
41 18
34 42
64 43
85 1
33 67
2 68
50 13
63 29
62 68
62 12
10 82
75 82
12 28
98 13
63 87
44 68
86 76
54 37
9 97
65 9
23 7
22 41
93 15
63 84
59 78
82 97
19 97
49 90
11 93
47 29
43 83
27 15
81 54
54 29
21 61
48 44
28 24
65 72
16 38
88 100
68 70
77 ...

output:

897294509

result:

ok 1 number(s): "897294509"

Test #13:

score: 5
Accepted
time: 2ms
memory: 4392kb

input:

100
66 48
34 14
69 58
15 54
11 74
11 26
85 16
52 19
9 96
14 2
49 83
91 47
38 75
27 84
44 10
55 77
77 23
41 67
19 58
48 22
64 80
63 31
38 17
57 52
32 50
96 70
7 45
43 22
61 12
89 13
94 92
67 88
14 71
1 68
94 78
32 67
27 72
73 44
18 90
61 1
17 2
75 29
7 41
49 28
71 78
57 99
89 82
21 3
46 95
85 35
63 1...

output:

654531193

result:

ok 1 number(s): "654531193"

Test #14:

score: 5
Accepted
time: 2ms
memory: 4556kb

input:

99
99 40
34 26
9 82
51 23
13 3
30 37
61 72
32 63
4 14
19 35
95 79
10 16
72 44
70 17
87 92
24 87
92 66
14 8
47 52
52 50
73 57
50 58
93 33
5 6
42 34
55 64
73 60
18 30
22 52
82 49
30 89
97 76
34 85
44 2
90 80
61 86
62 38
19 21
45 62
80 27
67 61
20 33
98 50
64 60
59 93
11 76
75 29
71 30
63 79
15 53
16 6...

output:

886626024

result:

ok 1 number(s): "886626024"

Test #15:

score: 5
Accepted
time: 6ms
memory: 4588kb

input:

494
487 439
42 258
53 418
97 251
307 18
33 167
174 25
18 258
429 147
47 437
144 73
406 161
420 297
281 364
471 426
151 234
492 44
175 348
241 460
340 141
139 142
494 186
435 343
416 33
251 434
356 78
370 466
317 60
54 230
476 358
426 364
102 189
217 456
8 24
427 303
460 224
20 390
273 182
436 438
32...

output:

580593594

result:

ok 1 number(s): "580593594"

Test #16:

score: 5
Accepted
time: 6ms
memory: 4664kb

input:

478
311 67
163 381
282 172
217 141
319 274
128 363
452 348
259 234
39 251
118 125
336 46
463 462
164 372
91 383
108 164
287 410
284 214
286 257
129 166
220 328
403 194
173 167
36 388
244 416
317 39
300 11
100 162
32 460
127 390
92 185
226 267
136 97
288 409
204 331
470 115
181 38
350 238
456 187
344...

output:

782076576

result:

ok 1 number(s): "782076576"

Test #17:

score: 5
Accepted
time: 5ms
memory: 4704kb

input:

483
357 199
148 479
452 445
400 317
155 219
324 270
425 67
44 270
12 464
73 179
432 230
410 439
17 55
62 446
187 346
449 473
301 353
184 136
180 344
318 381
218 323
225 453
43 302
278 200
164 432
196 6
132 360
101 340
463 404
29 333
6 141
49 340
359 96
380 365
253 244
435 278
256 88
208 142
69 479
4...

output:

335765358

result:

ok 1 number(s): "335765358"

Test #18:

score: 5
Accepted
time: 5ms
memory: 4412kb

input:

498
208 286
418 457
57 37
58 440
326 419
195 208
482 315
103 363
47 164
477 270
38 250
3 362
10 361
271 415
263 29
443 464
78 3
105 260
174 312
335 269
358 322
426 30
219 286
159 79
86 361
345 314
464 294
18 488
162 370
88 183
170 8
248 307
363 200
407 61
337 373
321 378
68 384
368 146
291 468
82 15...

output:

98998708

result:

ok 1 number(s): "98998708"

Test #19:

score: 5
Accepted
time: 283ms
memory: 4932kb

input:

3000
2323 1801
1801 2786
1801 1576
1801 217
2499 394
525 1785
1473 2608
2086 1801
1279 395
2129 2080
422 1844
1113 1473
239 1223
1643 1473
1473 2079
2230 2334
2343 927
1897 1801
1473 14
1473 2815
2949 830
1948 799
935 947
1473 2201
285 89
1801 293
1801 2413
1801 11
1473 1284
2709 265
1801 1518
1732 ...

output:

369871348

result:

ok 1 number(s): "369871348"

Test #20:

score: 5
Accepted
time: 279ms
memory: 4868kb

input:

3000
1314 1680
2794 951
951 863
461 2475
1607 2475
951 593
2887 2475
1461 951
2730 52
1845 951
2366 814
784 2475
669 1150
951 133
2475 2382
2814 2475
951 455
341 1618
2710 2475
2475 1444
1143 2484
951 1527
1386 1887
2475 251
463 2475
2355 147
2099 951
951 299
2475 1814
1015 2475
1182 2812
2612 2147
...

output:

26129954

result:

ok 1 number(s): "26129954"