B. BaCoder Testing Procedure
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

After founding his competitive programming company BaCoder, baluteshih saw rapid business growth and soon expanded into various services. One of the most important services offered is problem setting for programming contests — especially for clients who want to host a contest but lack the ability to write good problems themselves.

This job isn't easy. Besides ensuring that the problems are interesting and meet the client's desired difficulty, every detail must be carefully checked. To guarantee quality, BaCoder has a strict internal problem verification workflow. For a contest with $$$N$$$ problems, each problem has:

  • One setter responsible for preparing everything (e.g., test data, checker, editorial),
  • Two testers who review the setter's work and provide suggestions. One is designated the primary tester, and the other the secondary tester.

When assigning roles, suppose there are $$$M$$$ people participating in this contest preparation, labeled from $$$1$$$ to $$$M$$$. First, the setter for each problem is decided. Then, if someone is the setter for $$$x$$$ problems, they must also serve as the primary tester for $$$x$$$ problems and secondary tester for another $$$x$$$ problems.

Assigning testers is tricky — doing it manually often leads to mistakes like assigning the same person as both testers, or assigning the setter to test their own problem. baluteshih finds this frustrating. To improve efficiency, he asks you to write a program that assigns testers such that:

  • For each problem, the setter and the two testers are three distinct individuals,
  • The tester assignment satisfies the workload requirements described above.
Input

The first line contains an integer $$$T$$$, the number of test cases.

For each test case, the first line contains two integers $$$N$$$ and $$$M$$$: the number of problems and the number of participants.

The second line contains $$$N$$$ integers $$$s_1, s_2, \dots, s_N$$$, where $$$s_i$$$ is the ID of the setter for the $$$i$$$-th problem.

  • $$$1 \leq T \leq 10^5$$$
  • $$$1 \leq M \leq N \leq 10^6$$$
  • $$$1 \leq s_i \leq M$$$
  • It is guaranteed that each of the $$$M$$$ people is the setter for at least one problem.
  • It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$10^6$$$.
Output

For each test case, if no valid tester assignment exists, output a single line containing No.

Otherwise, output three lines:

  • The first line should be Yes.
  • The second line should contain $$$N$$$ integers $$$t_{1,1}, t_{1,2}, \dots, t_{1,N}$$$, where $$$t_{1,i}$$$ is the primary tester for the $$$i$$$-th problem.
  • The third line should contain $$$N$$$ integers $$$t_{2,1}, t_{2,2}, \dots, t_{2,N}$$$, where $$$t_{2,i}$$$ is the secondary tester for the $$$i$$$-th problem.

Your output will be considered correct if it satisfies all of the following conditions:

  • $$$1 \leq t_{1,i}, t_{2,i} \leq M$$$ for all $$$i$$$.
  • For each person $$$y$$$ ($$$1 \leq y \leq M$$$), if $$$y$$$ is the setter for exactly $$$x$$$ problems, then $$$y$$$ must also appear exactly $$$x$$$ times as a primary tester and exactly $$$x$$$ times as a secondary tester.
  • For every problem $$$i$$$, the three people $$$s_i$$$, $$$t_{1,i}$$$, and $$$t_{2,i}$$$ must be distinct.
Example
Input
4
5 5
1 2 3 4 5
6 3
1 1 2 2 3 3
10 5
3 1 4 1 5 2 4 5 3 1
3 1
1 1 1
Output
Yes
2 3 4 5 1
3 4 5 1 2
Yes
2 2 3 3 1 1
3 3 1 1 2 2
Yes
4 3 5 3 1 1 2 1 5 4
2 4 1 5 4 3 1 3 1 5
No