P8291 [NOI Qualifier Joint Exam 2022] Academic Community

**A warm reminder from Xiao I: There is a formal problem statement in the description, so you may skip the background. Also, please read all content except the background carefully before solving.** Xiao I is an OI contestant. But rather than saying Xiao I likes OI, it is better to say Xiao I likes the fun feature on the OJ he uses most often—FCCOJ—called the Academic Community. Although it is called an academic community, what Xiao I and other users can talk about is far more than academics. Every day, many posts appear in the academic community that catch Xiao I’s attention. Today, while browsing the community, Xiao I found a post like this: > `builtin_clz`: Newbie asking for help. For this Academic Community problem, it gets AC locally but RE after submission. > > `builtin_ctz`: Below `builtin_clz`. > > `jinkela`: Below `builtin_ctz`. > > `builtin_ctz`: Above `builtin_clz`. > > `builtin_clz`: Can you stop being weird? Please answer the question seriously. > > `OrzTourist`: Below `builtin_clz`. > > `OrzTourist`: Below `OrzTourist`. > > `builtin_clz`: Why is nobody answering? I’m angry! > > `builtin_clz`: Above `builtin_clz`. > > `builtin_clz`: Below `builtin_clz`. > > `builtin_clz`: Above `builtin_clz`. > > `builtin_clz`: Below `builtin_clz`. > > …… Although the user named `builtin_clz` got angry because nobody answered his academic question, this funny way of speaking amused Xiao I for a long time. This shows that people’s joys and sorrows are not connected. But when Xiao I refreshed the page to continue reading the replies, he found that the community admin had deleted the post because it contained too much spam. To restore this interesting post, Xiao I dug through the web cache for a long time and recovered every message in the post. However, for mysterious reasons, the order of the messages was shuffled, and the cache did not contain the sending time of each message, so Xiao I had no way to restore the original order. Following the spirit of “when you meet difficulties, go to sleep,” Xiao I decided to arrange the messages in any order. But since he is fascinated by the “`XXX` above” and “`XXX` below” style, he still hopes that after reordering, as many messages of this style as possible will match the real situation of the post. However, Xiao I is an OI contestant who only knows how to spam the community and cannot solve problems, so he asks you for help. Of course, Xiao I knows that giving you the raw original messages directly is inconvenient, so he standardized the messages. See the formal statement in the description. **Also, due to special rules of the academic community, the messages in the post satisfy certain special constraints. See the end of the description.**

**All string equality checks in this problem are case-sensitive. For example, `1oushang`, `Loushang`, and `LOUSHANG` are all different strings.** Xiao I is organizing a post in the academic community. There are $N$ users who have posted messages, with usernames $n_1, n_2, \ldots, n_N$. There are $M$ messages in total. For the $i$-th message, we describe it by a triple of strings $(s_{i,1}, s_{i,2}, s_{i,3})$, where $s_{i,1}$ is the username of the sender, and $s_{i,2}$ and $s_{i,3}$ describe the message content. For the $i$-th message, we define whether it is a **“below-type message”**, an **“above-type message”**, or an **academic message** as follows: - If $s_{i,3}$ is `louxia`, and $s_{i,2}$ is exactly equal to some given username (note that $s_{i,2} = s_{i,1}$ is allowed), then this message is called a **below-type message**, and $s_{i,2}$ is the user mentioned by the message. - If $s_{i,3}$ is `loushang`, and $s_{i,2}$ is exactly equal to some given username (note that $s_{i,2} = s_{i,1}$ is allowed), then this message is called an **above-type message**, and $s_{i,2}$ is the user mentioned by the message. - If neither of the above two conditions is satisfied, then this message is an **academic message**. A reordering of all messages is defined as a permutation $a_1, a_2, a_3, \ldots, a_M$ of $1$ to $M$, meaning that the first message is $(s_{a_1,1}, s_{a_1,2}, s_{a_1,3})$, the second message is $(s_{a_2,1}, s_{a_2,2}, s_{a_2,3})$, and so on. For the $i$-th message $(s_{a_i,1}, s_{a_i,2}, s_{a_i,3})$ in a reordering $a_1, a_2, a_3, \ldots, a_M$ (where $1 \le i \le M$), we define whether it is **consistent with the real situation** as follows: - If this message is a **below-type message**, then it is **consistent with the real situation** if and only if $i \ne 1$ and $s_{a_{i - 1}, 1} = s_{a_i, 2}$, i.e., the previous message exists and its sender is exactly the user mentioned by this message. - If this message is an **above-type message**, then it is **consistent with the real situation** if and only if $i \ne M$ and $s_{a_{i + 1}, 1} = s_{a_i, 2}$, i.e., the next message exists and its sender is exactly the user mentioned by this message. - If this message is an **academic message**, then no matter what, it is never consistent with the real situation, because Xiao I only wants to spam and does not want academics. Under the above definitions, Xiao I wants to find a reordering that maximizes the number of messages consistent with the real situation. You need to help him find such a reordering and the maximum number of consistent messages. **To make it easier for you to solve, Xiao I also tells you a special constraint of the post: because the academic community will mute people who only spam and never do academics, in the post given by Xiao I, every person who has posted in the thread must have sent at least one academic message.**

**This problem has multiple test cases.** The first line contains an integer $T$ denoting the number of test cases, followed by $T$ test cases. For each test case, the first line contains two integers $N, M$, denoting the number of users who have posted in the thread and the number of messages in the thread, respectively. The next $N$ lines each contain a string $n$, the username of a user who has posted in the thread. It is guaranteed that within each test case, the $N$ usernames are pairwise distinct. The next $M$ lines each contain three strings $s_1, s_2, s_3$ describing a message. Adjacent strings are separated by one space. Here, $s_1$ must be equal to one of the usernames in the input. All input strings consist only of uppercase and lowercase English letters, underscore (`_`), question mark (`?`), exclamation mark (`!`), and period (`.`), and have length at most $12$. For each test case, it is guaranteed that each of the $N$ usernames has sent at least one message, **and has sent at least one academic message**. In the same test case, multiple messages may have exactly the same content; in this case, they should be treated as **multiple** messages.

For each test case, output two lines. The first line outputs a non-negative integer, the maximum number of messages that are consistent with the real situation among all reorderings. The second line outputs $M$ integers $a_1, a_2, \ldots, a_m$, representing a reordering that achieves the maximum number of consistent messages. If there are multiple valid reorderings, **output any one of them**.

**[Sample Explanation #1]** The first test case is basically the same as the example given in the background. The difference is that, to satisfy the requirement that everyone sends at least one academic message, there are a few extra academic messages at the end of this test case. In the second test case, the first two input messages are above-type messages, the third message is a below-type message, and the other messages are academic messages. **[Sample #3]** See `community/community3.in` and `community/community3.ans` in the attachment. This sample satisfies special property A, special property B, and special property C in the constraints. **[Sample #4]** See `community/community4.in` and `community/community4.ans` in the attachment. This sample satisfies special property C in the constraints. **[Constraints]** Let $\sum M$ be the sum of $M$ over all test cases in a single test point. For all test points, $1 \le T \le 100$, $1 \le N \le M \le 77777$, $1 \le \sum M \le 2.5 \times {10}^5$. | $T \le$ | $M \le$ | $\sum M \le$ | Test point ID | Special property A | Special property B | Special property C | |:-:|:-:|:-:|:-:|:-:|:-:|:-:| | $5$ | $10$ | $50$ | $1$ | None | None | None | | $10$ | $16$ | $160$ | $2$ | None | None | None | | $30$ | $2222$ | $15000$ | $3 \sim 4$ | Yes | Yes | Yes | | $30$ | $2222$ | $15000$ | $5 \sim 6$ | Yes | No | Yes | | $30$ | $2222$ | $15000$ | $7 \sim 9$ | No | Yes | Yes | | $30$ | $2222$ | $15000$ | $10 \sim 11$ | No | No | Yes | | $30$ | $2222$ | $15000$ | $12 \sim 13$ | No | No | None | | $100$ | $77777$ | $2.5 \times {10}^5$ | $14 \sim 15$ | Yes | Yes | Yes | | $100$ | $77777$ | $2.5 \times {10}^5$ | $16$ | Yes | No | Yes | | $100$ | $77777$ | $2.5 \times {10}^5$ | $17 \sim 19$ | No | Yes | Yes | | $100$ | $77777$ | $2.5 \times {10}^5$ | $20 \sim 22$ | No | No | Yes | | $100$ | $77777$ | $2.5 \times {10}^5$ | $23 \sim 25$ | No | No | None | **Note: For easier reading, the test point ID is in the fourth column of the table.** Special property A: There are no above-type messages. **Note: This does not mean that $\bm{s_3}$ is not equal to `loushang`.** Special property B: For each test case, there exists a reordering such that every above-type message and below-type message is consistent with the real situation. Special property C: For each test case, if there exists a message $s_1$ $s_2$ `loushang`, where $s_1, s_2$ are arbitrary strings, then in this test case there must not exist a message $s_2$ $s_1$ `louxia`. **[Scoring]** If, for a test point, the number of messages consistent with the real situation is correct for all test cases, you will get $50 \%$ of the score for that test point. On this basis, if, for a test point, the reordering is also correct for all test cases, you will get the full score for that test point. Note that **if you only want to get $\bm{50 \%}$ of the score, you must still output a permutation of $\bm{1}$ to $\bm{M}$ on the second line for each test case, otherwise your actual score may differ from your expected score**. **[Reminder]** Because this may be important to you, Xiao I emphasizes again: **because the academic community will mute people who only spam and never do academics, in the post given by Xiao I, every person who has posted in the thread must have sent at least one academic message**. The input size of this problem is large. Please use a relatively fast input method. Translated by ChatGPT 5