[CSP-J 2024] 接龙

GitHub 跳转原题关系图返回列表

把接龙过程建成有颜色的边，用两个接龙人压缩颜色状态，并用扫描窗口批量处理连续子序列转移。

OJ: luogu

题目 ID: P11230

难度:普及+/提高

标签:建模动态规划状态压缩滑动窗口模拟

日期: 2026-07-05 21:24

题意

有 $n$ 个人，每个人有一个整数序列 $S_i$ 。每一轮选择一个人 $p$ ，从他的序列中选择一个长度在 $[2,k]$ 的连续子序列作为接龙序列。

规则是：

第一轮的接龙序列必须以 $1$ 开头；
之后每轮的接龙序列必须以上一轮的最后一个数开头；
相邻两轮不能由同一个人接龙。

每个询问给出 $r$ 和 $c$ ，问是否能进行恰好 $r$ 轮，并让最后一轮的最后一个数为 $c$ 。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107// brute.cpp：小数据暴力解，显式枚举每个人词库产生的所有有色边。
#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int to;
    int person;
};

const int MAXV = 205;

vector<Edge> edges[MAXV];
bool cur[MAXV][15], nxt[MAXV][15];
bool answer[105][MAXV];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, k, q;
        cin >> n >> k >> q;

        for (int i = 0; i < MAXV; i++) {
            edges[i].clear();
            for (int p = 0; p < 15; p++) {
                cur[i][p] = false;
                nxt[i][p] = false;
            }
            for (int r = 0; r < 105; r++) {
                answer[r][i] = false;
            }
        }

        vector<vector<int> > seq(n + 1);
        for (int p = 1; p <= n; p++) {
            int len;
            cin >> len;
            seq[p].resize(len + 1);
            for (int i = 1; i <= len; i++) {
                cin >> seq[p][i];
            }
            for (int l = 1; l <= len; l++) {
                for (int r = l + 1; r <= len && r <= l + k - 1; r++) {
                    int from = seq[p][l];
                    int to = seq[p][r];
                    if (from < MAXV && to < MAXV) {
                        edges[from].push_back({to, p});
                    }
                }
            }
        }

        vector<int> query_r(q + 1), query_c(q + 1);
        int max_r = 0;
        for (int i = 1; i <= q; i++) {
            cin >> query_r[i] >> query_c[i];
            max_r = max(max_r, query_r[i]);
        }

        cur[1][0] = true;
        for (int round = 1; round <= max_r; round++) {
            for (int v = 0; v < MAXV; v++) {
                for (int p = 0; p < 15; p++) {
                    nxt[v][p] = false;
                }
            }

            for (int from = 1; from < MAXV; from++) {
                for (int i = 0; i < (int)edges[from].size(); i++) {
                    int to = edges[from][i].to;
                    int person = edges[from][i].person;
                    bool ok = false;
                    for (int last = 0; last <= n; last++) {
                        if (cur[from][last] && last != person) {
                            ok = true;
                        }
                    }
                    if (ok) {
                        nxt[to][person] = true;
                        answer[round][to] = true;
                    }
                }
            }

            for (int v = 0; v < MAXV; v++) {
                for (int p = 0; p < 15; p++) {
                    cur[v][p] = nxt[v][p];
                }
            }
        }

        for (int i = 1; i <= q; i++) {
            int r = query_r[i];
            int c = query_c[i];
            if (c < MAXV && answer[r][c]) {
                cout << 1 << '\n';
            } else {
                cout << 0 << '\n';
            }
        }
    }

    return 0;
}

下面是另一种「状态搜索」风格的暴力写法。它把状态写成“当前轮数、当前数值、上一轮接龙人”，再递归枚举下一条能走的接龙边：

另一种暴力写法：状态搜索

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115// brute_01_style.cpp：状态搜索风格暴力，递归枚举每一轮能走的接龙边。
#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int to;
    int person;
};

int n, k, q;
int max_value;
int target_round, target_value;
vector<vector<int> > seq;
vector<vector<Edge> > edges;
map<long long, int> memo; // 0 表示未知，1 表示失败，2 表示成功。

long long make_key(int round, int value, int last_person) {
    return ((long long)round * (max_value + 1) + value) * (n + 1) + last_person;
}

bool dfs_game(int round, int value, int last_person) {
    if (round == target_round) {
        return value == target_value;
    }
    if (value < 0 || value > max_value) {
        return false;
    }

    long long key = make_key(round, value, last_person);
    auto it = memo.find(key);
    if (it != memo.end()) {
        return it->second == 2;
    }

    // 下一轮可以选择一条从当前值出发、且不是同一个人的边。
    for (int i = 0; i < (int)edges[value].size(); i++) {
        int to = edges[value][i].to;
        int person = edges[value][i].person;
        if (person == last_person) {
            continue;
        }
        if (dfs_game(round + 1, to, person)) {
            memo[key] = 2;
            return true;
        }
    }

    memo[key] = 1;
    return false;
}

void build_edges() {
    edges.assign(max_value + 1, vector<Edge>());

    for (int person = 1; person <= n; person++) {
        int len = (int)seq[person].size() - 1;
        for (int l = 1; l <= len; l++) {
            for (int r = l + 1; r <= len && r <= l + k - 1; r++) {
                int from = seq[person][l];
                int to = seq[person][r];
                if (from <= max_value && to <= max_value) {
                    Edge e;
                    e.to = to;
                    e.person = person;
                    edges[from].push_back(e);
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        cin >> n >> k >> q;

        seq.assign(n + 1, vector<int>());
        max_value = 1;
        for (int person = 1; person <= n; person++) {
            int len;
            cin >> len;
            seq[person].resize(len + 1);
            for (int i = 1; i <= len; i++) {
                cin >> seq[person][i];
                max_value = max(max_value, seq[person][i]);
            }
        }

        vector<int> query_r(q + 1), query_c(q + 1);
        for (int i = 1; i <= q; i++) {
            cin >> query_r[i] >> query_c[i];
            max_value = max(max_value, query_c[i]);
        }

        build_edges();

        for (int i = 1; i <= q; i++) {
            target_round = query_r[i];
            target_value = query_c[i];
            memo.clear();

            if (dfs_game(0, 1, 0)) {
                cout << 1 << '\n';
            } else {
                cout << 0 << '\n';
            }
        }
    }

    return 0;
}

这题不是那种只靠一个漂亮公式就能解决的题。更准确地说，它是一个“把暴力模型压到可实现”的题：

先把接龙过程建模清楚；
再发现暴力建边会爆；
最后用两个压缩技巧，把边数和状态数都压下来。

brute.cpp 对小数据显式枚举每个人序列中所有合法连续子序列，把每个连续子序列看成一条有颜色的边：

text

1起点数值 -> 终点数值，颜色 = 接龙人编号

然后做恰好 $r$ 步的 DP，并检查相邻边颜色不同。

正解也沿用这个模型，但不真的建出所有边。原因是：如果某个人的序列长度为 $len$ ，当 $k$ 很大时，一个开头位置后面可能连出很多结尾位置，边数接近 $O(len^2)$ 。

所以本题真正值得抓住的思维点只有两个。

思维点 1：颜色状态压缩

第 $round$ 轮结束后，我们关心的状态可以写成：

text

1最后一个数值是 value，上一轮是哪个人接龙

下一轮如果想使用人 $p$ ，只需要判断：

text

1当前 value 有没有一种到达方式，使得上一轮接龙人不是 p

这句话很关键。它说明我们不需要保存“所有能到达 $value$ 的上一轮接龙人”，只需要保存最多两个不同的人。

当前 $value$ 保存的人	下一轮用人 $p$ 是否可行	原因
没有人	不可行	$value$ 本身不可达
$\{0\}$	可行	$0$ 表示第 0 轮，还没有真正的接龙人
$\{x\}$ 且 $x != p$	可行	上一轮不是 $p$
$\{p\}$	不可行	会连续使用同一个人
$\{p, x\}$ 且 $x != p$	可行	可以选择上一轮为 $x$ 的那条路径

因此，对每个值 $value$ ，数组里只保存两个不同的上一轮接龙人即可：

$last1[value]$ ：第一个代表人；
$last2[value]$ ：第二个不同的代表人。

如果只有一个代表人且正好等于当前人 $p$ ，就不能从这个值开始；如果有第二个代表人，就说明存在另一条路径可以避开 $p$ 。

思维点 2：连续子序列批量转移

固定某个人 $p$ ，从左到右扫描他的序列。

如果位置 $i$ 的值可以作为本轮接龙序列的开头，那么合法结尾位置是：

text

1i+1, i+2, ..., min(len, i+k-1)

也就是说，一个开头位置会覆盖后面一段结尾位置。我们不必枚举这段里的每一条边，只需要维护当前已经被覆盖的结尾区间：

text

1[range_start, range_end]

扫描到位置 $pos$ 时：

如果 $seq[pos]$ 能作为开头，就把它贡献的结尾区间加入当前窗口；
如果 $pos$ 落在 $[range_start, range_end]$ 中，就说明它能作为某个合法连续子序列的结尾；
把 $seq[pos]$ 作为本轮可达结尾值，并记录当前接龙人 $p$ 。

注意窗口的左端不能随便丢掉。当前位置 $pos$ 可能已经被之前的开头覆盖，同时它自己又能作为新的开头。代码中只有当旧窗口已经过期时，才把 $range_start$ 重设成 $pos + 1$ ，这样既保证长度至少为 $2$ ，又不会漏掉当前位置作为结尾的情况。

完整转移过程

每一轮做一次状态转移：

上一轮状态保存在 $last1[]$ 、 $last2[]$ 中；
本轮新状态写到 $next1[]$ 、 $next2[]$ 中；
对每个人 $p$ 扫描他的序列；
用 $can_start(value, p)$ 判断某个值能不能作为本轮开头；
用 $[range_start, range_end]$ 判断当前位置能不能作为本轮结尾；
本轮结束后，把 $next1[]$ 、 $next2[]$ 复制回 $last1[]$ 、 $last2[]$ 。

第一轮之前，认为结尾值是 $1$ ，上一轮接龙人为特殊编号 $0$ ，表示还没有人接龙，因此第一轮可以使用任何人。

所有询问的 $r \leqslant 100$ ，所以可以预处理每一轮哪些结尾值可达，然后直接回答询问。

状态公式

本题的“DP”本质是逐轮可达性状态机。设第 $round$ 轮结束后，数值 $v$ 对应的代表接龙人集合为：

S_{round}[v] = \{first_v,\ second_v\}

这里集合大小最多为 $2$ ，表示“第 $round$ 轮结束在 $v$ 时，上一轮接龙人可能是谁”。

判断某个值 $v$ 能否被人 $p$ 作为下一轮开头：

allowed(v, p) = \begin{cases} \text{false}, & S_{round}[v] = \varnothing \\ \text{true}, & 0 \in S_{round}[v] \\ \text{true}, & \exists x \in S_{round}[v], x \neq p \\ \text{false}, & S_{round}[v] = \{p\} \end{cases}

如果扫描人 $p$ 的序列时，位置 $pos$ 落入当前覆盖窗口，就把当前人加入下一轮状态：

S_{round+1}[seq[pos]] \leftarrow S_{round+1}[seq[pos]] \cup \{p\}

实现时这个集合只保留两个不同的人；超过两个也不需要继续保存，因为判断“是否存在一个人不等于 $p$ ”时，两个代表已经足够。

样例 1 第一轮扫描

以样例 1 为例： $n = 3, k = 3$ ，三个人的序列分别为 $[1,2,3,4,1]$ 、 $[1,2,5]$ 、 $[5,1,6]$ 。

第 0 轮只有状态：

text

1S_0[1] = {0}

第一轮扫描过程如下：

接龙人	可作为开头的位置	覆盖的结尾位置	本轮产生的 $(值, 人)$
人 1： $[1,2,3,4,1]$	pos=1，值为 1	pos=2…3	$(2,1)$ , $(3,1)$
人 2： $[1,2,5]$	pos=1，值为 1	pos=2…3	$(2,2)$ , $(5,2)$
人 3： $[5,1,6]$	pos=2，值为 1	pos=3	$(6,3)$

所以第一轮结束后的代表状态是：

值 $v$	第一轮结束时保存的接龙人
2	$\{1, 2\}$
3	$\{1\}$
5	$\{2\}$
6	$\{3\}$

这张表展示了两个核心点：值 $2$ 可以由人 1 或人 2 得到，所以它保存两个代表人；而连续子序列并没有一条条显式建边，扫描时靠覆盖窗口直接得到可作为结尾的位置。

询问验证：

询问 $(r, c)$	第 $r$ 轮 $c$ 是否可达	输出
$(1, 2)$	第 1 轮值 2 可达 ✓	1
$(1, 4)$	第 1 轮值 4 不可达 ✗	0
$(2, 4)$	第 2 轮值 4 可达 ✓	1
$(3, 4)$	第 3 轮值 4 不可达 ✗	0
$(6, 6)$	第 6 轮值 6 可达 ✓	1
$(1, 1)$	接龙序列长度 ≥ 2，值 1 不可达 ✗	0
$(7, 7)$	值 7 从未出现 ✗	0

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-05 21:47
 * update_at: 2026-07-08 23:20
 */
// main.cpp：按人扫描序列做轮次 DP，用 reach_until 技巧批量标记可达值。
#include <bits/stdc++.h>
using namespace std;

const int MAXV = 200005;   // 值的范围
const int MAXN = 100005;   // 人数
const int MAXE = 200005;   // 序列总长度
const int MAXR = 105;      // 最大轮数（游戏状态在此之内必收敛）

// ---------- 所有人序列的平铺存储 ----------
int seq_vals[MAXE + 5];     // 所有人的序列值拼接
int seq_start[MAXN + 5];    // seq_start[p] = 第 p 个人的序列起始下标（1-indexed）
int seq_len[MAXN + 5];      // seq_len[p] = 第 p 个人序列的长度

// reachable[r][v]：第 r 轮结束时值 v 是否可达
bool reachable[MAXR][MAXV];

// ---------- 轮次状态 ----------
// last1[v]：值 v 在上一轮的第一个生产者
// last2[v]：值 v 在上一轮的第二个生产者（同一轮中另一个不同的人）
// -1 不可达，0 第 0 轮（初始状态，任何人都可用）
int last1[MAXV], last2[MAXV];

// 判断值 v 是否可以作为本轮 person 的开头：
// 上轮必须有人以 v 结尾，且本轮的人不能与上轮第一生产者相同
// 除非上轮还有另一个不同的人也以 v 结尾
bool can_start(int v, int person) {
    if (last1[v] == -1) return false;
    if (last1[v] == 0) return true;
    if (last1[v] != person) return true;
    return last2[v] != -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, k, q;
        cin >> n >> k >> q;

        // 读入每个人的序列
        int cur = 1;
        for (int p = 1; p <= n; p++) {
            int len;
            cin >> len;
            seq_start[p] = cur;
            seq_len[p] = len;
            for (int j = 1; j <= len; j++) {
                cin >> seq_vals[cur];
                cur++;
            }
        }

        // 读入所有查询，确定最大轮数
        int query_r[MAXN], query_c[MAXN];
        int max_r = 0;
        for (int i = 1; i <= q; i++) {
            cin >> query_r[i] >> query_c[i];
            if (query_r[i] > max_r) max_r = query_r[i];
        }

        // 初始化第 0 轮状态
        memset(last1, -1, sizeof(last1));
        memset(last2, -1, sizeof(last2));
        memset(reachable, 0, sizeof(reachable));
        last1[1] = 0;  // 第 0 轮值 1 可达

        // ---- 逐轮 DP ----
        int next1[MAXV], next2[MAXV]; // 本轮新产生的值的第一、第二生产者

        for (int round = 1; round <= max_r; round++) {
            memset(next1, -1, sizeof(next1));
            memset(next2, -1, sizeof(next2));

            for (int p = 1; p <= n; p++) {
                // 当前已经被某些开头位置覆盖的结尾区间 [range_start, range_end]。
                // 一个开头 pos 只能覆盖 pos + 1 到 pos + k - 1，保证长度至少为 2。
                int range_start = 1;
                int range_end = 0;
                int base = seq_start[p] - 1;
                int len = seq_len[p];

                for (int pos = 1; pos <= len; pos++) {
                    int v = seq_vals[base + pos];

                    // 步骤 1：判断 pos 能否做开头，若可以则拉宽结尾窗口。
                    if (can_start(v, p)) {
                        int new_end = min(len, pos + k - 1);
                        if (range_end < pos) {
                            range_start = pos + 1;
                            range_end = new_end;
                        } else {
                            range_end = max(range_end, new_end);
                        }
                    }

                    // 步骤 2：判断 pos 能否做结尾。
                    if (pos >= range_start && pos <= range_end) {
                        if (next1[v] == -1) {
                            next1[v] = p;
                        } else if (next2[v] == -1 && next1[v] != p) {
                            next2[v] = p;
                        }
                        reachable[round][v] = true;
                    }
                }
            }

            // 本轮状态 → 下一轮的 "上一轮" 状态
            memcpy(last1, next1, sizeof(last1));
            memcpy(last2, next2, sizeof(last2));
        }

        // ---- 回答查询 ----
        for (int i = 1; i <= q; i++) {
            int r = query_r[i];
            int c = query_c[i];
            if (c < MAXV && reachable[r][c]) {
                cout << 1 << '\n';
            } else {
                cout << 0 << '\n';
            }
        }

    }

    return 0;
}

复杂度

设值域 $V = 200000$ ，序列总长 $L = \sum l_i \leqslant 2\times10^5$ ，最大轮数 $R = max\_r \leqslant 100$ ，查询数 $Q \leqslant 2\times10^5$ 。

按代码逐行拆解

读入： $O(L + Q)$ ，约 $4 \times 10^5$ 次。

初始化：

memset(last1):\ V\ \text{次 int 写} \\ memset(last2):\ V\ \text{次 int 写} \\ memset(reachable):\ R \times V\ \text{次 bool 写（约 21MB）}

合计 $O(R \times V)$ ，约 $2.1 \times 10^7$ 次写，仅在每组数据开始时执行一次。

每轮 DP（ $round = 1$ 到 $R$ ）：

代码行	操作	次数
$memset(next1)$	本轮状态清零	$V$ 次 int 写
$memset(next2)$	第二轮生产者清零	$V$ 次 int 写
扫描所有人序列	每位置的判断与更新	$L$ 次迭代
$memcpy(last1)$	轮末状态搬迁	$V$ 次 int 拷贝
$memcpy(last2)$	同	$V$ 次 int 拷贝

每轮 = $4V + \text{常数} \cdot L$ 。其中：

$4V$ 部分（ $memset \times 2 + memcpy \times 2$ ）约为 $8 \times 10^5$ 次连续 int 读写（≈ 3.2MB），靠 CPU SIMD + 缓存预取，常数极小；
$L$ 部分的序列扫描是真正耗时处：每个位置调一次 $can_start()$ ，再判断 $pos$ 是否落在 $[range_start, range_end]$ 中， $2\times10^5$ 个位置做 $100$ 轮约为 $2\times10^7$ 次迭代。这部分的内存访问模式是按人随机跳，cache miss 是主要瓶颈。

单轮复杂度： $O(V + L)$ ， $L$ 项占主导。

总 DP：

R \times O(V + L) = 100 \times O(4\times10^5) \approx 4\times10^7

来源	总操作量	特点
$memset/memcpy$ （next/last）	$4R \cdot V \approx 8\times10^7$ 次 int 读写	连续内存，SIMD 优化
序列扫描（逐位判定）	$R \cdot L \approx 2\times10^7$ 次迭代	主耗时，cache miss 高
$memset(reachable)$	一次性 $R \times V \approx 2.1\times10^7$ 字节	初始化，不在循环内

答查询： $O(Q)$ ，直接取 $reachable[r][c]$ 。

总时间

约 $4\times10^7$ 次核心迭代 + $2\times10^7$ 次初始化 memset，在 C++ 中约 0.2–0.4 秒。真正的瓶颈不是大块 memset，而是序列扫描的逐位置散跳内存访问。

总结

本题更像一道建模和实现题，不是特别优雅的推导题。真正要学的地方有两个：一是把相邻不同人的限制压成“每个值只保存两个上一轮接龙人”；二是把连续子序列的所有结尾压成扫描窗口，避免显式枚举所有边。理解这两点后，剩下就是把状态数组和窗口边界写稳。

P11230 [CSP-J 2024] 接龙

题目描述

在玩惯了成语接龙之后，小 J 和他的朋友们发明了一个新的接龙规则。

总共有 $n$ 个人参与这个接龙游戏，第 $i$ 个人会获得一个整数序列 $S_i$ 作为他的词库。

一次游戏分为若干轮，每一轮规则如下：

$n$ 个人中的某个人 $p$ 带着他的词库 $S_p$ 进行接龙。若这不是游戏的第一轮，那么这一轮进行接龙的人不能与上一轮相同，但可以与上上轮或更往前的轮相同。
接龙的人选择一个长度在 $[2, k]$ 的 $S_p$ 的连续子序列 $A$ 作为这一轮的接龙序列，其中 $k$ 是给定的常数。若这是游戏的第一轮，那么 $A$ 需要以元素 $1$ 开头，否则 $A$ 需要以上一轮的接龙序列的最后一个元素开头。
- 序列 $A$ 是序列 $S$ 的连续子序列当且仅当可以通过删除 $S$ 的开头和结尾的若干元素（可以不删除）得到 $A$ 。

为了强调合作，小 J 给了 $n$ 个参与游戏的人 $q$ 个任务，第 $j$ 个任务需要这 $n$ 个人进行一次游戏，在这次游戏里进行恰好 $r_j$ 轮接龙，且最后一轮的接龙序列的最后一个元素恰好为 $c_j$ 。为了保证任务的可行性，小 J 请来你判断这 $q$ 个任务是否可以完成的，即是否存在一个可能的游戏过程满足任务条件。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 $T$ ，表示数据组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行包含三个整数 $n, k, q$ ，分别表示参与游戏的人数、接龙序列长度上限以及任务个数。

接下来 $n$ 行：

第 $i$ 行包含 $(l_i + 1)$ 个整数 $l_i, S_{i,1}, S_{i,2}, \dots , S_{i,l_i}$ ，其中第一个整数 $l_i$ 表示序列 $S_i$ 的长度，接下来 $l_i$ 个整数描述序列 $S_i$ 。

接下来 $q$ 行：

第 $j$ 行包含两个整数 $r_j, c_j$ ，描述一个任务。

输出格式

对于每个任务：输出一行包含一个整数，若任务可以完成输出 1，否则输出 0。

输入输出样例 #1

输入 #1

text

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

输出 #1

text

说明/提示

【样例 1 解释】

在下文中，我们使用 $\{A_i\} = \{A_1, A_2, \dots , A_r\}$ 表示一轮游戏中所有的接龙序列， $\{p_i\} = \{p_1, p_2, \dots , p_r\}$ 表示对应的接龙的人的编号。由于所有字符均为一位数字，为了方便我们直接使用数字字符串表示序列。

对于第一组询问， $p_1 = 1$ 、 $A_1 = 12$ 是一个满足条件的游戏过程。
对于第二组询问，可以证明任务不可完成。注意 $p_1 = 1$ 、 $A_1 = 1234$ 不是合法的游戏过程，因为此时 $|A_1| = 4 > k$ 。
对于第三组询问， $\{p_i\} = \{2, 1\}$ 、 $\{A_i\} = \{12, 234\}$ 是一个满足条件的游戏过程。
对于第四组询问，可以证明任务不可完成。注意 $\{p_i\} = \{2, 1, 1\}、\{A_i\} = \{12, 23, 34\}$ 不是一个合法的游戏过程，因为尽管所有的接龙序列长度均不超过 $k$ ，但第二轮和第三轮由同一个人接龙，不符合要求。
对于第五组询问， $\{p_i\} = \{1, 2, 3, 1, 2, 3\}$ 、 $\{A_i\} = \{12, 25, 51, 12, 25, 516\}$ 是一个满足条件的游戏过程。
对于第六组询问，可以证明任务不可完成。注意每个接龙序列的长度必须大于等于 $2$ ，因此 $A_1 = 1$ 不是一个合法的游戏过程。
对于第七组询问，所有人的词库均不存在字符 $\tt 7$ ，因此任务显然不可完成。

【样例 2】

见选手目录下的 chain/chain2.in 与 chain/chain2.ans。

该样例满足测试点 1 的特殊性质。

【样例 3】

见选手目录下的 chain/chain3.in 与 chain/chain3.ans。

该样例满足测试点 2 的特殊性质。

【样例 4】

见选手目录下的 chain/chain4.in 与 chain/chain4.ans。

该样例满足特殊性质 A，其中前两组测试数据满足 $n \leq 1000$ 、 $r \leq 10$ 、单组测试数据内所有词库的长度和 $\leq 2000$ 、 $q \leq 1000$ 。

【样例 5】

见选手目录下的 chain/chain5.in 与 chain/chain5.ans。

该样例满足特殊性质 B，其中前两组测试数据满足 $n \leq 1000$ 、 $r \leq 10$ 、单组测试数据内所有词库的长度和 $\leq 2000$ 、 $q \leq 1000$ 。

【样例 6】

见选手目录下的 chain/chain6.in 与 chain/chain6.ans。

该样例满足特殊性质 C，其中前两组测试数据满足 $n \leq 1000$ 、 $r \leq 10$ 、单组测试数据内所有词库的长度和 $\leq 2000$ 、 $q \leq 1000$ 。

【数据范围】

对于所有测试数据，保证：

$1 \leq T \leq 5$ ；
$1 \leq n \leq 10^5$ ， $2 \leq k \leq 2 \times 10^5$ ， $1 \leq q \leq 10^5$ ；
$1 \leq l_i \leq 2 \times 10^5$ ， $1 \leq S_{i,j} \leq 2 \times 10^5$ ；
$1 \leq r_j \leq 10^2$ ， $1 \leq c_j \leq 2 \times 10^5$ ；
设 $\sum l$ 为单组测试数据内所有 $l_i$ 的和，则 $\sum l\leq 2\times 10^5$ 。

::cute-table{tuack}

测试点	$n\leq$	$r\leq$	$\sum l\leq$	$q\leq$	特殊性质
$1$	$10^3$	$1$	$2000$	$10^3$	无
$2,3$	$10$	$5$	$20$	$10^2$	^
$4,5$	$10^3$	$10$	$2000$	$10^3$	A
$6$	$10^5$	$10^2$	$2\times 10^5$	$10^5$	^
$7,8$	$10^3$	$10$	$2000$	$10^3$	B
$9,10$	$10^5$	$10^2$	$2\times 10^5$	$10^5$	^
$11,12$	$10^3$	$10$	$2000$	$10^3$	C
$13,14$	$10^5$	$10^2$	$2\times 10^5$	$10^5$	^
$15\sim 17$	$10^3$	$10$	$2000$	$10^3$	无
$18\sim 20$	$10^5$	$10^2$	$2\times 10^5$	$10^5$	^

特殊性质 A：保证 $k = 2 \times 10^5$ 。

特殊性质 B：保证 $k ≤ 5$ 。

特殊性质 C：保证在单组测试数据中，任意一个字符在词库中出现次数之和均不超过 $5$ 。