#define MULTEST #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include namespace kod { namespace util { template class fixed_point : private F { constexpr fixed_point(F&& f) noexcept : F(std::forward(f)) {} template friend constexpr decltype(auto) make_fixed(G&&) noexcept; public: template constexpr decltype(auto) operator()(Args&&... args) const noexcept { return F::operator()(*this, std::forward(args)...); } }; template [[nodiscard]] constexpr decltype(auto) make_fixed(G&& g) noexcept { using F = std::decay_t; return fixed_point(std::forward(g)); } } // namespace util } // namespace kod namespace kod { namespace util { class forward_loop { int x, y; constexpr forward_loop(int x, int y) noexcept : x(x), y(y) {} friend constexpr forward_loop rep(int, int) noexcept; friend constexpr forward_loop rep(int) noexcept; public: constexpr forward_loop begin() const noexcept { return *this; } constexpr std::monostate end() const noexcept { return {}; } constexpr bool operator!=(std::monostate) const noexcept { return x < y; } constexpr void operator++() const noexcept {} constexpr int operator*() noexcept { return x++; } }; [[nodiscard]] constexpr forward_loop rep(int l, int r) noexcept { return forward_loop(l, r); } [[nodiscard]] constexpr forward_loop rep(int n) noexcept { return forward_loop(0, n); } class backward_loop { int x, y; constexpr backward_loop(int x, int y) noexcept : x(x), y(y) {} friend constexpr backward_loop revrep(int, int) noexcept; friend constexpr backward_loop revrep(int) noexcept; public: constexpr backward_loop begin() const noexcept { return *this; } constexpr std::monostate end() const noexcept { return {}; } constexpr bool operator!=(std::monostate) const noexcept { return x > y; } constexpr void operator++() const noexcept {} constexpr int operator*() noexcept { return --x; } }; [[nodiscard]] constexpr backward_loop revrep(int l, int r) noexcept { return backward_loop(r, l); } [[nodiscard]] constexpr backward_loop revrep(int n) noexcept { return backward_loop(n, 0); } template constexpr void repeat(int n, const F& f) noexcept { assert(n >= 0); while (n--) f(); } } // namespace util } // namespace kod namespace kod { namespace util { namespace stdio_impl { template T scan() { T x; std::cin >> x; return x; } struct scan_any { template operator T() const { return scan(); } }; } // namespace stdio_impl template decltype(auto) scan() { if constexpr (std::is_same_v) return stdio_impl::scan_any{}; else return stdio_impl::scan(); } template std::array scan_arr() { std::array a; for (auto& x : a) x = scan(); return a; } template std::vector scan_vec(int n) { if (n == -1) n = scan(); assert(n >= 0); std::vector v; v.reserve(n); while (n--) v.push_back(scan()); return v; } void flush() { std::cout << std::flush; } void print() {} template void print(const T& x, const Args&... args) { std::cout << x; if (sizeof...(args) != 0) std::cout << ' '; print(args...); } template void println(const Args&... args) { print(args...); std::cout << '\n'; } template void print_seq(const C& c, const char* sep = " ", const char* end = "\n") { bool f = false; for (const auto& x : c) { if (f) std::cout << sep; else f = true; std::cout << x; } std::cout << end; } } // namespace util } // namespace kod namespace kod { namespace sol { using ll = long long; using uint = unsigned; using ull = unsigned long long; using std::array; using std::pair; using std::string; using std::tuple; using std::vector; using namespace util; constexpr int inf = std::numeric_limits::max() / 2; constexpr ll infll = std::numeric_limits::max() / 2; constexpr ll floor_div(ll x, ll y) noexcept { assert(y != 0); return x / y - ((x ^ y) < 0 && x % y != 0); } constexpr ll ceil_div(ll x, ll y) noexcept { assert(y != 0); return x / y + ((x ^ y) >= 0 && x % y != 0); } template constexpr bool setmin(T& lhs, const T& rhs) noexcept { if (lhs > rhs) { lhs = rhs; return true; } return false; } template constexpr bool setmax(T& lhs, const T& rhs) noexcept { if (lhs < rhs) { lhs = rhs; return true; } return false; } void run(); } // namespace sol } // namespace kod int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout << std::fixed << std::setprecision(20); int cases = 1; #ifdef MULTEST std::cin >> cases; #endif while (cases--) kod::sol::run(); return 0; } #ifdef KOD_LOCAL #define OJ_LOCAL(a, b) b #include #else #define OJ_LOCAL(a, b) a #define DBG(...) #define SHOW(...) #endif namespace kod { namespace sol { class Range { struct Iter { int itr; constexpr Iter(const int pos) noexcept : itr(pos) {} constexpr void operator++() noexcept { ++itr; } constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; } constexpr int operator*() const noexcept { return itr; } }; const Iter first, last; public: explicit constexpr Range(const int first, const int last) noexcept : first(first), last(std::max(first, last)) {} constexpr Iter begin() const noexcept { return first; } constexpr Iter end() const noexcept { return last; } }; constexpr Range rep(const int l, const int r) noexcept { return Range(l, r); } constexpr Range rep(const int n) noexcept { return Range(0, n); } class UnionFind { int components; std::vector data; public: explicit UnionFind(const int size = 0) : components(size), data(size, (int)-1) {} int size() const { return data.size(); } int count() const { return components; } int leader(const int u) { assert(0 <= u and u < size()); return data[u] < 0 ? u : data[u] = leader(data[u]); } int size(const int u) { assert(0 <= u and u < size()); return -data[leader(u)]; } std::pair merge(int u, int v) { assert(0 <= u and u < size()); assert(0 <= v and v < size()); u = leader(u); v = leader(v); if (u == v) return std::make_pair(u, false); if (data[u] > data[v]) std::swap(u, v); components -= 1; data[u] += data[v]; data[v] = u; return std::make_pair(u, true); } bool same(const int u, const int v) { assert(0 <= u and u < size()); assert(0 <= v and v < size()); return leader(u) == leader(v); } std::vector> decompose() { std::vector buf(size()), len(size()); for (const int i : rep(size())) len[buf[i] = leader(i)]++; std::vector> ret(size()); for (const int i : rep(size())) ret[i].reserve(len[i]); for (const int i : rep(size())) ret[buf[i]].push_back(i); ret.erase(std::remove_if(ret.begin(), ret.end(), [&](const std::vector& v) { return v.empty(); }), ret.end()); return ret; } }; void run() { const int n = scan(); auto a = scan_vec(n); auto b = scan_vec(n); UnionFind dsu(n); vector deg(n); for (const int i : rep(n)) { a[i] -= 1, b[i] -= 1; dsu.merge(i, a[i]); deg[a[i]] += 1; } vector> tree(n); vector cycle(n); { std::queue que; for (const int i : rep(n)) { if (deg[i] == 0) que.push(i); } while (!que.empty()) { const int u = que.front(); que.pop(); tree[a[u]].push_back(u); if ((--deg[a[u]]) == 0) que.push(a[u]); } for (const int i : rep(n)) { cycle[i] = (deg[i] > 0); } } vector in(n), out(n); { int timer = 0; for (const int i : rep(n)) { if (cycle[i]) { make_fixed([&](auto&& dfs, const int u) -> void { in[u] = timer++; for (const int v : tree[u]) dfs(v); out[u] = timer++; })(i); } } } for (const int i : rep(n)) { if (!dsu.same(i, b[i])) { println("No"); return; } if (cycle[i]) { if (!cycle[b[i]]) { println("No"); return; } } else { if (!cycle[b[i]] && !(in[b[i]] < in[i] && out[i] < out[b[i]])) { println("No"); return; } } } vector done(n); std::fill(deg.begin(), deg.end(), 0); vector next(n), prev(n); for (const int src : rep(n)) { if (!cycle[src] || done[src]) continue; vector seq; for (int i = src; !done[i]; i = a[i]) { done[i] = true; seq.push_back(i); } const int m = (int)seq.size(); for (const int i : rep(m)) { const int x = seq[i]; const int y = seq[(i + 1) % m]; next[x] = y; prev[y] = x; } for (const int i : seq) deg[b[i]] += 1; std::queue que; for (const int i : seq) { if (deg[i] == 0) que.push(i); } while (!que.empty()) { const int i = que.front(); que.pop(); const int l = prev[i]; const int r = next[i]; next[l] = r; prev[r] = l; if ((--deg[b[i]]) == 0) { que.push(b[i]); } } for (const int i : seq) { if (deg[i] > 0 && next[i] != b[i]) { println("No"); return; } } } println("Yes"); } } // namespace sol } // namespace kod