QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#267607#7869. 建设终末树hos_lyric#55 2070ms531076kbC++1412.3kb2023-11-27 15:13:232024-07-04 03:09:52

Judging History

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

  • [2024-07-04 03:09:52]
  • 评测
  • 测评结果:55
  • 用时:2070ms
  • 内存:531076kb
  • [2023-11-27 15:13:23]
  • 提交

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")


struct Scc {
  int n;
  vector<int> as, bs;
  vector<int> ptr, zu, us;

  int l;
  vector<int> ids;
  int operator[](int u) const { return ids[u]; }

  explicit Scc(int n_) : n(n_), as(), bs(), l(-1) {}
  void ae(int u, int v) {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    as.push_back(u);
    bs.push_back(v);
  }

  void dfs0(int u) {
    if (!ids[u]) {
      ids[u] = -1;
      for (int i = ptr[u]; i < ptr[u + 1]; ++i) dfs0(zu[i]);
      us.push_back(u);
    }
  }
  void dfs1(int u) {
    if (!~ids[u]) {
      ids[u] = l;
      for (int i = ptr[u]; i < ptr[u + 1]; ++i) dfs1(zu[i]);
    }
  }
  void run() {
    const int m = as.size();
    ptr.resize(n + 2);
    zu.resize(m);
    for (int u = 0; u < n + 2; ++u) ptr[u] = 0;
    for (int i = 0; i < m; ++i) ++ptr[as[i] + 2];
    for (int u = 2; u < n + 1; ++u) ptr[u + 1] += ptr[u];
    for (int i = 0; i < m; ++i) zu[ptr[as[i] + 1]++] = bs[i];
    ids.assign(n, 0);
    us.clear();
    for (int u = 0; u < n; ++u) dfs0(u);
    for (int u = 0; u < n + 2; ++u) ptr[u] = 0;
    for (int i = 0; i < m; ++i) ++ptr[bs[i] + 2];
    for (int u = 2; u < n + 1; ++u) ptr[u + 1] += ptr[u];
    for (int i = 0; i < m; ++i) zu[ptr[bs[i] + 1]++] = as[i];
    l = 0;
    for (int j = n; --j >= 0; ) if (!~ids[us[j]]) { dfs1(us[j]); ++l; }
  }

  vector<vector<int>> group() const {
    assert(~l);
    vector<vector<int>> uss(l);
    for (int u = 0; u < n; ++u) uss[ids[u]].push_back(u);
    return uss;
  }
};


struct Hld {
  int n, rt;
  // needs to be tree
  // vertex lists
  // modified in build(rt) (parent removed, heavy child first)
  vector<vector<int>> graph;
  vector<int> sz, par, dep;
  int zeit;
  vector<int> dis, fin, sid;
  // head vertex (minimum depth) in heavy path
  vector<int> head;

  Hld() : n(0), rt(-1), zeit(0) {}
  explicit Hld(int n_) : n(n_), rt(-1), graph(n), zeit(0) {}
  void ae(int u, int v) {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    graph[u].push_back(v);
    graph[v].push_back(u);
  }

  void dfsSz(int u) {
    sz[u] = 1;
    for (const int v : graph[u]) {
      auto it = std::find(graph[v].begin(), graph[v].end(), u);
      if (it != graph[v].end()) graph[v].erase(it);
      par[v] = u;
      dep[v] = dep[u] + 1;
      dfsSz(v);
      sz[u] += sz[v];
    }
  }
  void dfsHld(int u) {
    dis[u] = zeit++;
    const int deg = graph[u].size();
    if (deg > 0) {
      int vm = graph[u][0];
      int jm = 0;
      for (int j = 1; j < deg; ++j) {
        const int v = graph[u][j];
        if (sz[vm] < sz[v]) {
          vm = v;
          jm = j;
        }
      }
      swap(graph[u][0], graph[u][jm]);
      head[vm] = head[u];
      dfsHld(vm);
      for (int j = 1; j < deg; ++j) {
        const int v = graph[u][j];
        head[v] = v;
        dfsHld(v);
      }
    }
    fin[u] = zeit;
  }
  void build(int rt_) {
    assert(0 <= rt_); assert(rt_ < n);
    rt = rt_;
    sz.assign(n, 0);
    par.assign(n, -1);
    dep.assign(n, -1);
    dep[rt] = 0;
    dfsSz(rt);
    zeit = 0;
    dis.assign(n, -1);
    fin.assign(n, -1);
    head.assign(n, -1);
    head[rt] = rt;
    dfsHld(rt);
    assert(zeit == n);
    sid.assign(n, -1);
    for (int u = 0; u < n; ++u) sid[dis[u]] = u;
  }

  friend ostream &operator<<(ostream &os, const Hld &hld) {
    const int maxDep = *max_element(hld.dep.begin(), hld.dep.end());
    vector<string> ss(2 * maxDep + 1);
    int pos = 0, maxPos = 0;
    for (int j = 0; j < hld.n; ++j) {
      const int u = hld.sid[j];
      const int d = hld.dep[u];
      if (hld.head[u] == u) {
        if (j != 0) {
          pos = maxPos + 1;
          ss[2 * d - 1].resize(pos, '-');
          ss[2 * d - 1] += '+';
        }
      } else {
        ss[2 * d - 1].resize(pos, ' ');
        ss[2 * d - 1] += '|';
      }
      ss[2 * d].resize(pos, ' ');
      ss[2 * d] += std::to_string(u);
      if (maxPos < static_cast<int>(ss[2 * d].size())) {
        maxPos = ss[2 * d].size();
      }
    }
    for (int d = 0; d <= 2 * maxDep; ++d) os << ss[d] << '\n';
    return os;
  }

  bool contains(int u, int v) const {
    return (dis[u] <= dis[v] && dis[v] < fin[u]);
  }
  int lca(int u, int v) const {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    for (; head[u] != head[v]; ) (dis[u] > dis[v]) ? (u = par[head[u]]) : (v = par[head[v]]);
    return (dis[u] > dis[v]) ? v : u;
  }
  int jumpUp(int u, int d) const {
    assert(0 <= u); assert(u < n);
    assert(d >= 0);
    if (dep[u] < d) return -1;
    const int tar = dep[u] - d;
    for (u = head[u]; ; u = head[par[u]]) {
      if (dep[u] <= tar) return sid[dis[u] + (tar - dep[u])];
    }
  }
  int jump(int u, int v, int d) const {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    assert(d >= 0);
    const int l = lca(u, v);
    const int du = dep[u] - dep[l], dv = dep[v] - dep[l];
    if (d <= du) {
      return jumpUp(u, d);
    } else if (d <= du + dv) {
      return jumpUp(v, du + dv - d);
    } else {
      return -1;
    }
  }
  // [u, v) or [u, v]
  template <class F> void doPathUp(int u, int v, bool inclusive, F f) const {
    assert(contains(v, u));
    for (; head[u] != head[v]; u = par[head[u]]) f(dis[head[u]], dis[u] + 1);
    if (inclusive) {
      f(dis[v], dis[u] + 1);
    } else {
      if (v != u) f(dis[v] + 1, dis[u] + 1);
    }
  }
  // not path order, include lca(u, v) or not
  template <class F> void doPath(int u, int v, bool inclusive, F f) const {
    const int l = lca(u, v);
    doPathUp(u, l, false, f);
    doPathUp(v, l, inclusive, f);
  }

  // (vs, ps): compressed tree
  // vs: DFS order (sorted by dis)
  // vs[ps[x]]: the parent of vs[x]
  // ids[vs[x]] = x, not set for non-tree vertex
  vector<int> ids;
  pair<vector<int>, vector<int>> compress(vector<int> us) {
    // O(n) first time
    ids.resize(n, -1);
    std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
      return (dis[u] < dis[v]);
    });
    us.erase(std::unique(us.begin(), us.end()), us.end());
    int usLen = us.size();
    assert(usLen >= 1);
    for (int x = 1; x < usLen; ++x) us.push_back(lca(us[x - 1], us[x]));
    std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
      return (dis[u] < dis[v]);
    });
    us.erase(std::unique(us.begin(), us.end()), us.end());
    usLen = us.size();
    for (int x = 0; x < usLen; ++x) ids[us[x]] = x;
    vector<int> ps(usLen, -1);
    for (int x = 1; x < usLen; ++x) ps[x] = ids[lca(us[x - 1], us[x])];
    return make_pair(us, ps);
  }
};

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


int N, M, Q;
vector<int> A, B;
vector<vector<int>> C;
vector<vector<int>> V, S;

int main() {
  for (; ~scanf("%d%d%d", &N, &M, &Q); ) {
    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];
    }
    C.resize(M);
    for (int m = 0; m < M; ++m) {
      int len;
      scanf("%d", &len);
      C[m].resize(len);
      for (int &c : C[m]) {
        scanf("%d", &c);
        --c;
      }
    }
    V.resize(Q);
    S.resize(Q);
    for (int q = 0; q < Q; ++q) {
      int len;
      scanf("%d", &len);
      V[q].resize(len);
      for (int &v : V[q]) {
        scanf("%d", &v);
        --v;
      }
      scanf("%d", &len);
      S[q].resize(len);
      for (int &s : S[q]) {
        scanf("%d", &s);
        --s;
      }
    }
    
    Hld hld(N);
    for (int i = 0; i < N - 1; ++i) {
      hld.ae(A[i], B[i]);
    }
    hld.build(0);
    const auto &par = hld.par;
    const auto &sid = hld.sid;
