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>
- 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;
- static inline void solve(){
- int n;cin>>n;
- V<int> h(n),w(n);
- for(auto& i:h) cin>>i;
- for(auto& i:w) cin>>i;
- V<V<int>> e(maxn);
- V<int> in(maxn,0),dsu(maxn);
- iota(dsu.begin(),dsu.end(),0);
- F<int(int)> find=[&](int x){
- return x==dsu[x]?x:dsu[x]=find(dsu[x]);
- };
- auto merge=[&](int a,int b){dsu[find(a)]=find(b);};
- for(int i=0;i<n;i++){
- e[h[i]].emplace_back(w[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((int)e[i].size()<in[i]) pos++,t=i;
- if(in[i]<(int)e[i].size()) neg++,s=i;
- if(abs((int)e[i].size()-in[i])>1) {
- cerr<<i<<' '<<in[i]<<' '<<e[i].size()<<endl;
- 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(e[s=t=i].size()>0) break;
- for(int i=0;i<maxn;i++)
- if((in[i]||e[i].size())&&find(i)!=find(s)){
- cerr<<i<<endl;
- goto ICANT;
- }
- cout<<s<<' '<<t<<endl;
- return;
- ICANT:
- cout<<-1<<endl;
- }
- int main(){
- int T=1;
- cin>>T;
- while(T--)
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment