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;
}