#ifdef LOCAL
cerr<<string(80,'=')<<endl;
cerr<<hld<<endl;
cerr<<"C = "<<C<<endl;
cerr<<"V = "<<V<<endl;
cerr<<"S = "<<S<<endl;
#endif
    
    
    // item m is in subtree(u)
    auto tru = [&](int m, int u) -> int { return (m * N + u) << 1; };
    auto fal = [&](int m, int u) -> int { return (m * N + u) << 1 | 1; };
    auto prefix = [&](int m, int u) -> int { return (M * N + (m * N + u)) << 1; };
    Scc scc((M * N + M * N) << 1);
    // x ==> y
    auto add = [&](int x, int y) -> void {
      if (x != y) {
        scc.ae(x, y);
        if ((x ^ 1) != y) {
          scc.ae(y ^ 1, x ^ 1);
        }
      }
    };
    
    for (int m = 0; m < M; ++m) {
      vector<int> dp(N, 0);
      for (const int c : C[m]) {
        dp[c] += 1;
      }
      for (int j = N; --j >= 1; ) {
        const int u = sid[j];
        dp[par[u]] += dp[u];
      }
      for (int u = 0; u < N; ++u) {
        if (dp[u] == (int)C[m].size()) {
          add(fal(m, u), tru(m, u));
          continue;
        }
        if (dp[u] == 0) {
          add(tru(m, u), fal(m, u));
          continue;
        }
        add(tru(m, u), tru(m, par[u]));
      }
      for (int u = 0; u < N; ++u) {
        const auto &vs = hld.graph[u];
        /*
        for (int j0 = 0; j0 < (int)vs.size(); ++j0) for (int j1 = j0 + 1; j1 < (int)vs.size(); ++j1) {
          add(tru(m, vs[j0]), fal(m, vs[j1]));
        }
        */
        const int len = vs.size();
        for (int j = 1; j < len; ++j) {
          add(prefix(m, vs[j - 1]), prefix(m, vs[j]));
        }
        for (int j = 0; j < len; ++j) {
          add(tru(m, vs[j]), prefix(m, vs[j]));
          if (j) add(tru(m, vs[j]), prefix(m, vs[j - 1]) ^ 1);
        }
      }
    }
    
    for (int q = 0; q < Q; ++q) {
      /*
      vector<int> dp(N, 0);
      for (const int v : V[q]) {
        dp[v] += 1;
      }
      for (int j = N; --j >= 1; ) {
        const int u = sid[j];
        dp[par[u]] += dp[u];
      }
      for (int u = 0; u < N; ++u) {
        if (dp[u] == (int)V[q].size()) continue;
        if (dp[u] == 0) continue;
        // same side when cut (par[u], u)
        for (const int m0 : S[q]) for (const int m1 : S[q]) {
          add(tru(m0, u), tru(m1, u));
        }
      }
      */
      const auto vsps = hld.compress(V[q]);
      const int len = vsps.first.size();
// cerr<<V[q]<<": "<<vsps<<endl;
      for (int j = 1; j < len; ++j) {
        const int p = vsps.first[vsps.second[j]];
        for (int u = vsps.first[j]; u != p; u = par[u]) {
          // same side when cut (par[u], u)
          for (int k = 0; k < (int)S[q].size(); ++k) {
            add(tru(S[q][k], u), tru(S[q][(k + 1 == (int)S[q].size()) ? 0 : (k + 1)], u));
          }
        }
      }
    }
    
    scc.run();
    bool ok = true;
    for (int x = 0; x < scc.n; x += 2) {
      ok = ok && (scc[x] != scc[x ^ 1]);
    }
    if (ok) {
      vector<int> ans(M, -1);
      for (int m = 0; m < M; ++m) {
// for(int u=0;u<N;++u)cerr<<(scc[fal(m,u)]<scc[tru(m,u)]);cerr<<endl;
        for (int j = N; --j >= 0; ) {
          const int u = sid[j];
          if (scc[fal(m, u)] < scc[tru(m, u)]) {
            ans[m] = u;
            break;
          }
        }
      }
      for (int m = 0; m < M; ++m) {
        if (m) printf(" ");
        printf("%d", ans[m] + 1);
      }
      puts("");
    } else {
      puts("-1");
    }
  }
  return 0;
}

詳細信息

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

1999 1998 27199
1368 233
233 617
233 388
233 1127
1905 233
907 233
233 40
233 1325
233 1940
1739 233
501 233
233 33
735 233
233 283
233 1427
1992 233
233 632
233 685
1188 233
648 233
233 344
233 1321
986 233
848 233
770 233
256 233
164 233
936 233
1206 233
53 233
1054 233
1430 233
1714 233
86 233
11...

output:


result:


Subtask #2:

score: 15
Accepted

Test #8:

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

input:

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

output:

10 10 10 10 2 10 8 2 1 10

result:

ok Accepted.

Test #9:

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

input:

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

output:

7 8 9 1 9 3 8 3 9 2

result:

ok Accepted.

Test #10:

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

input:

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

output:

9 3 10 2 9 10 10 3 3 1

result:

ok Accepted.

Test #11:

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

input:

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

output:

-1

result:

ok Accepted.

Test #12:

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

input:

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

output:

7 2 7 7 7 1 2 7 7 7

result:

ok Accepted.

Test #13:

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

input:

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

output:

1 4 4 4 4 4 4 4 4 4

result:

ok Accepted.

Test #14:

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

input:

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

output:

1 1 10 10 10 5 10 10 10 10

result:

ok Accepted.

Test #15:

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

input:

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

output:

3 4 3 3 3 3 3 3 3 5

result:

ok Accepted.

Test #16:

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

input:

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

output:

-1

result:

ok Accepted.

Test #17:

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

input:

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

output:

1 10 10 10 10 10 1 10 7 10

result:

ok Accepted.

Test #18:

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

input:

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

output:

2 7 1 7 10 1 1 1 7 7

result:

ok Accepted.

Subtask #3:

score: 20
Accepted

Test #19:

score: 20
Accepted
time: 114ms
memory: 68264kb

input:

500 498 5000
60 409
462 125
461 410
42 178
133 372
137 265
358 27
450 294
45 454
76 405
132 118
333 331
365 230
114 218
112 377
49 429
60 299
488 95
85 362
89 33
426 308
427 198
468 481
289 363
195 430
61 21
162 55
12 487
395 85
79 475
391 215
244 351
331 43
452 186
247 271
224 390
206 347
447 165
9...

output:

266 198 83 93 384 77 212 74 363 147 257 74 74 37 243 48 373 446 92 491 500 71 161 409 455 321 7 161 443 390 317 492 469 369 74 309 415 366 239 275 352 391 74 278 261 452 161 74 161 161 341 92 4 78 491 279 441 74 288 485 42 266 441 261 491 213 424 432 492 140 207 337 161 6 279 92 342 352 446 303 431 ...

result:

ok Accepted.

Test #20:

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

input:

500 500 5000
297 429
444 310
304 235
470 8
33 395
174 34
276 320
298 478
149 117
400 211
118 399
448 268
446 484
268 180
465 471
68 443
33 358
256 431
490 452
110 389
304 418
286 219
498 16
416 376
495 173
408 138
473 228
317 199
344 279
31 469
159 16
377 397
492 402
308 107
461 11
332 105
377 77
31...

output:

362 116 499 207 313 403 470 31 468 227 103 31 481 181 415 412 65 87 94 244 60 117 83 60 357 441 105 6 69 38 231 65 44 133 422 283 65 103 423 162 367 489 405 83 357 455 472 65 223 300 354 414 481 48 240 185 325 373 227 481 436 30 181 144 461 464 65 349 281 29 249 202 65 481 349 229 165 110 357 1 381 ...

result:

ok Accepted.

Test #21:

score: 0
Accepted
time: 115ms
memory: 68196kb

input:

499 498 5000
28 246
54 26
13 312
346 225
377 80
274 410
352 446
394 386
204 453
54 355
337 480
313 263
90 395
388 61
193 71
213 265
125 121
65 120
154 216
331 206
475 413
263 332
322 306
75 290
335 222
149 360
89 139
52 10
91 132
202 88
211 106
205 422
19 467
250 156
382 223
161 486
4 8
495 16
64 12...

output:

128 176 407 490 57 128 62 438 354 405 442 225 96 33 421 57 269 136 57 211 369 176 442 438 117 6 110 221 98 405 277 198 11 172 136 6 475 57 314 62 377 166 57 107 305 200 344 57 229 136 193 200 10 369 78 301 6 57 221 200 438 172 96 358 458 21 7 395 254 455 133 405 9 200 298 412 421 200 200 355 266 397...

result:

ok Accepted.

Test #22:

score: 0
Accepted
time: 133ms
memory: 67940kb

input:

499 500 5000
71 225
374 470
413 420
422 368
357 141
479 360
172 237
21 40
16 386
434 274
188 207
249 16
9 259
152 63
488 264
166 467
51 70
90 417
209 411
43 101
102 206
320 29
110 408
182 333
115 394
138 458
29 296
73 241
392 145
235 428
197 114
271 125
131 401
122 377
215 252
186 253
38 309
11 491
...

output:

66 299 375 188 163 22 391 82 378 357 4 497 29 82 188 378 82 82 29 378 220 4 220 363 378 4 390 363 29 163 323 82 391 497 357 463 295 363 82 66 21 497 91 82 497 390 91 497 220 497 375 91 378 22 390 295 118 93 29 284 497 82 22 91 463 375 463 497 22 21 391 93 21 299 29 21 4 22 463 82 391 497 22 29 93 35...

result:

ok Accepted.

Test #23:

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

input:

498 498 5000
181 300
371 226
361 224
82 101
233 476
366 273
212 240
90 169
488 477
22 374
164 369
276 390
350 61
101 165
331 274
72 325
371 190
472 404
250 449
179 451
64 153
447 267
97 24
495 168
139 170
203 407
493 225
413 216
29 490
306 332
257 309
43 279
189 94
294 287
297 319
289 406
221 338
74...

output:

178 489 439 71 71 326 44 448 270 71 274 8 63 145 8 71 96 326 274 178 109 437 491 391 437 326 96 140 63 343 270 437 439 489 274 36 178 491 324 481 448 270 391 8 251 489 437 274 491 97 473 124 8 97 343 491 8 44 473 124 491 63 391 178 489 97 448 343 489 324 448 438 393 439 489 489 489 178 437 391 71 27...

result:

ok Accepted.

Test #24:

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

input:

498 499 5000
49 110
380 351
80 59
60 4
378 224
383 28
95 381
220 227
287 440
251 493
278 388
157 339
489 377
98 308
122 403
267 47
109 207
140 31
461 264
210 481
130 216
31 410
383 9
141 13
343 448
45 324
297 449
371 149
474 214
41 154
185 138
299 34
412 411
492 327
277 229
33 494
237 12
97 420
6 18...

output:

187 412 483 63 412 483 93 483 412 483 483 63 412 483 483 412 483 93 412 93 187 412 187 483 431 93 187 483 63 187 93 483 63 261 63 93 187 63 483 187 93 187 93 63 187 187 187 187 412 483 187 483 187 483 187 483 483 63 187 93 483 412 412 187 483 412 483 187 412 460 483 63 483 187 412 15 93 412 63 63 48...

result:

ok Accepted.

Test #25:

score: 0
Accepted
time: 121ms
memory: 68216kb

input:

500 499 5000
368 181
285 335
445 454
267 331
22 212
294 281
454 121
19 31
57 14
101 152
130 284
329 396
406 500
446 115
337 61
421 68
203 119
352 238
313 450
16 259
167 307
326 255
173 256
77 42
203 270
249 402
153 135
146 450
172 73
185 149
398 15
426 213
407 368
351 124
159 356
371 418
319 156
304...

output:

355 210 309 310 309 210 210 310 355 309 309 19 309 487 487 309 19 355 310 309 310 487 355 487 487 487 310 487 355 487 210 487 210 210 355 355 487 309 487 355 19 355 355 487 210 487 487 310 355 309 210 355 487 310 487 487 487 487 19 355 19 309 309 487 309 19 224 210 210 210 309 355 19 309 210 309 210...

result:

ok Accepted.

Test #26:

score: 0
Accepted
time: 134ms
memory: 73844kb

input:

500 499 5000
350 140
294 337
407 172
180 28
139 287
2 413
498 218
4 449
245 412
45 247
397 482
427 165
202 490
53 323
178 209
247 341
253 485
478 203
34 305
306 173
111 14
188 64
213 9
278 59
347 454
83 448
356 336
148 239
378 272
145 402
457 189
299 209
291 368
96 110
187 270
218 304
358 217
6 455
...

output:

-1

result:

ok Accepted.

Test #27:

score: 0
Accepted
time: 203ms
memory: 72520kb

input:

499 499 5000
75 164
439 163
466 334
370 484
25 201
107 165
250 122
355 17
411 164
169 9
463 497
428 442
93 50
7 326
15 207
479 112
454 391
329 96
127 290
1 2
99 347
39 84
407 405
147 271
57 298
472 129
195 377
296 35
441 440
232 176
388 92
325 198
425 267
23 100
487 433
78 416
193 365
348 352
324 28...

output:

-1

result:

ok Accepted.

Subtask #4:

score: 20
Accepted

Dependency #2:

100%
Accepted

Test #28:

score: 20
Accepted
time: 104ms
memory: 48636kb

input:

499 499 265
20 482
382 88
211 434
122 198
238 180
411 104
462 291
28 215
220 69
192 172
493 52
25 455
162 29
405 278
161 339
316 212
443 257
419 262
411 458
331 93
106 144
422 264
488 248
86 165
62 411
426 236
443 30
140 260
499 37
295 372
315 237
15 67
403 366
467 235
42 262
61 300
312 362
469 202
...

output:

298 488 28 14 17 17 222 222 81 7 488 488 28 81 215 17 81 28 74 488 369 222 488 17 369 222 250 369 81 250 479 479 250 442 57 488 81 298 17 267 496 17 496 298 5 496 442 222 488 57 81 479 74 488 28 267 14 17 28 17 298 51 479 298 2 28 28 17 28 222 74 51 1 222 488 28 479 488 488 222 28 298 42 28 51 488 4...

result:

ok Accepted.

Test #29:

score: 0
Accepted
time: 90ms
memory: 47800kb

input:

500 498 275
323 261
41 144
117 22
223 61
412 79
403 191
166 56
401 274
42 204
439 277
439 175
475 382
320 164
179 397
143 302
68 276
11 9
252 25
421 419
109 353
451 165
63 461
28 241
7 91
302 420
60 284
283 113
418 176
443 177
64 412
144 497
493 14
483 209
287 375
287 100
298 376
298 193
188 321
288...

output:

156 491 491 11 339 20 11 420 144 157 420 208 193 76 157 157 160 208 76 339 208 76 11 229 193 157 491 191 4 17 191 156 491 420 157 157 420 11 156 144 420 156 76 160 160 1 76 193 420 420 302 156 11 420 156 193 193 156 11 420 41 420 11 156 11 237 156 160 11 156 156 156 11 420 11 11 157 420 491 237 160 ...

result:

ok Accepted.

Test #30:

score: 0
Accepted
time: 107ms
memory: 51176kb

input:

500 499 215
233 327
276 433
188 7
393 452
431 389
55 485
238 103
411 344
273 193
351 211
248 161
489 149
13 427
336 210
487 199
76 324
452 477
290 134
108 418
378 300
371 218
499 85
418 450
480 353
248 451
89 3
249 248
283 203
294 443
102 360
412 20
234 177
479 171
357 165
490 340
133 110
52 106
374...

output:

-1

result:

ok Accepted.

Test #31:

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

input:

499 499 260
157 101
80 132
333 13
206 419
136 233
322 168
48 362
32 485
426 214
493 349
179 181
245 284
332 366
234 63
407 254
429 337
32 217
469 130
18 129
147 42
223 473
9 310
330 6
242 483
233 228
154 498
31 351
171 377
455 328
497 301
343 244
355 144
386 489
437 247
307 493
134 316
185 256
199 2...

output:

-1

result:

ok Accepted.

Test #32:

score: 0
Accepted
time: 73ms
memory: 41896kb

input:

498 498 1951
289 275
304 352
50 441
95 466
432 162
324 216
367 399
413 154
163 345
290 127
450 195
437 41
326 421
236 299
248 449
60 233
31 183
278 228
184 444
384 448
135 462
39 486
215 123
136 120
12 200
182 416
475 292
180 40
381 334
324 310
113 429
177 398
393 447
67 350
112 46
133 23
205 218
33...

output:

136 381 233 255 416 173 137 39 416 137 100 136 44 416 136 151 262 173 185 173 402 44 151 137 311 137 154 198 151 136 416 68 44 185 11 198 327 475 416 416 334 136 402 262 255 100 475 44 100 475 151 107 39 381 68 68 173 173 173 173 262 11 416 39 136 173 398 446 255 475 260 100 416 137 152 262 311 352 ...

result:

ok Accepted.

Test #33:

score: 0
Accepted
time: 64ms
memory: 40084kb

input:

498 499 2728
88 127
472 81
109 272
124 323
459 371
316 200
321 29
306 46
458 36
95 143
148 205
207 308
252 440
39 74
131 100
237 277
298 341
16 473
349 492
83 461
98 382
17 13
295 198
65 83
165 426
127 412
413 327
237 268
183 211
207 255
221 41
128 433
100 217
40 9
151 64
426 360
189 322
209 26
290 ...

output:

-1

result:

ok Accepted.

Test #34:

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

input:

498 500 285
165 321
87 3
184 139
75 133
257 406
187 14
396 96
323 248
63 165
69 170
388 281
117 164
114 329
103 355
138 177
169 498
182 462
368 424
323 474
322 317
303 416
57 259
498 425
135 216
137 38
30 437
151 205
147 19
459 12
174 280
400 348
248 435
362 213
180 54
363 77
54 157
65 303
447 366
6...

output:

189 400 362 57 362 323 47 425 425 189 323 132 47 189 47 189 57 323 47 57 189 323 362 165 47 189 57 132 165 362 425 57 362 47 323 400 362 165 47 132 400 132 323 362 47 27 47 47 132 323 165 425 400 400 27 323 47 132 323 323 57 189 57 362 323 362 57 47 47 455 27 400 27 400 323 400 400 27 165 455 47 425...

result:

ok Accepted.

Test #35:

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

input:

499 500 371
4 44
100 459
299 107
478 284
421 197
56 90
381 198
305 237
137 260
451 188
381 435
230 458
354 76
100 157
431 198
133 394
181 340
221 198
180 15
269 386
287 330
378 152
198 129
274 318
139 38
150 385
11 352
114 428
408 154
248 44
206 76
264 56
35 222
457 194
196 272
494 443
96 453
439 43...

output:

222 294 157 76 294 76 294 222 76 44 76 294 157 381 294 381 428 294 76 76 381 222 157 381 157 381 294 428 222 381 381 157 294 44 76 76 157 76 76 428 157 428 294 44 294 157 157 76 381 157 428 157 157 157 76 157 44 428 381 157 428 44 428 76 157 381 157 157 157 381 381 76 76 294 44 76 381 157 381 428 38...

result:

ok Accepted.

Test #36:

score: 0
Accepted
time: 97ms
memory: 49032kb

input:

498 500 355
367 393
291 435
471 306
44 77
23 36
411 421
59 308
419 155
179 222
58 44
66 4
420 442
228 398
435 339
133 296
184 382
335 175
346 398
316 237
24 57
208 281
332 389
195 320
60 425
136 205
9 365
187 177
493 108
468 445
430 494
241 321
486 304
478 127
18 223
182 261
279 377
233 210
212 193
...

output:

-1

result:

ok Accepted.

Test #37:

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

input:

500 498 215
80 358
454 116
72 463
139 277
370 436
202 220
16 188
1 213
38 59
494 217
497 424
426 135
35 302
419 26
326 499
209 10
311 315
451 285
54 60
161 103
168 413
393 104
234 308
434 39
442 49
306 374
311 158
342 287
74 14
199 102
285 51
379 459
411 125
101 210
84 321
369 111
45 334
65 471
143 ...

output:

466 98 75 199 1 122 22 240 8 39 247 1 1 459 177 274 1 447 1 400 91 98 283 274 356 122 91 447 1 175 41 396 285 215 24 60 400 447 379 15 392 5 177 24 199 285 407 15 54 201 287 481 91 8 287 4 8 87 175 278 123 481 1 397 458 215 177 7 287 24 392 240 201 199 24 7 27 15 400 24 458 347 91 59 3 129 15 98 28 ...

result:

ok Accepted.

Test #38:

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

input:

499 498 307
333 446
460 222
39 378
485 52
81 34
75 195
334 424
457 84
460 367
255 166
223 160
310 85
437 87
61 238
108 430
264 487
122 6
319 428
119 154
258 304
133 36
276 326
235 383
327 146
375 340
206 98
157 414
241 47
63 479
307 81
308 335
91 390
121 108
463 492
487 146
361 371
9 311
199 265
297...

output:

12 442 224 224 336 224 12 79 378 1 442 336 432 1 487 1 442 224 79 126 79 39 79 12 336 442 491 487 435 251 487 487 435 79 34 1 224 435 224 224 12 224 435 442 224 432 378 12 1 1 336 12 378 224 336 1 435 39 39 12 224 491 442 487 224 1 79 224 435 1 6 79 12 224 224 378 487 1 491 34 224 79 378 1 487 12 43...

result:

ok Accepted.

Test #39:

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

input:

498 499 314
282 244
343 470
265 268
88 151
423 412
198 242
421 306
203 225
297 471
63 170
290 497
83 91
132 248
11 395
127 81
387 98
422 222
108 122
29 375
419 297
144 324
151 58
96 345
330 475
177 68
144 28
35 448
394 371
328 124
141 279
231 67
208 340
10 403
298 77
170 127
274 378
305 439
81 442
3...

output:

406 144 406 144 144 144 144 144 144 406 146 406 146 144 144 144 144 144 144 144 155 144 146 144 144 144 406 144 144 144 144 406 144 144 144 144 144 144 144 144 144 406 146 144 144 144 155 16 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 406 155 144 144 144 155 144 406 1...

result:

ok Accepted.

Test #40:

score: 0
Accepted
time: 123ms
memory: 68412kb

input:

499 500 5000
262 245
206 378
294 422
331 197
13 210
57 31
239 117
278 155
209 272
182 479
200 209
178 150
371 388
286 42
104 405
356 494
171 235
362 305
361 269
34 20
256 137
233 425
346 311
170 69
76 319
168 110
366 162
305 265
199 194
107 182
59 157
48 243
153 435
469 22
226 54
360 187
72 363
293 ...

output:

475 206 96 249 384 7 358 150 192 287 357 343 494 498 308 249 435 435 5 40 466 182 292 486 262 182 455 471 81 2 81 7 497 82 176 75 486 220 192 227 365 342 350 463 428 51 104 96 260 494 102 202 230 249 403 343 96 323 192 270 475 388 479 217 205 180 287 455 96 412 407 233 131 343 453 90 345 136 114 475...

result:

ok Accepted.

Test #41:

score: 0
Accepted
time: 135ms
memory: 68572kb

input:

498 500 5000
306 1
215 389
341 416
374 34
262 125
476 288
444 90
342 85
215 31
472 463
2 111
325 349
59 275
435 49
448 82
497 167
233 428
407 232
155 109
365 49
322 318
381 10
84 226
422 345
388 168
206 304
301 282
275 47
38 489
210 442
332 118
339 125
393 67
210 421
270 388
380 354
358 352
310 228
...

output:

243 36 34 465 414 21 359 206 355 379 438 434 44 205 482 88 243 96 372 285 348 93 240 167 498 469 131 457 348 85 298 400 175 394 93 58 449 243 149 4 193 374 372 221 205 127 416 410 70 416 31 187 175 143 44 348 364 113 355 439 262 8 31 242 379 283 446 387 94 187 285 457 245 179 263 387 217 127 235 368...

result:

ok Accepted.

Test #42:

score: 0
Accepted
time: 144ms
memory: 73356kb

input:

499 498 5000
395 382
498 86
410 99
157 411
263 304
133 323
163 150
111 220
38 124
305 157
398 491
269 82
9 376
91 239
285 185
370 362
121 456
414 63
306 140
454 183
206 60
417 483
34 482
138 412
358 173
75 346
477 324
429 59
10 486
202 412
426 246
360 267
200 439
394 363
77 348
320 187
442 428
120 5...

output:

-1

result:

ok Accepted.

Test #43:

score: 0
Accepted
time: 127ms
memory: 67912kb

input:

499 499 5000
56 232
281 262
375 216
390 313
244 105
298 227
349 160
115 400
455 98
147 463
25 371
97 131
255 345
187 342
93 207
207 432
330 216
301 346
415 377
166 265
399 495
94 276
354 139
74 50
230 385
42 480
276 457
419 239
264 97
413 157
436 401
154 203
284 425
414 389
358 93
60 308
285 259
144...

output:

147 232 181 67 159 245 52 245 168 194 159 481 17 371 293 91 336 324 207 15 422 481 294 427 171 171 112 422 293 207 161 159 80 43 168 161 324 206 110 293 52 481 293 283 343 303 468 213 348 147 294 348 336 15 354 112 236 277 236 17 293 4 226 168 17 194 17 348 213 422 481 28 226 381 293 422 213 371 371...

result:

ok Accepted.

Test #44:

score: 0
Accepted
time: 133ms
memory: 67988kb

input:

498 498 5000
466 442
188 316
306 215
336 277
11 225
2 23
426 316
396 299
463 201
280 428
288 440
104 398
238 363
341 6
289 106
142 49
192 481
4 195
323 278
185 213
461 475
465 317
324 465
68 187
434 491
222 268
141 334
72 108
61 360
321 471
498 18
166 206
396 377
96 127
5 91
213 456
29 286
191 224
2...

output:

356 226 341 237 474 351 457 474 435 482 31 414 457 377 71 127 401 482 37 91 310 373 137 474 236 91 482 44 416 265 329 101 359 265 184 405 356 351 138 341 14 329 416 101 127 138 373 35 414 156 184 346 416 341 150 70 150 384 416 70 46 265 46 137 236 20 226 377 474 91 137 384 341 439 482 346 482 46 346...

result:

ok Accepted.

Test #45:

score: 0
Accepted
time: 84ms
memory: 43448kb

input:

498 500 367
378 138
146 248
403 496
200 459
400 75
23 277
418 16
101 24
277 362
384 408
320 208
441 46
361 25
85 303
278 288
337 425
24 114
56 344
346 124
128 250
75 9
193 130
114 360
273 250
68 268
310 145
468 287
283 469
225 319
24 400
212 378
135 354
280 311
1 90
208 357
280 56
403 321
411 455
47...

output:

453 403 400 75 403 400 8 24 400 307 75 357 8 250 24 24 330 453 10 400 307 250 8 330 453 24 8 24 24 24 75 250 453 400 8 491 24 453 24 24 400 403 24 24 400 307 24 491 8 51 51 400 1 24 51 24 453 453 400 400 24 453 400 403 24 8 400 400 400 75 307 24 75 400 51 400 75 250 250 24 330 250 24 24 400 400 24 3...

result:

ok Accepted.

Test #46:

score: 0
Accepted
time: 96ms
memory: 48180kb

input:

498 498 294
286 177
26 389
64 73
369 155
345 299
409 106
94 9
286 191
199 354
43 307
107 441
258 222
264 129
456 23
462 275
344 156
193 445
401 360
215 267
33 442
209 465
170 1
257 189
418 15
324 377
175 120
486 498
303 353
30 172
104 43
344 76
126 325
264 455
445 310
47 12
420 381
394 331
391 233
1...

output:

416 238 471 28 179 365 471 28 365 238 238 28 498 371 416 371 416 28 76 471 177 177 28 286 416 179 471 365 76 238 371 179 76 177 76 371 365 365 238 76 76 238 76 177 371 471 286 371 471 383 179 76 177 177 371 28 371 498 498 286 286 498 416 498 471 177 179 177 177 286 498 286 498 416 416 383 28 365 286...

result:

ok Accepted.

Test #47:

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

input:

498 500 214
246 323
132 465
29 71
436 107
95 214
163 281
487 35
388 133
469 148
250 240
486 135
45 144
311 160
461 127
372 283
254 127
252 389
276 441
94 194
115 98
209 127
411 242
99 50
180 47
124 107
483 44
175 272
229 159
176 41
9 206
477 397
302 108
11 318
362 391
356 363
417 391
274 65
71 309
1...

output:

146 213 213 147 146 146 146 394 147 147 146 276 147 147 276 394 146 394 213 213 146 276 213 213 146 147 146 394 213 394 276 276 147 276 394 276 146 147 276 276 394 146 213 213 147 276 146 213 146 394 146 394 146 276 213 146 146 394 147 394 146 213 146 394 394 146 276 213 213 147 394 146 147 276 146 ...

result:

ok Accepted.

Subtask #5:

score: 0
Time Limit Exceeded

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #48:

score: 25
Accepted
time: 1889ms
memory: 517988kb

input:

1999 1999 16990
734 609
971 297
1864 1528
1995 858
1223 411
1800 580
451 1384
800 866
1709 422
740 1381
1402 431
614 526
249 531
406 228
1589 456
1357 1731
852 869
557 1681
1072 632
1695 358
1686 186
1706 313
189 1115
907 1051
1645 1854
1794 1639
1857 1859
496 660
1784 578
311 100
1430 765
330 1319
...

output:

1040 531 200 971 1592 54 901 869 1497 901 971 1196 919 824 311 311 919 1534 1759 531 311 1645 311 200 325 54 1196 869 1194 919 971 869 1196 901 1645 1668 1592 1990 1845 1695 1845 1527 1645 1527 639 54 325 1534 531 122 1196 1497 531 639 1534 54 311 1645 1194 1534 1527 1527 1534 531 824 325 971 1845 1...

result:

ok Accepted.

Test #49:

score: 0
Accepted
time: 2070ms
memory: 531076kb

input:

2000 1998 12882
650 855
532 1114
1227 1437
104 109
599 1148
1400 1487
993 78
1127 1447
1961 1896
1683 170
403 327
1883 1974
1392 1111
1803 571
738 717
1088 1311
411 654
1268 444
919 859
741 954
893 1815
967 1079
1070 1257
1368 643
825 199
7 799
1752 377
1560 1870
1693 748
1834 707
277 411
1175 598
1...

output:

633 633 967 1946 967 1946 1590 967 1988 967 13 292 1114 1946 1020 1020 13 1593 1174 1824 967 506 1632 967 506 573 1824 1174 1632 1632 1174 220 1946 1824 1632 1824 1824 506 1824 1038 1447 1447 13 967 1824 119 967 633 1114 967 633 893 13 1988 13 506 1632 119 1020 1593 1227 1114 893 1824 1174 1020 633 ...

result:

ok Accepted.

Test #50:

score: -25
Time Limit Exceeded

input:

1999 1998 2748
1888 854
1797 419
1733 1121
1431 1009
622 1970
1348 1837
55 478
607 1747
1982 1626
1959 1099
1837 130
605 333
1805 1369
1202 35
1503 986
875 837
693 332
238 1200
41 222
314 925
5 194
1049 238
1493 1290
1206 374
1642 1107
363 1963
49 199
1440 687
75 1130
1131 985
1405 1814
219 953
1134...

output:


result:


Subtask #6:

score: 0
Skipped

Dependency #1:

0%