QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#393123#8551. DFS Order 5hos_lyricAC ✓274ms22200kbC++1412.9kb2024-04-18 10:22:592024-04-18 10:22:59

Judging History

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

  • [2024-04-18 10:22:59]
  • 评测
  • 测评结果:AC
  • 用时:274ms
  • 内存:22200kb
  • [2024-04-18 10:22:59]
  • 提交

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

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


// T: monoid representing information of an interval.
//   T()  should return the identity.
//   T(S s)  should represent a single element of the array.
//   T::pull(const T &l, const T &r)  should pull two intervals.
template <class T> struct SegmentTreePoint {
  int logN, n;
  vector<T> ts;
  SegmentTreePoint() : logN(0), n(0) {}
  explicit SegmentTreePoint(int n_) {
    for (logN = 0, n = 1; n < n_; ++logN, n <<= 1) {}
    ts.resize(n << 1);
  }
  template <class S> explicit SegmentTreePoint(const vector<S> &ss) {
    const int n_ = ss.size();
    for (logN = 0, n = 1; n < n_; ++logN, n <<= 1) {}
    ts.resize(n << 1);
    for (int i = 0; i < n_; ++i) at(i) = T(ss[i]);
    build();
  }
  T &at(int i) {
    return ts[n + i];
  }
  void build() {
    for (int u = n; --u; ) pull(u);
  }

  inline void pull(int u) {
    ts[u].pull(ts[u << 1], ts[u << 1 | 1]);
  }

  // Changes the value of point a to s.
  template <class S> void change(int a, const S &s) {
    assert(0 <= a); assert(a < n);
    ts[a += n] = T(s);
    for (; a >>= 1; ) pull(a);
  }

  // Applies T::f(args...) to point a.
  template <class F, class... Args>
  void ch(int a, F f, Args &&... args) {
    assert(0 <= a); assert(a < n);
    (ts[a += n].*f)(args...);
    for (; a >>= 1; ) pull(a);
  }

  // Calculates the product for [a, b).
  T get(int a, int b) {
    assert(0 <= a); assert(a <= b); assert(b <= n);
    if (a == b) return T();
    T prodL, prodR, t;
    for (a += n, b += n; a < b; a >>= 1, b >>= 1) {
      if (a & 1) { t.pull(prodL, ts[a++]); prodL = t; }
      if (b & 1) { t.pull(ts[--b], prodR); prodR = t; }
    }
    t.pull(prodL, prodR);
    return t;
  }

  // Calculates T::f(args...) of a monoid type for [a, b).
  //   op(-, -)  should calculate the product.
  //   e()  should return the identity.
  template <class Op, class E, class F, class... Args>
#if __cplusplus >= 201402L
  auto
#else
  decltype((std::declval<T>().*F())())
#endif
  get(int a, int b, Op op, E e, F f, Args &&... args) {
    assert(0 <= a); assert(a <= b); assert(b <= n);
    if (a == b) return e();
    auto prodL = e(), prodR = e();
    for (a += n, b += n; a < b; a >>= 1, b >>= 1) {
      if (a & 1) prodL = op(prodL, (ts[a++].*f)(args...));
      if (b & 1) prodR = op((ts[--b].*f)(args...), prodR);
    }
    return op(prodL, prodR);
  }

  // Find min b s.t. T::f(args...) returns true,
  // when called for the partition of [a, b) from left to right.
  //   Returns n + 1 if there is no such b.
  template <class F, class... Args>
  int findRight(int a, F f, Args &&... args) {
    assert(0 <= a); assert(a <= n);
    if ((T().*f)(args...)) return a;
    if (a == n) return n + 1;
    a += n;
    for (; ; a >>= 1) if (a & 1) {
      if ((ts[a].*f)(args...)) {
        for (; a < n; ) {
          if (!(ts[a <<= 1].*f)(args...)) ++a;
        }
        return a - n + 1;
      }
      ++a;
      if (!(a & (a - 1))) return n + 1;
    }
  }

  // Find max a s.t. T::f(args...) returns true,
  // when called for the partition of [a, b) from right to left.
  //   Returns -1 if there is no such a.
  template <class F, class... Args>
  int findLeft(int b, F f, Args &&... args) {
    assert(0 <= b); assert(b <= n);
    if ((T().*f)(args...)) return b;
    if (b == 0) return -1;
    b += n;
    for (; ; b >>= 1) if ((b & 1) || b == 2) {
      if ((ts[b - 1].*f)(args...)) {
        for (; b <= n; ) {
          if (!(ts[(b <<= 1) - 1].*f)(args...)) --b;
        }
        return b - n - 1;
      }
      --b;
      if (!(b & (b - 1))) return -1;
    }
  }
};  // SegmentTreePoint<T>

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

