USACO2023JanuarySilverProblem1FindandReplace
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int T;
cin>>T;
while(T>0){
vector<int> g(128),inDegree(128);
T--;
string s,t;
cin>>s>>t;
bool miss=false;
set<int> allc,outchar;
set<pair<int,int>> inpair;
bool notAlleq=false;
for(int i=0;i<s.size();i++){
int a=(int)s[i], b=(int)t[i];
if(inpair.count(make_pair(a,b))>0){//ignore duplicated pairs
continue;
}else{
inpair.insert(make_pair(a,b));
}
if(g[a]>0&&g[a]!=b){
miss=true;
break;
}
outchar.insert(b);
allc.insert(a), allc.insert(b);
if(a!=b){
notAlleq=true;
}
g[a]=b;
inDegree[b]++;
}
if(miss){
cout<<-1<<endl;
continue;
}
if(outchar.size()==52&&!(s==t)){
cout<<-1<<endl;
continue;
}
int ans=0;
int count=0;
for(int c:allc){
if(g[c]>0){
if(g[c]!=c){
ans++;
}else{
g[c]=0;
}
}
}
//find all pure cycle to add ans
vector<int> pathRec(128);
for(int c:allc){
if(pathRec[c]>0){
continue;
}
int a=c;
bool endFound=false;
bool hasInDegreeMoreThanOne=false;
while(pathRec[a]==0){
pathRec[a]=c;
if(inDegree[a]>1){
hasInDegreeMoreThanOne=true;
}
if(g[a]>0){
a=g[a];
}else{
endFound=true;
break;
}
}
if(!endFound&&pathRec[a]==c&&!hasInDegreeMoreThanOne){
ans++;
}
}
cout<<ans<<endl;
}
return 0;
}