Ayoub is a coach of a team that contains $n$ players and Mahmoud is a coach of a team that contains $m$ players.
Every player in both teams has a unique strength between $1$ and $(n + m)$.
Ayoub is going to face Mahmoud in $m$ matches, in the $i_{th}$ match he will face the $i_{th}$ player in Mahmoud's team.
Ayoub wants to order his team in a way that maximizes the number of winning matches, but he should satisfy some rules.
In every match, the player with the higher strength will win.
You should help Ayoub and tell him what is the maximum number of matches he can win.
The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) ~--- the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers $n$ and $m$ $(2 \leq n \leq m \leq 2 \cdot 10 ^ {5})$~--- the number of players in Ayoub's team and the number of players in Mahmoud's team.
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq n + m)$, $a_i$ is equal to the strength of the $i_{th}$ player in Ayoub's team.
The third line of each test case contains $m$ integers $b_1, b_2, \ldots, b_m$ $(1 \leq b_i \leq n + m)$, $b_i$ is equal to the strength of the $i_{th}$ player in Mahmoud's team.
It is guaranteed that all values in both arrays $a$ and $b$ are distinct.
It is also guaranteed that the sum of $n + m$ over all test cases will not exceed $4 \cdot 10 ^ {5}$.
For every test case print the answer in the following format:
Print the maximum number of matches Ayoub's team can win in the first line.
On the second line print $m$ integers, the $i_{th}$ one should be equal to the index of the player from Ayoub's team that should play the $i_{th}$ match.
Make sure to satisfy the rules and that the number of winning matches is correct.
| Input | Output |
|---|---|
1 3 5 1 3 7 2 4 5 8 6 Copy
|
3 3 1 3 2 3 Copy
|
If the problem was without the first rule the solution will be like this:
Sort the players and take the 3 strongest players, then we can solve the problem using dp, dp[N][3], the N for the current match, and 3 for the player who played in the last match.
We don't need to use someone not from the strongest 3, because if the player of a specific match wasn't from top 3, and the player of the next and the previous match was from the top 3, we can replace the current player of third player from the top 3.
Now to solve this problem, we should sort the players and take all players except the strongest 3, start from the weakest one, for every player if he can win any match assign him to that match, otherwise mark him as a bad player.
Now do dp for non assigned matches with the top 3, like that, dp[N][3][2^3] which is dp[N][3][8], the last parameter is bitmask for every player in the top 3, if he played at least one winning match or not, every player who didn't play any winning match will be considered as a bad player.
We will try to dp 3 times, first time we will consider no player in the top 3 as a bad player (every one of them should player at least one winning match), second time we will only consider player 3 as a bad player, and the last time we will consider player 2 and 3 as a bad players.
Every time when we calculate the answer of the dp, we will minimise it with (n - bad players) and then maximise it with the answer.
#include <bits/stdc++.h>
using namespace std;
#define oo 1000000010
#define mod 1000000007
const int N = 200010;
int n , m , a[N] , b[N] , arr[N] , res = 0 , bad = 0 , ans[N] , frq[N] , cur;
pair<int,int> arr1[N] , arr2[N];
int dp[N][3][8] , nn , nnn;
int solve(int i,int last,int mask){
if(i == m)
return ((mask == (1 << nnn) - 1) ? 0 : -oo);
if(arr[i] != -1)
return (1 + solve(i + 1, last , mask));
if(dp[i][last][mask] != -1) return dp[i][last][mask];
dp[i][last][mask] = -oo;
for(int j = 0 ;j < nn;j++){
if(i && arr[i - 1] == -1 && j == last) continue;
if(j >= nnn)
dp[i][last][mask] = max(dp[i][last][mask] , solve(i + 1, j , mask));
else
dp[i][last][mask] = max(dp[i][last][mask] , (arr1[j].first > b[i]) + solve(i + 1, j , (mask | (arr1[j].first > b[i] ? (1 << j) : 0))));
}
return dp[i][last][mask];
}
void build_path(int i,int last,int mask){
if(i == m) return;
if(arr[i] != -1){
build_path(i + 1, last , mask);
return;
}
int cur = solve(i , last , mask);
for(int j = 0 ;j < nn;j++){
if(i && arr[i - 1] == -1 && j == last) continue;
if(j >= nnn){
if(cur == solve(i + 1, j , mask)){
ans[i] = arr1[j].second;
build_path(i + 1, j , mask);
return;
}
}
else{
if(cur == (arr1[j].first > b[i]) + solve(i + 1, j , (mask | (arr1[j].first > b[i] ? (1 << j) : 0)))){
ans[i] = arr1[j].second;
build_path(i + 1, j , (mask | (arr1[j].first > b[i] ? (1 << j) : 0)));
return;
}
}
}
}
void solve(){
scanf("%d%d",&n,&m);
res = bad = cur = nn = nnn = 0;
for(int i = 0 ;i < n;i++){
scanf("%d",&a[i]);
arr1[i] = make_pair(a[i] , i);
frq[i] = 0;
}
for(int i = 0 ;i < m;i++){
scanf("%d",&b[i]);
arr2[i] = make_pair(b[i] , i);
arr[i] = -1;
}
sort(arr1,arr1+n);
sort(arr2,arr2+m);
for(int i = 0 , j = 0;i < n - 3 && j < m;i++){
if(arr1[i].first > arr2[j].first)
res++ , arr[arr2[j].second] = arr1[i].second , j++;
else
bad++;
}
for(int i = 0 ;i < m;i++) ans[i] = arr[i];
reverse(arr1,arr1+n);
nn = min(n , 3);
bad += nn;
for(int i = 0 ;i < 3;i++){
bad--;
nnn++;
for(int j = 0 ;j < m;j++) for(int k = 0 ;k < 3;k++) for(int l = 0 ;l < 8;l++) dp[j][k][l] = -1;
cur = solve(0 , 0 , 0);
cur = min(cur , m - bad);
if(cur > res){
res = cur;
build_path(0 , 0 , 0);
}
}
for(int i = 0 ;i < m;i++)
if(ans[i] != -1) frq[ans[i]]++;
for(int i = 0 , j = 0 ;i < n;i++){
if(frq[i] > 0) continue;
while(j < m && (ans[j] != -1 && (frq[ans[j]] == 1 || a[ans[j]] > b[j]))) j++;
if(j == m) break;
frq[i]++;
if(ans[j] != -1) frq[ans[j]]--;
ans[j] = i;
}
for(int i = 0 , j = 0 ;i < n;i++){
if(frq[i] != 0) continue;
while(j < m && (ans[j] != -1 && frq[ans[j]] == 1)) j++;
if(j == m) break;
frq[i]++;
if(ans[j] != -1) frq[ans[j]]--;
ans[j] = i;
}
for(int i = 0 ;i < m;i++){
if(ans[i] == -1){
ans[i] = 0;
while((i > 0 && ans[i] == ans[i - 1]) || (i < m - 1 && ans[i] == ans[i + 1])) ans[i]++;
}
}
printf("%d\n",res);
for(int i = 0 ;i < m;i++){
if(i) putchar(' ');
printf("%d",ans[i] + 1);
}
puts("");
}
int main(){
int t;
scanf("%d",&t);
while(t--){
solve();
}
return 0;
}