All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
It's final exam week of Chef's cooking class. His class of N students are busy studying for it. Unfortunately, being crammers, each student is only able to study one topic. The i-th student studied topic Si. Topics are numbered 1 to 106.
Chef prepared N tasks for exam. He intends to assign each task to exactly one student. Each task requires exactly one topic to pass. The j-th task requires topic Tj.
Chef is a sadistic teacher, he doesn't want the students to pass! Therefore he wants to assign the tasks in such that the number of students assigned to the topic he/she studied for is minimized. Can you please help Chef in finding any such assignment?
If there are multiple possible assignments, you may output any one.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N.
The second line contains N space-separated integers S1, S2, ..., SN.
The third line contains N space-separated integers T1, T2, ..., TN.
For each test case, output two lines.
The first line should contain a single integer denoting the minimum number of students assigned to the topic he/she studied for, i.e. number of students who passed the exam.
The second line should describes assignment. It should contain N space separated integers - a1, a2, ..., aN, meaning the i-th student is assigned to the ai-th task.
- 1 ≤ T ≤ 105
- 1 ≤ N ≤ 103
- The sum of the Ns in a single test file is ≤ 3×105
- 1 ≤ Si ≤ 106
- 1 ≤ Tj ≤ 106
Input: 2 4 100 200 300 400 200 200 300 400 3 100 100 200 100 100 200 Output: 0 2 3 4 1 1 2 3 1
Example case 1. Here, there exists an assignment where no student is assigned to the topic he/she studied for:
- Student 1 gets task 2,
- Student 2 gets task 3,
- Student 3 gets task 4,
- Student 4 gets task 1.
Example case 2. In this test case, there's no way we can avoid at least one student from being assigned the topic he/she studied for. But the sample output shows that the minimum in this case is 1:
- Student 1 gets task 2 (and thus gets the topic he/she studied for),
- Student 2 gets task 3,
- Student 3 gets task 1.
|Tags||easy, greedy, kevinsogo, snckpb16|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.