NOI '22 Multi-Provincial Team Selection P3 - Community

View as PDF

Submit solution

Points: 40 (partial)
Time limit: 1.5s
Memory limit: 512M

Problem type

Tommy discovers the relics of m messages [X_1, X_2, \dots, X_m] corresponding to n clowns participating in a forum thread. A message X_i can be described by three strings X_{i\ 1}, X_{i\ 2}, X_{i\ 3}. Tommy will reorder the m messages into some sequence [Y_1, Y_2, \dots, Y_m]. A message Y_i is good if and only if either

  • i \ne m, Y_{i\ 3} = \texttt{`loushang'} and Y_{i\ 2} = Y_{i+1\ 1}
  • i \ne 1, Y_{i\ 3} = \texttt{`louxia'} and Y_{i\ 2} = Y_{i-1\ 1}

Find any ordering of the m given messages that maximizes the number of good messages.

Let S = \{X_{i\ 1} : 1 \le i \le m\}. The test data guarantees that |S| = n and that for any X_{i\ 1}, there exists j such that X_{j\ 1} = X_{i\ 1} and X_{j\ 3} \notin \{\texttt{`loushang'}, \texttt{`louxia'}\}.

Constraints

The input consists of T \le 100 individual test cases.

For each test case, 1 \le n \le m \le 77\,777.

Over all test cases, \sum m \le 2.5 \times 10^5.

The length of any token of input will not exceed 12 ASCII characters.

50\% of points will be granted for finding the maximum number of good messages but failing to find a valid ordering.

T \le M \le \sum M \le Test Prop. A Prop. B Prop. C
5 10 50 1 / / /
10 16 160 2 / / /
30 2\,222 15\,000 3, 4 Y Y Y
30 2\,222 15\,000 5, 6 Y / Y
30 2\,222 15\,000 7, 8, 9 / Y Y
30 2\,222 15\,000 10, 11 / / Y
30 2\,222 15\,000 12, 13 / / /
100 77\,777 2.5 \times 10^5 14, 15 Y Y Y
100 77\,777 2.5 \times 10^5 16 Y / Y
100 77\,777 2.5 \times 10^5 17, 18, 19 / Y Y
100 77\,777 2.5 \times 10^5 20, 21, 22 / / Y
100 77\,777 2.5 \times 10^5 23, 24, 25 / / /

Property A: There is no i where X_{i\ 3} = \texttt{`loushang'} and X_{i\ 2} \in S.

Property B: There exists an ordering such that all i where X_{i\ 3} \in \{\texttt{`loushang'}, \texttt{`louxia'}\} and X_{i\ 2} \in S, are good messages.

Property C: There exists no pair 1 \le i, j \le m where X_{i\ 1} = X_{j\ 2}, X_{i\ 2} = X_{j\ 1}, X_{i\ 3} = \texttt{`loushang'}, and X_{j\ 3} = \texttt{`louxia'}.

Input Specification

The first line contains a positive integer T, the number of test cases. For each test case:

The first line contains two positive integers n and m, the number of clowns and the number of messages, respectively.

The following n lines contain the names of the clowns.

The following m lines contain three strings X_{i\ 1}, X_{i\ 2}, and X_{i\ 3}, describing message X_i.

Output Specification

For each test case:

On the first line output an integer, corresponding to the maximum number of good messages.

On the second line output m distinct integers a_1, a_2, \dots, a_m from 1 to m, corresponding to an ordering of the messages, i.e. Y_i = X_{a_i}.

Sample Input

2
4 15
builtin_clz
builtin_ctz
jinkela
OrzTourist
builtin_clz MengXin QiuZhu
builtin_ctz builtin_clz louxia
jinkela builtin_ctz louxia
builtin_ctz builtin_clz loushang
builtin_clz BieMoZheng YaoXueShu
OrzTourist builtin_clz louxia
OrzTourist OrzTourist louxia
builtin_clz Iam Angry!
builtin_clz builtin_clz loushang
builtin_clz builtin_clz louxia
builtin_clz builtin_clz loushang
builtin_clz builtin_clz louxia
builtin_ctz Xue Shu
jinkela Xue Shu
OrzTourist Xue Shu
1 9
builtin_clz
builtin_clz builtin_clz loushang
builtin_clz builtin_clz loushang
builtin_clz builtin_clz louxia
builtin_clz builtin_clz Loushang
builtin_clz builtin_clz LOUSHANG
builtin_clz Builtin_clz loushang
builtin_clz loushang louxia
builtin_clz builtin_clz builtin_clz
builtin_clz loushang builtin_clz

Sample Output

9
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
3
8 1 2 7 9 3 6 4 5

Attachments


Comments

There are no comments at the moment.