P16321 [Language Monthly Contest 202604] Birthday Invitation (Hard ver.)

This problem differs from the Easy ver. only in the constraints. The [regular version](https://www.luogu.com.cn/problem/B4528) of this problem is in the beginner problem set.

Alice’s birthday is coming soon, and she invited many good friends to her birthday party. All friends’ names consist only of uppercase and lowercase letters. However, her friends are all busy and are not sure whether they can attend, so they cannot give her a clear answer. The replies she receives can be divided into the following three types (where $A, B$ are any names): - `A=>B`: If $A$ attends, then $B$ also attends. - `ABob

The first line contains a string $s$, representing the string formed by all friends’ replies. The second line contains a positive integer $q$, representing the number of queries. The next $q$ lines each contain two names $u, v$, representing one query.

For each query, output one line with a string: if “if $u$ attends, then $v$ must attend” is true, output `Yes`; otherwise output `No`.

[Sample 1 Explanation] We explain each query in order: - From `Andrea=>Bob`, if Andrea attends, then Bob attends. - From `CindyDora`, if Dora attends, then Cindy attends. - If Dora attends, then Cindy will attend, which also means Bob will attend. Therefore, if Dora attends, then Bob attends. - For the $4$-th query, we can construct a counterexample where “only Andrea and Bob attend”. Therefore, if Andrea attends, Cindy does not necessarily attend. - For the $5$-th and $6$-th queries, since we do not know any reply about Mike, the answer is clearly not guaranteed. - But the $7$-th query is different: “if Mike attends, then Mike must attend” is a meaningless statement, and it is always true. [Constraints] For all testdata, it is guaranteed that: - $s$ consists of non-repeated names, and the separator between names must be one of ``, and ``. - Each name consists only of English letters, with the first letter uppercase and the other letters lowercase, and none of these names is `Alice`. - $|s|\le 3\times 10^6$, and the sum of name lengths appearing in all queries is $\le 3\times 10^6$. Translated by ChatGPT 5