4182: 字符串问题
[Creator : ]
Description
Yazid 和 Tiffany 喜欢字符串问题。在这里，我们将给你介绍一些关于字符串的基本概念。
对于一个字符串 SS，我们定义 |S||S|表示 SS 的长度。
接着，我们定义该串的子串 S(L,R)S(L,R)表示由 SS 中从左往右数，第 LL 个字符到第 RR 个字符依次连接形成的字符串，特别地，如果 L<1L<1 或 R>|S|R>|S|或 L>RL>R，则 S(L,R)S(L,R) 表示空串。
我们说两个字符串相等，当且仅当它们的长度相等，且从左至右各位上的字符依次相同。
我们说一个字符串 TT 是 SS 的前缀，当且仅当 S(1,|T|)=TS(1,|T|)=T。
两个字符串 SS,TT 相加 S+TS+T 表示的是在 SS后紧挨着写下 TT 得到的长度为|S|+|T||S|+|T|的字符串。
Input
第 1 行一个只包含小写字母的字符串 SS。
第 2 行一个非负整数nana，表示 A 类串的数目。接下来nana 行，每行 2 个用空格 隔开的整数。
– 这部分中第ii 行的两个数分别为lailai,rairai，描述第 ii 个 A 类串。
– 保证 1≤lai≤rai≤|S|1≤lai≤rai≤|S|。
接下来一行一个非负整数 nbnb，表示 B 类串的数目。接下来 nbnb 行，每行 2 个用空格隔开的整数。
– 这部分中第 ii行的两个数分别为lbilbi,rbirbi，描述第ii个 B 类串。
– 保证1≤lbi≤rbi≤|S|1≤lbi≤rbi≤|S|。
接下来一行一个非负整数 m，表示支配关系的组数。接下来 m 行，每行 2 个用空格隔开的整数。
– 这部分中每行的两个整数 xx,yy，描述一对(x，y)(x，y)的支配关系，具体意义见 【题目描述】。
– 保证 1≤x≤na1≤x≤na，1≤y≤nb1≤y≤nb。保证所有支配关系两两不同，即不存在两组支 配关系的 xx,yy 均相同。
第 2 行一个非负整数nana，表示 A 类串的数目。接下来nana 行，每行 2 个用空格 隔开的整数。
– 这部分中第ii 行的两个数分别为lailai,rairai，描述第 ii 个 A 类串。
– 保证 1≤lai≤rai≤|S|1≤lai≤rai≤|S|。
接下来一行一个非负整数 nbnb，表示 B 类串的数目。接下来 nbnb 行，每行 2 个用空格隔开的整数。
– 这部分中第 ii行的两个数分别为lbilbi,rbirbi，描述第ii个 B 类串。
– 保证1≤lbi≤rbi≤|S|1≤lbi≤rbi≤|S|。
接下来一行一个非负整数 m，表示支配关系的组数。接下来 m 行，每行 2 个用空格隔开的整数。
– 这部分中每行的两个整数 xx,yy，描述一对(x，y)(x，y)的支配关系，具体意义见 【题目描述】。
– 保证 1≤x≤na1≤x≤na，1≤y≤nb1≤y≤nb。保证所有支配关系两两不同，即不存在两组支 配关系的 xx,yy 均相同。
Output
一行一个整数表示最大串长。特别地，如果满足限制的串可以是无限长的，则请 输出 −1。
Sample 1 Input
3
abaaaba
2
4 7
1 3
1
3 4
1
2 1
abaaaba
2
4 7
1 3
1
7 7
1
2 1
abbaabbaab
4
1 5
4 7
6 9
8 10
3
1 6
10 10
4 6
5
1 2
1 3
2 1
3 3
4 1
Sample 1 Output
7
-1
13