constexpr int INF = 1001001001;

struct NodeMin {
  int mn;
  NodeMin() : mn(+INF) {}
  NodeMin(int val) : mn(val) {}
  void pull(const NodeMin &l, const NodeMin &r) {
    mn = min(l.mn, r.mn);
  }
  void ch(int val) {
    mn = val;
  }
  void chmin(int val) {
    if (mn > val) mn = val;
  }
  bool test(int tar) const {
    return (mn <= tar);
  }
};
struct NodeMax {
  int mx;
  NodeMax() : mx(-INF) {}
  NodeMax(int val) : mx(val) {}
  void pull(const NodeMax &l, const NodeMax &r) {
    mx = max(l.mx, r.mx);
  }
  void ch(int val) {
    mx = val;
  }
  void chmax(int val) {
    if (mx < val) mx = val;
  }
  bool test(int tar) const {
    return (mx >= tar);
  }
};

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


int N, Q;
vector<int> A, B;
int K;
vector<int> U;

Hld hld;

SegmentTreePoint<NodeMin> segMin;
SegmentTreePoint<NodeMax> segMax;
int rangeLca(int kL, int kR) {
  assert(kL < kR);
  const int mn = segMin.get(kL, kR).mn;
  const int mx = segMax.get(kL, kR).mx;
  return hld.lca(hld.sid[mn], hld.sid[mx]);
}

bool solve(int kL, int kR, int u, bool pre, bool suf) {
// cerr<<U<<"; [solve] "<<kL<<" "<<kR<<" "<<u<<" "<<pre<<" "<<suf<<endl;
  assert(kL < kR);
  if (!pre) {
    u = rangeLca(kL, kR);
  }
  if (U[kL] == u) {
    ++kL;
    pre = true;
  } else {
    if (pre) return false;
  }
  set<int> used;
  for (int k = kL; k < kR; ) {
    if (U[k] == u) return false;
    int lo = k + 1, hi = kR + 1;
    for (; lo + 1 < hi; ) {
      const int mid = (lo + hi) / 2;
      ((rangeLca(k, mid) != u) ? lo : hi) = mid;
    }
    // subtree: [k, lo)
    const int v = hld.jump(u, U[k], 1);
    if (!used.insert(v).second) return false;
    const bool res = solve(k, lo, v, pre || (k != kL), suf || (lo != kR));
    if (!res) return false;
    k = lo;
  }
  if (pre && suf && used.size() != hld.graph[u].size()) return false;
  return true;
}

bool solve() {
  vector<int> js(K);
  for (int k = 0; k < K; ++k) js[k] = hld.dis[U[k]];
  segMin = SegmentTreePoint<NodeMin>(js);
  segMax = SegmentTreePoint<NodeMax>(js);
  return solve(0, K, 0, false, false);
}

int main() {
  for (; ~scanf("%d%d", &N, &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];
    }
    
    hld = Hld(N);
    for (int i = 0; i < N - 1; ++i) {
      hld.ae(A[i], B[i]);
    }
    hld.build(0);
// cerr<<hld<<endl;
    
    for (int q = 0; q < Q; ++q) {
      scanf("%d", &K);
      U.resize(K);
      for (int k = 0; k < K; ++k) {
        scanf("%d", &U[k]);
        --U[k];
      }
// cerr<<"U = "<<U<<endl;
      const bool ans = solve();
      puts(ans ? "Yes" : "No");
    }
  }
  return 0;
}

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

详细

Test #1:

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

input:

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

output:

No
No
Yes
No
No
Yes
Yes

