Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<algorithm>
- #include<vector>
- #include<functional>
- #include<numeric>
- #include<cstdlib>
- #include<cassert>
- #define endl '\n'
- using namespace std;
- namespace {
- template<typename T> using V=vector<T>;
- template<typename T1,typename T2=T1> using P=pair<T1,T2>;
- template<typename T> using F=function<T>;
- using ll=long long;
- }
- constexpr int maxn=1e6+5;
- int n=0,h[maxn],w[maxn],in[maxn],out[maxn],dsu[maxn];
- int find(int x,int d=0){
- assert(d<maxn);
- return x==dsu[x]?x:dsu[x]=find(dsu[x],d+1);
- }
- void merge(int a,int b){dsu[find(a)]=find(b);}
- void init(){
- iota(dsu,dsu+maxn,0);
- }
- void reinit(){
- for(int i=0;i<n;i++){
- in[h[i]]=in[w[i]]=out[h[i]]=out[w[i]]=0;
- dsu[h[i]]=h[i],dsu[w[i]]=w[i];
- }
- }
- void solve(){
- cin>>n;
- for(int i=0;i<n;i++) cin>>h[i];
- for(int i=0;i<n;i++) cin>>w[i];
- for(int i=0;i<n;i++)
- out[h[i]]++,in[w[i]]++,merge(h[i],w[i]);
- int pos=0,neg=0,s=-1,t=-1;
- for(int i=0;i<maxn;i++){
- if(out[i]<in[i]) pos++,t=i;
- if(in[i]<out[i]) neg++,s=i;
- if(abs(out[i]-in[i])>1) goto ICANT;
- }
- if(P{pos,neg}!=P{0,0}&&P{pos,neg}!=P{1,1}) goto ICANT;
- if(!~s) for(int i=0;i<maxn;i++)
- if(out[s=t=i]>0) break;
- for(int i=0;i<maxn;i++)
- if((in[i]||out[i])&&find(i)!=find(s)) goto ICANT;
- cout<<s<<' '<<t<<endl;
- return;
- ICANT:
- cout<<-1<<endl;
- }
- int main(){
- cin.tie(nullptr);
- ios::sync_with_stdio(false);
- int T=1;
- cin>>T;
- init();
- while(T--)
- solve(),reinit();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement