← 返回题目列表

Codeforces · 868/D

D. 巨大的字符串

中文机器翻译题面 查看原题

给定 n 个字符串 s1, s2, ..., sn,由字符 0 和 1 组成。执行 m 次操作,在每个操作上将两个现有字符串连接成一个新字符串。在第 i 次操作中,串联 saisbi 被保存到新字符串 sn + i 中(操作从 1 开始编号)。每次操作后,您需要找到最大正整数 k,使得所有可能的由 0 和 1 组成、长度为 k 的字符串(有 2k 个这样的字符串)都是新字符串的子字符串。如果没有这样的k,则打印0。

输入

第一行包含单个整数 n (1 ≤ n ≤ 100) — 字符串的数量。接下来的 n 行包含字符串 s1, s2, ..., sn (1 ≤ |si| ≤ 100),每行一个。字符串总长度不大于100。

下一行包含单个整数 m (1 ≤ m ≤ 100) — 操作数。接下来是 m 行,每行包含两个整数 ai abd bi (1 ≤ ai, bi ≤ n + i - 1) - 连接形成 sn + i 的字符串数量。

输出

打印 m 行,每行应包含一个整数 - 相应操作后问题的答案。

示例

输入 #1

5
01
10
101
11111
0
3
1 2
6 5
4 4

输出 #1

1
2
0

注意

在第一次操作中,创建一个新字符串“0110”。对于 k = 1,长度为 k 的两个可能的二进制字符串是“0”和“1”,它们是新字符串的子串。对于 k = 2 及更大,存在长度为 k 的字符串未出现在该字符串中(对于 k = 2,该字符串为“00”)。所以答案是1。

在第二次操作中,创建字符串“01100”。现在所有长度为 k = 2 的字符串都存在。

在第三次操作中,创建字符串“1111111111”。没有零,所以答案是0。