result:

ok 7 tokens

Test #2:

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

input:

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

output:

No
No
No
Yes
No
No
No
No
Yes
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
Yes
No
No
No
No
No
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
Yes
Yes
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
N...

result:

ok 100000 tokens

Test #3:

score: 0
Accepted
time: 92ms
memory: 3732kb

input:

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

output:

No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
Yes
No
No
No
No
No
Yes
Yes
No
No
No
No
No
No
No
No
No...

result:

ok 95326 tokens

Test #4:

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

input:

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

output:

No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
N...

result:

ok 64393 tokens

Test #5:

score: 0
Accepted
time: 76ms
memory: 3780kb

input:

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

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
Yes
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 48628 tokens

Test #6:

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

input:

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

output:

No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
N...

result:

ok 39193 tokens

Test #7:

score: 0
Accepted
time: 62ms
memory: 3752kb

input:

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

output:

No
No
No
Yes
No
No
No
No
Yes
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
Yes
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
Yes
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 100000 tokens

Test #8:

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

input:

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

output:

No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
Yes
Yes
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 100000 tokens

Test #9:

score: 0
Accepted
time: 58ms
memory: 3784kb

input:

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

output:

No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
Yes
No
No
No
Yes
No
No
Yes
No
No
Yes
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 100000 tokens

Test #10:

score: 0
Accepted
time: 62ms
memory: 3780kb

input:

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

output:

No
No
No
No
Yes
No
No
Yes
Yes
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
Yes
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
...

result:

ok 100000 tokens

Test #11:

score: 0
Accepted
time: 58ms
memory: 3728kb

input:

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

output:

No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
Yes
Yes
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No...

result:

ok 100000 tokens

Test #12:

score: 0
Accepted
time: 94ms
memory: 3732kb

input:

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

output:

No
No
No
No
No
No
Yes
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
Yes
No
No
No
No
No
Yes
Yes
No
No
No
No
No
No
No
No
N...

result:

ok 95326 tokens

Test #13:

score: 0
Accepted
time: 83ms
memory: 3732kb

input:

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

output:

No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
N...

result:

ok 64393 tokens

Test #14:

score: 0
Accepted
time: 76ms
memory: 3752kb

input:

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

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
Yes
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 48628 tokens

Test #15:

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

input:

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

output:

No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
N...

result:

ok 39193 tokens

Test #16:

score: 0
Accepted
time: 45ms
memory: 3700kb

input:

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

output:

No
No
Yes
No
Yes
No
No
No
Yes
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
No
Yes
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
No
Yes
Yes
Yes
No
No
No
Yes
No
Yes
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
No
No
Yes
Yes
No
Yes
No
Yes
Yes
No
Yes
Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes...

result:

ok 100000 tokens

Test #17:

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

input:

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

output:

Yes
No
Yes
Yes
Yes
No
Yes
No
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
Yes
No
No
Yes
No
Yes
Yes
Yes
Yes
No
No
Yes
Yes
No
No
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
No
No
Yes
Yes
No
Yes
Yes
No
No
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
No
No
No
Yes
Yes
Yes
No
No
Yes
Yes
No
No
Yes
Y...

result:

ok 100000 tokens

Test #18:

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

input:

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

output:

Yes
No
Yes
No
Yes
Yes
Yes
No
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
No
Yes
Yes
No
No
No
Yes
Yes
No
Yes
Yes
No
No
Yes
No
No
Yes
No
No
Yes
Yes
No
No
Yes
Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
No
No
No
Yes
No
No
Yes
Yes
No
Yes
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
No
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
...

result:

ok 100000 tokens

Test #19:

score: 0
Accepted
time: 45ms
memory: 3780kb

input:

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

output:

Yes
No
Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
Yes
Yes
No
No
No
No
No
No
No
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
No
No
No
Yes
Yes
Yes
No
Yes
No
No
Yes
Yes
Yes
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Y...

result:

ok 100000 tokens

Test #20:

score: 0
Accepted
time: 46ms
memory: 3728kb

input:

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

output:

No
Yes
No
Yes
Yes
No
Yes
Yes
No
Yes
Yes
No
No
Yes
Yes
Yes
No
Yes
Yes
Yes
No
Yes
No
Yes
Yes
No
Yes
No
No
Yes
Yes
Yes
Yes
No
Yes
Yes
No
Yes
No
Yes
Yes
No
No
Yes
Yes
Yes
Yes
No
No
Yes
Yes
No
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
No
No
No
Yes
No
No
Yes
Yes
Yes
No
Ye...

result:

ok 100000 tokens

Test #21:

score: 0
Accepted
time: 82ms
memory: 3712kb

input:

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

output:

No
No
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
No
No
No
Yes
No
Yes
No
No
No
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
No
No
Yes
No
Yes
No
Yes
No
No
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
No
No
Yes
No
Yes
Yes
No
No
No
No
Yes
Yes
No
No
Yes
No
Yes
No
No
Yes
Yes
Yes
No
Yes
No
No
Yes
Yes
No
No
Yes...

result:

ok 100000 tokens

Test #22:

score: 0
Accepted
time: 111ms
memory: 3728kb

input:

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

output:

Yes
Yes
Yes
Yes
No
Yes
No
Yes
No
No
Yes
No
Yes
No
Yes
Yes
No
Yes
Yes
No
Yes
No
Yes
Yes
No
No
Yes
Yes
No
Yes
Yes
Yes
Yes
No
No
Yes
Yes
No
No
Yes
No
Yes
No
No
Yes
No
No
Yes
Yes
Yes
Yes
No
No
Yes
No
No
Yes
Yes
Yes
Yes
No
Yes
Yes
No
Yes
Yes
No
No
No
No
No
Yes
Yes
No
Yes
Yes
Yes
No
Yes
No
No
No
Yes
No
No...

result:

ok 100000 tokens

Test #23:

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

input:

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

output:

Yes
Yes
No
No
Yes
Yes
No
Yes
Yes
Yes
Yes
No
Yes
No
Yes
No
Yes
No
Yes
Yes
Yes
No
Yes
Yes
No
No
No
Yes
Yes
Yes
No
Yes
No
Yes
No
No
Yes
No
No
No
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
No
No
No
Yes
No
No
No
No
Yes
No
No
No
Yes
Yes
Yes
No
No
Yes
Yes
No
No
No
No
No
No
Yes
No
No
Yes
Yes
No
Y...

result:

ok 92713 tokens

Test #24:

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

input:

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

output:

No
Yes
Yes
Yes
No
No
No
Yes
No
Yes
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
Yes
Yes
Yes
No
No
Yes
Yes
Yes
No
Yes
No
No
Yes
Yes
Yes
No
No
No
Yes
No
No
No
No
No
Yes
Yes
No
No
No
Yes
Yes
Yes
No
No
Yes
No
No
No
No
Yes
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
No
No
Yes
No
Yes
No
Yes
No...

result:

ok 75394 tokens

Test #25:

score: 0
Accepted
time: 71ms
memory: 14224kb

input:

100000 100000
22031 19709
79977 20677
72195 10689
88600 65820
9422 9595
3821 93983
96434 92645
72154 63751
88298 50712
58441 10216
66429 11541
80376 50932
50750 3251
39637 9534
35886 1323
34267 26052
61878 74481
49528 38924
69738 16187
99731 43694
18246 31836
68871 3281
17124 1158
95557 48000
65959 ...

output:

No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
N...

result:

ok 100000 tokens

Test #26:

score: 0
Accepted
time: 68ms
memory: 12408kb

input:

100000 100000
6390 17242
19936 20882
46229 37775
87701 45891
93858 43746
24030 30025
21273 3891
8969 19204
31507 99402
31610 22619
57908 71859
86596 48565
69684 42945
81569 46463
11482 1436
69395 25798
83954 12570
38345 22133
99955 65046
47955 34204
37747 85317
19733 67085
12058 1916
8229 88515
3055...

output:

No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No...

result:

ok 100000 tokens

Test #27:

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

input:

100000 100000
65796 41231
47215 20437
14648 92497
7368 16204
1057 12939
57423 58031
90889 26728
19075 73300
16433 75923
44452 80414
69850 59598
99777 15742
35503 49371
20702 80793
88570 51926
92517 94171
37244 20383
29247 19506
81624 62559
2926 63517
96697 65725
29639 38173
74903 34618
313 16309
299...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 100000 tokens

