Advertisement
konchin_shih

pH

Nov 13th, 2022
599
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.58 KB | None | 0 0
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4. #include<functional>
  5. #include<numeric>
  6. #include<cstdlib>
  7. #include<cassert>
  8. #define endl '\n'
  9. using namespace std;
  10. namespace {
  11.     template<typename T> using V=vector<T>;
  12.     template<typename T1,typename T2=T1> using P=pair<T1,T2>;
  13.     template<typename T> using F=function<T>;
  14.     using ll=long long;
  15. }
  16. constexpr int maxn=1e6+5;
  17. int n=0,h[maxn],w[maxn],in[maxn],out[maxn],dsu[maxn];
  18. int find(int x,int d=0){
  19.     assert(d<maxn);
  20.     return x==dsu[x]?x:dsu[x]=find(dsu[x],d+1);
  21. }
  22. void merge(int a,int b){dsu[find(a)]=find(b);}
  23. void init(){
  24.     iota(dsu,dsu+maxn,0);
  25. }
  26. void reinit(){
  27.     for(int i=0;i<n;i++){
  28.         in[h[i]]=in[w[i]]=out[h[i]]=out[w[i]]=0;
  29.         dsu[h[i]]=h[i],dsu[w[i]]=w[i];
  30.     }
  31. }
  32. void solve(){
  33.     cin>>n;
  34.     for(int i=0;i<n;i++) cin>>h[i];
  35.     for(int i=0;i<n;i++) cin>>w[i];
  36.     for(int i=0;i<n;i++)
  37.         out[h[i]]++,in[w[i]]++,merge(h[i],w[i]);
  38.     int pos=0,neg=0,s=-1,t=-1;
  39.     for(int i=0;i<maxn;i++){
  40.         if(out[i]<in[i]) pos++,t=i;
  41.         if(in[i]<out[i]) neg++,s=i;
  42.         if(abs(out[i]-in[i])>1) goto ICANT;
  43.     }
  44.     if(P{pos,neg}!=P{0,0}&&P{pos,neg}!=P{1,1}) goto ICANT;
  45.     if(!~s) for(int i=0;i<maxn;i++)
  46.         if(out[s=t=i]>0) break;
  47.     for(int i=0;i<maxn;i++)
  48.         if((in[i]||out[i])&&find(i)!=find(s)) goto ICANT;
  49.     cout<<s<<' '<<t<<endl;
  50.     return;
  51. ICANT:
  52.     cout<<-1<<endl;
  53. }
  54. int main(){
  55.     cin.tie(nullptr);
  56.     ios::sync_with_stdio(false);
  57.     int T=1;
  58.     cin>>T;
  59.     init();
  60.     while(T--)
  61.         solve(),reinit();
  62.     return 0;
  63. }
  64.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement