QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#715400#7330. Territory Gamehos_lyricAC ✓217ms49740kbC++1411.0kb2024-11-06 11:49:482024-11-06 11:49:49

Judging History

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

  • [2024-11-06 11:49:49]
  • 评测
  • 测评结果:AC
  • 用时:217ms
  • 内存:49740kb
  • [2024-11-06 11:49:48]
  • 提交

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 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);
  }
};

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


// (without edge property)
// sub[u]: inside subtree at u, rooted at u
// bus[u]: outside subtree at u, rooted at par[u]
// tot[u]: rooted at u
// T: monoid representing information of a subtree.
//   T::init()  should assign the identity.
//   T::pull(const T &l, const T &r)  should assign the product.
//   T::up(int u)  should attach vertex u to the product of the subtrees.
template <class T> struct ForestDP {
  int n;
  vector<vector<int>> graph;
  vector<int> par;
  vector<T> sub, bus, tot;

  ForestDP() : n(0) {}
  explicit ForestDP(int n_) : n(n_), graph(n_) {}
  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 run() {
    par.assign(n, -2);
    sub.resize(n);
    bus.resize(n);
    tot.resize(n);
    for (int u = 0; u < n; ++u) if (par[u] == -2) {
      dfs0(u, -1);
      dfs1(u, -1);
    }
  }
  void dfs0(int u, int p) {
    par[u] = p;
    const int deg = graph[u].size();
    int w = -1;
    for (int j = deg; --j >= 0; ) {
      const int v = graph[u][j];
      if (p != v) {
        dfs0(v, u);
        if (~w) {
          bus[v].pull(sub[v], bus[w]);
        } else {
          bus[v] = sub[v];
        }
        w = v;
      }
    }
    if (~w) {
      sub[u] = bus[w];
    } else {
      sub[u].init();
    }
    sub[u].up(u);
  }
  void dfs1(int u, int p) {
    const int deg = graph[u].size();
    int v = -1;
    for (int j = 0; j < deg; ++j) {
      const int w = graph[u][j];
      if (p != w) {
        if (~v) {
          bus[v].pull(tot[v], bus[w]);
          bus[v].up(u);
          tot[w].pull(tot[v], sub[v]);
          dfs1(v, u);
        } else {
          if (~p) {
            tot[w] = bus[u];
          } else {
            tot[w].init();
          }
        }
        v = w;
      }
    }
    if (~v) {
      bus[v] = tot[v];
      bus[v].up(u);
      tot[u].pull(tot[v], sub[v]);
      dfs1(v, u);
    } else {
      if (~p) {
        tot[u] = bus[u];
      } else {
        tot[u].init();
      }
    }
    tot[u].up(u);
  }
};


int N, Q;
vector<int> U, V;

Hld hld;
int dist(int u, int v) {
  return hld.dep[u] + hld.dep[v] - 2 * hld.dep[hld.lca(u, v)];
}

struct Data {
  int d;
  int x, y;
  Data() : d(-1), x(-1), y(-1) {}
  void init() {
    d = -1;
    x = y = -1;
  }
  void pull(const Data &a, const Data &b) {
    if (a.d < 0) { *this = b; return; }
    if (b.d < 0) { *this = a; return; }
    const int us[4] = {a.x, a.y, b.x, b.y};
    d = -1;
    x = y = -1;
    for (int i = 0; i < 4; ++i) for (int j = i + 1; j < 4; ++j) {
      if (chmax(d, dist(us[i], us[j]))) {
        x = us[i];
        y = us[j];
      }
    }
  }
  void up(int u) {
    if (!~d) {
      d = 0;
      x = y = u;
      return;
    }
    const int us[3] = {u, x, y};
    d = -1;
    x = y = -1;
    for (int i = 0; i < 3; ++i) for (int j = i + 1; j < 3; ++j) {
      if (chmax(d, dist(us[i], us[j]))) {
        x = us[i];
        y = us[j];
      }
    }
  }
};
ForestDP<Data> F;

// can A move ka times within {u | dist[b][u] > kb} ?
bool canEscape(int a, int b, int ka, int kb) {
  if (dist(a, b) <= kb) return false;
  // diameter below p-u
  const int p = hld.jump(b, a, kb);
  const int u = hld.jump(b, a, kb + 1);
  const Data &f = (p == hld.par[u]) ? F.sub[u] : F.bus[p];
  for (const int v : {f.x, f.y}) {
    if (dist(a, v) >= ka) return true;
  }
  return false;
}

int main() {
  for (; ~scanf("%d%d", &N, &Q); ) {
    U.resize(N - 1);
    V.resize(N - 1);
    for (int i = 0; i < N - 1; ++i) {
      scanf("%d%d", &U[i], &V[i]);
      --U[i];
      --V[i];
    }
    
    hld = Hld(N);
    F = ForestDP<Data>(N);
    for (int i = 0; i < N - 1; ++i) {
      hld.ae(U[i], V[i]);
      F.ae(U[i], V[i]);
    }
    hld.build(0);
    F.run();
// cerr<<"sub = ";for(int u=0;u<N;++u)cerr<<F.sub[u].d<<" ";cerr<<endl;
// cerr<<"bus = ";for(int u=0;u<N;++u)cerr<<F.bus[u].d<<" ";cerr<<endl;
    
    for (; Q--; ) {
      int A, B, K;
      scanf("%d%d%d", &A, &B, &K);
      --A;
      --B;
      
      int ans;
      if ((hld.dep[A] + hld.dep[B]) % 2 != 0) {
        // A: oikakeru, B: nigeru
        if (K % 2 == 0) {
          ans = 0;
        } else {
          ans = canEscape(B, A, K/2, (K+1)/2) ? 1 : 2;
        }
      } else {
        // A: nigeru, B: oikakeru
        if (K % 2 != 0) {
          ans = 1;
        } else {
          ans = canEscape(A, B, (K+1)/2, K/2) ? 0 : -1;
        }
      }
      printf("%d\n", ans);
    }
  }
  return 0;
}

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

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3908kb

input:

4 3
1 2
2 3
3 4
1 4 1
1 4 2
1 4 3

output:

1
0
2

result:

ok 3 number(s): "1 0 2"

Test #2:

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

input:

2 8
1 2
1 2 1
1 2 2
1 2 3
1 2 4
2 1 1
2 1 2
2 1 3
2 1 4

output:

2
0
2
0
2
0
2
0

result:

ok 8 numbers

Test #3:

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

input:

3 36
1 3
1 2
1 2 1
1 2 2
1 2 3
1 2 4
1 2 5
1 2 6
1 3 1
1 3 2
1 3 3
1 3 4
1 3 5
1 3 6
2 1 1
2 1 2
2 1 3
2 1 4
2 1 5
2 1 6
2 3 1
2 3 2
2 3 3
2 3 4
2 3 5
2 3 6
3 1 1
3 1 2
3 1 3
3 1 4
3 1 5
3 1 6
3 2 1
3 2 2
3 2 3
3 2 4
3 2 5
3 2 6

output:

2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
1
-1
1
-1
1
-1
2
0
2
0
2
0
1
-1
1
-1
1
-1

result:

ok 36 numbers

Test #4:

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

input:

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

output:

1
-1
1
-1
1
-1
1
-1
2
0
2
0
2
0
2
0
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
2
0
2
0
2
0
2
0
1
-1
1
-1
1
-1
1
-1
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
1
0
1
-1
1
-1
1
-1
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
1
0
2
0
2
0
2
0
1...

result:

ok 192 numbers

Test #5:

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

input:

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

output:

1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
2
0
2
0
2
0
2
0
2
0
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
2
0
2
0
2
0
2
0
2
0
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
2
0
2
0
2
0
2
0
2
0
1
-1
1
-1
1
-1
1
-1
1
-1
2
0
2
0
2
0
2
0...

result:

ok 600 numbers

Test #6:

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

input:

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

output:

2
0
2
0
2
0
2
0
2
0
2
0
1
0
1
0
2
0
2
0
2
0
2
0
1
0
1
0
2
0
2
0
2
0
2
0
1
0
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
2
0
2
0
2
0
2
0
2
0
2
0
1
0
1
-1
1
-1
1
-1
1
-1
1
-1
1
0
1
-1
1
-1
1
-1
1
-1
1
-1
1
0
1
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
1
0
2
0
2
0
2
0
2
0
2
0
1
0
1
-1
1
-1
1...

result:

ok 2520 numbers

Test #7:

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

input:

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

output:

1
0
1
0
2
0
2
0
2
0
2
0
2
0
1
0
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
2
0
2
0
2
0
2
0
2
0
2
0
2
0
1
0
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
2
0
2
0
2
0
2
0
2
0
2
0
2
0
1
0
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
0
1
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
1
0
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
2
0
2
0
2
0
2
0
2
0
2
0
...

result:

ok 6468 numbers

Test #8:

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

input:

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

output:

1
0
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
1
0
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
0
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
0
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
0
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
2...

result:

ok 25984 numbers

Test #9:

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

input:

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

output:

1
0
1
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
1
0
1
0
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
0
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
1
0
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
1
0
1
0
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
2
0
2
0
2
0
2
0
2
...

result:

ok 60912 numbers

Test #10:

score: 0
Accepted
time: 147ms
memory: 4936kb

input:

5000 5000
2064 4325
667 740
3177 394
2334 1488
2691 4373
401 3052
2406 2326
2532 3838
542 135
162 1340
3644 1935
2376 1026
3322 1573
3156 2500
4625 1315
59 952
2168 2756
263 607
4023 571
4630 197
1915 4527
2629 3365
1371 2517
1592 1134
1716 112
3822 986
4147 3298
3337 4593
4739 416
2721 4801
2662 45...

output:

1
0
0
2
0
1
1
1
-1
1
0
-1
2
1
2
1
-1
2
1
-1
-1
0
-1
1
-1
2
-1
-1
-1
2
1
-1
0
2
-1
-1
2
1
-1
-1
0
1
-1
0
1
1
1
0
2
2
2
1
1
-1
0
-1
-1
0
2
0
-1
1
2
0
1
2
2
1
0
1
2
1
1
1
-1
1
2
1
0
1
1
2
1
-1
1
-1
0
1
-1
0
2
1
-1
2
2
-1
0
-1
2
-1
0
2
2
-1
2
2
-1
0
1
2
0
0
1
-1
-1
1
1
0
0
-1
2
-1
-1
2
2
2
0
0
2
-1
2
-1...

result:

ok 200000 numbers

Test #11:

score: 0
Accepted
time: 130ms
memory: 5172kb

input:

5000 5000
4455 4458
1192 1180
4739 4748
241 258
3516 3526
2659 2660
3096 3101
4633 4624
4686 4677
4203 4195
2754 2758
1935 1936
2118 2122
2074 2072
4261 4257
2274 2270
2004 2017
3474 3479
4384 4381
610 608
3125 3132
1869 1862
4345 4349
2236 2233
2794 2802
4290 4291
338 337
4893 4897
817 827
1582 161...

output:

-1
-1
0
1
1
1
2
2
0
0
1
1
2
-1
-1
1
0
2
2
-1
-1
0
-1
1
1
2
-1
-1
2
-1
1
0
0
1
0
1
-1
0
-1
0
-1
-1
2
1
0
-1
2
2
0
0
-1
-1
2
-1
2
2
0
0
2
1
2
2
-1
2
0
1
-1
1
0
-1
1
1
-1
2
-1
1
2
1
-1
2
1
0
-1
1
1
0
-1
1
-1
1
1
-1
2
0
2
-1
0
1
0
2
-1
2
1
2
1
-1
1
1
0
0
2
1
-1
2
1
1
1
1
-1
1
0
2
-1
-1
0
0
2
2
2
-1
-1
2...

result:

ok 200000 numbers

Test #12:

score: 0
Accepted
time: 217ms
memory: 40180kb

input:

200000 200000
92730 181199
38837 182835
71312 108585
121481 98424
183932 119127
120539 155369
2127 151235
104887 121805
82050 2595
119129 2759
89663 129962
115544 198800
50651 114956
12187 129275
64082 120776
140999 14404
147807 70230
181718 86055
34952 4311
140250 2200
197157 191802
51357 123986
10...

output:

-1
2
-1
-1
0
1
1
-1
0
2
1
1
1
0
2
2
2
2
1
2
1
-1
2
1
0
1
0
2
-1
1
-1
-1
0
1
-1
1
0
2
2
1
0
2
2
1
-1
0
2
0
0
0
1
1
1
-1
1
0
-1
0
1
2
2
2
-1
2
2
0
1
1
2
-1
2
1
1
1
0
1
-1
2
0
0
0
-1
0
2
-1
-1
-1
2
2
0
-1
-1
2
2
1
2
-1
-1
0
1
0
0
0
2
-1
-1
0
1
-1
0
1
0
0
1
0
-1
1
2
2
2
-1
2
0
1
-1
-1
1
1
0
-1
0
2
-1
-1...

result:

ok 200000 numbers

Test #13:

score: 0
Accepted
time: 217ms
memory: 40128kb

input:

200000 200000
186204 169159
89116 86263
40883 48037
98340 103172
171991 172107
182256 185416
78988 79480
115828 116943
198265 196946
95775 94930
111689 103330
130493 133063
1472 1816
177860 182285
101084 100197
21242 24282
115855 119323
81061 79093
53111 43245
93597 80079
73467 67956
188540 195931
1...

output:

2
-1
1
0
-1
1
1
0
1
0
-1
0
1
-1
-1
0
0
0
1
2
2
1
2
2
-1
2
1
2
-1
2
1
-1
2
2
2
0
1
1
-1
2
-1
0
0
1
-1
0
-1
0
-1
0
2
-1
0
0
0
2
0
1
1
1
1
-1
1
1
-1
-1
1
2
-1
-1
2
1
-1
2
2
0
2
-1
0
0
1
1
2
-1
-1
2
2
1
0
1
1
2
1
2
2
2
0
2
2
-1
2
1
-1
-1
0
-1
2
1
-1
-1
0
-1
1
2
1
0
1
1
-1
0
0
2
0
0
0
1
-1
2
0
2
1
-1
2
2...

result:

ok 200000 numbers

Test #14:

score: 0
Accepted
time: 188ms
memory: 40164kb

input:

200000 200000
32111 32145
22582 22497
169745 169556
184886 183841
173772 173435
97857 98150
80637 81340
54274 54876
132013 132771
864 72
185645 185595
41190 41165
128186 128199
106132 106829
97304 97342
136071 136088
196699 196533
118059 117861
26758 27069
142601 142234
198168 198456
175480 175629
1...

output:

2
1
-1
0
2
2
2
1
1
2
2
1
-1
-1
-1
1
1
1
0
0
0
2
0
-1
-1
2
1
0
1
2
0
0
-1
-1
-1
2
2
2
1
1
1
0
1
1
2
1
-1
0
0
1
2
2
0
-1
-1
2
2
0
-1
0
1
-1
-1
0
-1
-1
2
1
0
2
1
-1
-1
0
0
-1
2
2
2
1
-1
2
-1
0
2
-1
1
0
-1
2
1
0
1
0
1
1
0
2
2
0
1
0
1
-1
2
0
-1
1
0
-1
0
-1
1
1
0
2
2
-1
2
2
0
2
0
1
-1
0
1
2
2
1
0
-1
0
-1
...

result:

ok 200000 numbers

Test #15:

score: 0
Accepted
time: 166ms
memory: 41072kb

input:

200000 200000
185586 185596
13361 13332
6195 6242
135359 135364
132597 132592
149835 149832
130613 130617
119157 119174
95116 95105
29289 29308
63123 63124
184901 184972
96469 96489
123113 123121
197521 197630
88723 88918
50261 50249
17243 17167
185636 185622
21850 21861
165058 165014
186796 186745
...

output:

-1
1
-1
0
0
0
2
-1
2
0
2
-1
2
1
-1
1
-1
2
1
0
0
-1
-1
0
1
-1
1
2
-1
-1
-1
-1
0
0
0
0
2
0
2
1
0
1
2
0
1
2
0
0
2
0
1
0
2
0
2
-1
0
1
-1
0
1
1
2
1
2
2
0
0
1
1
2
1
0
0
0
0
1
0
0
1
-1
-1
2
0
0
1
1
0
-1
1
-1
-1
2
1
0
2
0
-1
-1
0
2
2
-1
-1
1
-1
0
1
-1
0
-1
1
-1
2
0
1
1
1
0
1
1
0
1
2
2
1
1
-1
-1
-1
1
1
1
-1
...

result:

ok 200000 numbers

Test #16:

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

input:

200000 200000
92192 92196
167616 167617
58244 58245
112443 112441
45046 45045
64045 64046
38826 38827
89663 89662
57217 57215
189516 189518
19828 19827
23699 23700
127710 127707
91194 91195
109553 109555
115068 115069
74104 74105
131070 131071
150412 150411
64557 64560
96402 96400
137438 137437
3960...

output:

1
-1
0
0
-1
1
1
0
0
0
2
-1
0
-1
1
1
2
1
0
2
1
2
-1
2
0
1
2
0
1
0
2
1
2
2
0
0
2
0
2
1
0
0
2
-1
1
0
0
0
2
0
-1
-1
1
0
1
0
0
1
0
1
0
-1
1
2
2
-1
2
2
-1
1
2
1
0
0
0
-1
0
1
0
0
1
2
0
2
-1
0
2
0
1
0
0
2
-1
1
2
2
1
0
1
1
-1
2
-1
-1
0
2
1
-1
2
0
2
2
2
0
1
-1
-1
0
1
1
-1
-1
2
1
0
1
1
0
2
1
1
0
2
-1
0
2
1
1
2...

result:

ok 200000 numbers

Extra Test:

score: 0
Extra Test Passed