P16321 [语言月赛 202604] 生日邀请 (Hard ver.)

本题和 Easy ver. 只有数据范围的区别。 本题的[常规版](https://www.luogu.com.cn/problem/B4528)在入门题库。

Alice 快要过生日了，她邀请了很多位好朋友参加她的生日宴会。所有朋友的名字长度均仅由大小写字母构成。 然而她的朋友们都很忙，不确定能否参加，无法给她一个明确的答复。她收到的回复可分为下面三类（其中 $A,B$ 为任意人名）： - `A=>B`：如果 $A$ 参加，那么 $B$ 也参加。 - `ABob

输入的第一行有一个字符串 $s$，表示所有朋友的回复形成的字符串。 第二行有一个正整数 $q$，表示问题的个数。 之后 $q$ 行，每行有两个人名 $u,v$，表示一个问题。

对于每个问题，输出一行一个字符串：“如果 $u$ 参加，那么 $v$ 一定参加”若成立，输出 `Yes`，否则输出 `No`。

【样例 1 解释】 对于每个询问我们依次解释： - 根据 `Andrea=>Bob`，如果 Andrea 参加，那么 Bob 参加。 - 根据 `CindyDora`，如果 Dora 参加，那么 Cindy 参加。 - 如果 Dora 参加，那么 Cindy 会参加，而这也就意味着 Bob 会参加，因此，如果 Dora 参加，那么 Bob 参加。 - 对于第 $4$ 组询问，可以构造“仅 Andrea, Bob 参加”的反例，因此，如果 Andrea 参加，则 Cindy 不一定参加。 - 对于第 $5,6$ 组询问，由于我们不知道关于 Mike 的任何回复，显然答案是不一定。 - 但是第 $7$ 组询问不一样——“如果 Mike 参加，那么 Mike 一定参加了”是一句废话，这是永远成立的。 【数据范围】 对于全部数据，保证： - $s$ 由不重复人名组成，人名之间的间隔必为 `` 和 `` 之一。 - 每个人名仅由英文字母组成，首字母大写，其他字母小写，并且这些人名都不是 `Alice`。 - $|s|\le 3\times 10^6$，所有询问中出现的人名长度和 $\le 3\times 10^6$。