QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#536279#8551. DFS Order 5QSteve_PaulTL 86ms65980kbC++235.2kb2024-08-28 22:13:202024-08-28 22:13:22

Judging History

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

  • [2024-08-28 22:13:22]
  • 评测
  • 测评结果:TL
  • 用时:86ms
  • 内存:65980kb
  • [2024-08-28 22:13:20]
  • 提交

answer

#include <vector>
#include <iostream>
#include <functional>

using namespace std;

struct SegmentTree
{
    constexpr static int N = 1e6 + 5;

#define rson ((k << 1) + 1)
#define lson (k << 1)
#define me (k)
#define mid ((a[me].l + a[me].r) >> 1)

    struct node
    {
        int l, r;
        int sum;
        int lazy;

        node()
        {
            l = r = sum = 0;
            lazy = -1;
        }
    };

    vector<node> a = vector<node>(N * 4);

    void update(int k)
    {
        a[me].sum = a[lson].sum + a[rson].sum;
    }

    void build(int k, int l, int r)
    // 当前在k上,建树
    {
        a[me].l = l;
        a[me].r = r;
        if (l == r)
        {
            a[me].sum = 0;
            return;
        }
        build(lson, a[me].l, mid);
        build(rson, mid + 1, a[me].r);
        update(k);
    }

    void pushdown(int k)
    {
        if (a[me].l == a[me].r)
        {
            a[me].lazy = -1;
            return;
        }
        a[lson].sum = (a[lson].r - a[lson].l + 1) * a[me].lazy;
        a[rson].sum = (a[rson].r - a[rson].l + 1) * a[me].lazy;
        a[lson].lazy = a[me].lazy;
        a[rson].lazy = a[me].lazy;
        a[me].lazy = -1;
    }

    int query(int k, int idx)
    {
        if (a[me].lazy != -1)
            pushdown(k);
        if (a[me].l == idx && a[me].r == idx)
            return a[me].sum;
        if (idx <= mid)
            return query(lson, idx);
        return query(rson, idx);
    }

    void set_segment(int k, int l, int r, int x)
    {
        if (a[k].l == l && a[k].r == r)
        {
            a[k].sum = (r - l + 1) * x;
            a[k].lazy = x;
            return;
        }
        if (a[me].lazy != -1)
            pushdown(k);
        if (r <= mid)
            set_segment(lson, l, r, x);
        else if (l > mid)
            set_segment(rson, l, r, x);
        else
        {
            set_segment(lson, l, mid, x);
            set_segment(rson, mid + 1, r, x);
        }
        update(k);
    }
#undef rson
#undef lson
#undef me
#undef mid
};

void solve()
{
    int n;
    cin >> n;
    int q;
    cin >> q;
    SegmentTree st;
    st.build(1, 1, n);
    vector<vector<int>> tree(n + 1);
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        tree[u].emplace_back(v);
        tree[v].emplace_back(u);
    }
    vector<int> dfn(n + 1);
    vector<int> ofn(n + 1);
    vector<int> sz(n + 1);
    vector<int> ffa(n + 1);
    vector<int> depth(n + 1);
    //SegmentTree st;

    int dfncnt = 0;
    function<void(int, int)> dfs = [&](int node, int fa) -> void
    {
        dfncnt++;
        dfn[node] = dfncnt;
        depth[node] = depth[fa] + 1;
        ffa[node] = fa;
        for (const int& child : tree[node])
        {
            if (child == fa) continue;
            dfs(child, node);
        }
        ofn[node] = dfncnt;
        sz[node] = ofn[node] - dfn[node];
    };

    dfs(1, 0);

    function<bool(int, int)> is_in_tree = [&](int node, int fa) -> bool
    {
        return dfn[node] >= dfn[fa] && dfn[node] <= ofn[fa];
    };

    vector<int> stk;
    auto pop_stk = [&]() -> void
    {
        int node = stk.back();
        stk.pop_back();
    };
    auto push_stk = [&](int node) -> void
    {
        stk.push_back(node);
        st.set_segment(1, dfn[node], dfn[node], 1);
    };

    vector<int> k;
    vector<int> tmp;
    while (q--)
    {
        int qq;
        cin >> qq;
        k.resize(qq + 1);
        for (int i = 1; i <= qq; i++)
            cin >> k[i];

        // TODO: clear the SegmentTree
        st.set_segment(1, 1, n, 0);

        tmp.clear();
        int node = k[1];

        stk.clear();
        while (node != 0)
        {
            tmp.push_back(node);
            node = ffa[node];
        }
        reverse(tmp.begin(), tmp.end());
        for (const int& nd : tmp)
            push_stk(nd);

        bool isok = true;

        if (!is_in_tree(k[min(1 + sz[k[1]], qq)], k[1]))
            isok = false;

        for (int i = 2; i <= qq; i++)
        {
            if (!is_in_tree(k[min(i + sz[k[i]], qq)], k[i])) isok = false;
            if (!isok) break;
            int thisfa = ffa[k[i]];
            int nearfa = -1;
            while (!stk.empty() && stk.back() != thisfa)
            {
                nearfa = stk.back();
                pop_stk();
            }
            if (stk.empty()) isok = false;
            if (!isok) break;

            // TODO: ensure it's not visited in SegmentTree
            if (st.query(1, dfn[k[i]]))
                isok = false;
            if (!isok) break;

            push_stk(k[i]);

            if (thisfa != k[i - 1])
            {
                // TODO: ensure the childs of nearfa and itself is visited
                st.set_segment(1, dfn[nearfa], ofn[nearfa], 1);
            }
        }

        if (isok) cout << "Yes\n";
        else cout << "No\n";
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
}

/*
*
6 4
1 2
1 3
2 4
3 5
2 6
3 4 6 3
3 4 6 1
4 2 6 4 3
4 1 4 6 3
*/

詳細信息

Test #1:

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

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: 38ms
memory: 65512kb

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: 55ms
memory: 65660kb

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: 55ms
memory: 65776kb

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: 41ms
memory: 65680kb

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: 54ms
memory: 65480kb

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: 36ms
memory: 65676kb

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: 39ms
memory: 65852kb

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: 40ms
memory: 65852kb

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: 36ms
memory: 65680kb

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: 36ms
memory: 65680kb

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: 63ms
memory: 65788kb

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: 56ms
memory: 65684kb

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: 44ms
memory: 65488kb

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: 47ms
memory: 65564kb

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: 32ms
memory: 65436kb

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: 27ms
memory: 65684kb

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: 40ms
memory: 65856kb

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: 26ms
memory: 65484kb

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: 36ms
memory: 65776kb

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: 55ms
memory: 65968kb

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: 66ms
memory: 65760kb

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: 82ms
memory: 65980kb

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: 86ms
memory: 65756kb

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: -100
Time Limit Exceeded

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:


result: