1534C - Little Alawn's Puzzle - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define vll vector<ll>
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define no cout<<"NO"<<endl
#define yes cout<<"YES"<<endl
#define min3(a,b,c) min(a,min(b,c))
#define min4(a,b,c,d) min(a,min(b,min(c,d)))
#define max3(a,b,c) max(a,max(b,c))
#define max4(a,b,c,d) max(a,max(b,max(c,d)))
#define slow ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
const int N=4*(1e5)+1;
const int mod=1e9+7;
vector<bool> vis(N,false);
vector<ll> g[N];


void dfs(int parent){
  vis[parent]=true;
  for(auto x:g[parent]){
    if(vis[x]==true) continue;
    dfs(x);
  }
}


void solve()
{ 
   ll n;
   cin>>n;
   vll a(n),b(n);
   for(int i=0;i<n;i++){
    cin>>a[i];
    g[a[i]].pb(b[i]);
    vis[i+1]=false;
    g[i+1].clear();
   }

    for(int i=0;i<n;i++){
    cin>>b[i];
    g[b[i]].pb(a[i]);
   }
 ll ans=1;
   for(int i=1;i<=n;i++){
     if(vis[i]==false){
      dfs(i);
        ans*=2;
        ans=ans%mod;
     }
   }
   cout<<ans<<endl;
  
  
}


 

int main() {

#ifndef ONLINE_JUDGE
  freopen("Error.txt", "w", stderr);
#endif


  slow;

  ll t = 1;
  // ll ks = 1;
 cin >> t;
  while (t--)
  {
    // cout << "Case #" << ks++ << ":" << ' ';
    solve();
  }

  return 0;
}