Baidu Star Preliminary 2--Degree Bear and Arrangement--Binary Match

Degree Bear and Arrangement

Accepts: 1100

Submissions: 3486

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Problem Description

Duxiong has a machine that has a 1_M1 \sim M1_M queue p[1..M]p[1..M]p[1..M] as a parameter. If a string of length MMM is dropped, the machine rearranges the string and outputs it again by changing the character at the original location of I I I I to p[i]p[i]p[i]p[i]Location.

For example, when M=3M=3M=3, p[1]=3,p[2]=1,p[3]=2p[1]=3,p[2]=1,p[3]=2p[1]=3,p[2]=1,p[3]=2, the machine will output "bca" when "abc" is discarded into the machine; if "ded" is discarded, the machine will output "edd".

One day, Duxiong accidentally forgot the parameters of this machine. He only remembered that the length of the parameters was MMM, so he threw in a string with NNN length of MMM and recorded the output results for each string machine. Based on these results, you can help Duxiong find the parameters of this machine.If multiple sets of parameters satisfy the record of a degree bear, output the lowest rank in dictionary order as a parameter.If there is no record of parameter satisfaction bears, output 1-1_1.

Note: For two distinct permutations a: a[1..M]a[1..M]a[1..M] and b[1..M]b[1..M]b[1..M], we call a a a smaller than B B B if and only if there is an I I i, which satisfies that for all jjj s less than I I I there is a j=b J a_j = b_j a J =b J and a i<b I a_i < b_i a_i <b.i.

Input

There are multiple sets of queries, and the first line contains a positive integer TTT representing several sets of queries.

The first line of each group of queries contains two positive integers, N, MN, M, representing the number of strings that the bear dropped into the machine and the length of the parameter, respectively.Next, there are 2 x N2 \times N2 x N lines, each with a string length of MMM, in which the string representation of line 2 x i_12 \times i - 12 x i_1 is dropped into the machine's I I I string, whereas the string of line 2 x i2 \times i2 x I represents the machine's output for the I I I string.

  • 1≤T≤1001 \le T \le 1001≤T≤100

  • 1≤N≤201 \le N \le 201≤N≤20

  • 1≤M≤501 \le M \le 501≤M≤50

  • Strings consist of lower case letters ('a'to'z')

Output

For each query, output a line containing only one integer 1-1_1, unless there is no record of parameter satisfaction bears.Otherwise, this line contains an arrangement representing the one with the smallest dictionary order of all possible parameters for this machine.

Sample Input

Copy

4
1 3
abc
bca
2 4
aaab
baaa
cdcc
cccd
3 3
aaa
aaa
bbb
bbb
ccc
ccc
1 1
a
z

Sample Output

Copy

3 1 2
2 4 3 1
1 2 3
-1

Note
 In the first set of questions, p[1]=3,p[2]=1,p[3]=2p[1]=3,p[2]=1,p[3]=2p[1]=3,p[2]=1,p[3]=2 are the only possible machine parameters.

P=[2,4,4,4,3,3,3,1]p=[2,4,4,4,3,3,3,3,3,1]p=[2,4,4,2,2,1]p=[3,4,4,4,2,1]p=[3,4,4,2,2,1][3,4,4,3,3,1][2,4,4,3,3,3,1][2,4,4,4,3,3,3,3,3,1]p=[p=[p=[2,4,4,4,4,4,4,2,3,3,3,3,3]p=[p=[2,4,4,4,4,3,4,3,4,3,4,3 The result is that 

Is the bipartite matching.If the current if(ch1[j]==ch2[k]) num[j][k]++; if num[j][k] is n, add an edge and run a binary match.

Note that you write from the back to the front so that the dictionary order is minimal.

#Include <algorithm>//STL general algorithm
#Include <bitset> //STL BitSet container
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#Include <complex> //plural class
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#Include <deque> //STL double-ended queue container
#Include <exception>//exception handling class
#include <fstream>
#Include <function>//STL Defines an Operating Function (instead of an Operator)
#include <limits>
#Include <list> //STL Linear List Container
#Include <map> //STL mapping container
#include <iomanip>
#Include <ios> //basic input/output support
#Include <iosfwd> //Pre-declarations used by input/output systems
#include <iostream>
#Include <istream> //basic input stream
#Include <ostream> //basic output stream
#Include <queue> //STL queue container
#Include <set> //STL collection container
#Include <sstream> //String-based streams
#Include <stack> //STL Stack Container
#Include <stdexcept>//Standard exception class
#Include <streambuf>//underlying input/output support
#Include <string> //string class
#Include <utility> //STL generic template class
#Include <vector> //STL dynamic array container
#include <cwchar>
#include <cwctype>
#define ll long long
using namespace std;
//priority_queue<int,vector<int>,less<int> >q;
int dx[]= {-1,1,0,0,-1,-1,1,1};
int dy[]= {0,0,-1,1,-1,1,1,-1};
const int maxn = 1000+66;
const ll mod=1e9+7;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,m;
int vis[maxn];
int pre[maxn];
int ans[maxn];
int num[maxn][maxn];
int mark[maxn][maxn];
bool finds(int x)
{
    for(int i=1; i<=m; i++)
    {
        if(mark[x][i]&&!vis[i])
        {
            vis[i]=1;
            if(pre[i]==0||finds(pre[i]))
            {
                pre[i]=x;
                ans[x]=i;
                return 1;
            }
        }
    }
    return 0;
}
char ch1[maxn];
char ch2[maxn];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(num,0,sizeof(num));
        memset(pre,0,sizeof(pre));
        memset(mark,0,sizeof(mark));
        scanf("%d %d",&n,&m);
        for(int i=1; i<=n; i++)
        {
            scanf("%s%s",ch1,ch2);
            for(int j=0; j<m; j++)
            {
                for(int k=0; k<m; k++)
                {
                    if(ch1[j]==ch2[k])
                        num[j][k]++;
                }
            }
        }
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(num[i][j]==n)
                    mark[i+1][j+1]=1;
            }
        }
        int sum=0;
        for(int i=m; i>=1; i--)
        {
            memset(vis,0,sizeof(vis));
            if(finds(i))
                sum++;
        }
        if(sum<m)
        {
            printf("-1\n");
        }
        else
        {
            for(int i=1; i<=m; i++)
            {
                printf("%d%c",ans[i],i==m?'\n':' ');
            }
        }
    }
}

 

Tags: Java less iOS

Posted on Sun, 18 Aug 2019 20:04:33 -0700 by Edd