Test #28:

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

input:

100000 100000
49565 66073
21944 4457
28322 40724
77401 81004
433 54017
3920 51304
21061 36288
14752 22530
92090 5883
9978 78398
92537 35543
88335 45607
83800 53358
77729 40863
1541 42486
96162 58764
41980 21524
83274 15162
84917 67941
74664 63431
54624 33582
35792 18967
29901 70394
38286 61456
86428...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 100000 tokens

Test #29:

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

input:

100000 100000
1766 4748
32844 9107
73356 52002
29127 35776
77551 96310
6586 12633
931 30529
97055 93805
71514 17120
15322 89816
48447 85139
69178 18689
88038 53343
18983 2203
31527 99630
92008 23951
82997 93138
74484 96972
36465 83542
10207 38726
70768 90541
6516 33979
57143 27898
2602 94702
72636 2...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 100000 tokens

Test #30:

score: 0
Accepted
time: 198ms
memory: 14496kb

input:

100000 100000
38656 38649
49244 49240
72097 72092
16362 16367
89712 89708
31833 31828
1776 1769
28913 28906
61888 61878
7131 7124
28437 28442
20338 20329
68540 68539
31334 31328
83244 83234
6344 6343
53941 53948
78386 78388
40417 40413
97136 97140
17048 17039
74885 74879
37932 37939
72242 72240
9052...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 100000 tokens

Test #31:

score: 0
Accepted
time: 210ms
memory: 12416kb

input:

100000 100000
91113 91209
82125 82196
17061 17030
63492 63450
86825 86766
20090 20048
98842 98857
83335 83270
8996 9015
65800 65720
49122 49155
84038 84135
45583 45609
71664 71592
80151 80184
55978 56066
84122 84142
47884 47984
6616 6659
24124 24141
44203 44230
88031 87936
21094 21143
52361 52425
93...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 100000 tokens

Test #32:

score: 0
Accepted
time: 213ms
memory: 12148kb

input:

100000 100000
50728 50654
44261 45163
22208 22565
58688 58373
32612 33030
71660 71873
89913 89664
75805 76744
71503 71934
27322 28111
55812 55356
33720 32754
48440 48264
41048 41781
93214 94182
17629 17722
17561 18146
28329 27383
98169 98356
1216 1055
84703 84515
2881 2084
87390 88222
21264 21663
43...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 100000 tokens

Test #33:

score: 0
Accepted
time: 206ms
memory: 12100kb

input:

100000 100000
31222 33552
41521 44119
50990 49903
44464 43003
15190 22921
47485 53253
74261 79380
85164 93724
59780 55724
93738 98324
63895 60609
21017 18180
433 773
93075 97786
8027 11031
12196 12724
97981 90548
96946 87968
93529 86667
20125 16341
63577 54107
90336 99374
52847 52441
35212 35612
691...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 100000 tokens

Test #34:

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

input:

100000 100000
12095 71885
9520 19536
6341 58535
9549 31319
17658 31062
26096 84345
55575 98102
41278 39200
54189 4024
9555 15722
84991 33220
57827 29323
17571 57697
89020 37327
13499 12471
15923 46106
46684 27028
68544 94977
72265 95916
25582 17437
84373 12019
40053 70207
30578 14849
99726 5741
8896...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 100000 tokens

Test #35:

score: 0
Accepted
time: 48ms
memory: 12436kb

input:

100000 100000
58286 1
92801 1
1 23835
31111 1
63517 1
1 64597
85533 1
22562 1
1 88412
75722 1
1 59697
92715 1
1 81332
74340 1
871 1
1 21972
1 54497
66797 1
10937 1
1 80448
29777 1
8287 1
1 65626
82496 1
88110 1
81770 1
79830 1
64455 1
1 5287
54867 1
19241 1
84920 1
40595 1
1 91660
86005 1
9536 1
1 4...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 100000 tokens

Test #36:

score: 0
Accepted
time: 59ms
memory: 12420kb

input:

100000 100000
1 31153
1 70648
65640 2
2 42097
1 30566
79120 79118
79694 79695
1 15175
58998 58996
46344 2
60522 1
69811 69809
2 10516
2 29288
84465 2
43108 2
46861 1
1 79362
85016 1
2 33704
2 65391
83512 83511
96951 1
62813 62814
1 80646
2 54179
88522 88521
29945 2
57863 2
2 22120
86745 1
8607 2
325...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 100000 tokens

Test #37:

score: 0
Accepted
time: 76ms
memory: 12468kb

input:

100000 100000
4 6165
61280 61285
79316 79317
75138 75139
3294 3
1 81489
10503 4
11462 4
95690 95693
6053 2
3 34295
66316 66320
9365 4
35707 5
2 4704
1 51638
13980 4
17619 5
14348 5
1 1157
38076 3
99377 99376
42362 3
58971 58969
2 48323
70177 3
5 10946
76634 76633
1 97298
5 44538
77954 1
16166 4
7346...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 100000 tokens

Test #38:

score: 0
Accepted
time: 85ms
memory: 12452kb

input:

100000 100000
69019 69027
10 20115
79300 79296
66171 66164
98706 98700
4 47454
57286 57289
78954 78960
92664 92658
5 24956
1 3044
55786 55795
73188 8
9 2296
67932 67937
8528 9
81852 81842
33011 10
51298 51293
67010 2
95125 95119
54265 4
1 35228
61407 61406
82568 82562
3 26672
5 16416
74458 74467
296...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 100000 tokens

Test #39:

score: 0
Accepted
time: 87ms
memory: 12644kb

input:

100000 100000
35 23329
87458 87437
35 99794
57784 57747
39576 3
76333 76305
49205 29
2218 21
65211 65244
36543 48
96822 96776
10507 12
77139 77096
17 337
11 19269
63630 63601
26 2484
23942 26
6 19197
89865 89888
87821 87823
15698 22
2617 8
38048 3
37076 28
17 2205
66500 66504
51236 51277
86214 86203...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 100000 tokens

Test #40:

score: 0
Accepted
time: 92ms
memory: 12476kb

input:

100000 100000
46 29253
32 11065
75112 75016
97872 97943
83462 83559
55450 55378
2 14708
89044 88960
98802 98709
88777 88765
83571 83601
37363 60
57778 57821
12825 71
42 13650
68 27305
9 25066
52407 52445
92990 92923
79698 79702
38704 66
75102 75030
64 3133
47898 1
3047 64
41 46208
51715 51738
93 669...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 100000 tokens

Test #41:

score: 0
Accepted
time: 62ms
memory: 22200kb

input:

100000 100000
64269 64268
66535 66536
9759 9758
42907 42908
80000 84213
80000 83489
27749 27748
86199 80000
80000 80659
11615 11614
93420 1
2529 2528
96161 1
79473 79474
83518 80000
43109 43110
37111 37112
46604 46603
1 93666
54540 54541
84237 80000
62717 62718
24720 24719
57226 57225
8333 8334
1572...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 100000 tokens

Test #42:

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

input:

100000 37
29162 63623
96664 54044
11535 67257
10642 29054
10206 58115
95878 4300
94836 69937
78765 28295
22874 53200
43075 87524
13107 77611
7813 13031
51591 40743
7168 67498
25699 32495
7125 37661
28803 9718
18154 16537
86140 56605
89290 3771
36638 63730
57297 68534
25220 8566
98229 56905
48005 462...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 37 tokens

Test #43:

score: 0
Accepted
time: 264ms
memory: 16480kb

input:

100000 33
60074 18401
35678 11648
38252 92824
51971 94160
24926 70750
19026 46634
14302 30542
40772 16995
74011 54458
39554 11112
15458 2470
40516 48499
47136 92413
74957 81119
86949 69165
2914 22736
93669 29627
81851 64391
96131 18955
85414 48801
11987 81925
44883 43397
57347 15860
25315 42763
2252...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 33 tokens

Test #44:

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

input:

1 1
1 1

output:

Yes

result:

ok "Yes"

Extra Test:

score: 0
Extra Test Passed