#pragma region preprocessor #ifdef LOCAL //* #define _GLIBCXX_DEBUG // gcc /*/ #define _LIBCPP_DEBUG 0 // clang //*/ #define __clock__ // #define __buffer_check__ #else #pragma GCC optimize("Ofast") // #define __buffer_check__ // #define NDEBUG #endif #define __precision__ 15 #define iostream_untie true #include #include #define __all(v) std::begin(v), std::end(v) #define __rall(v) std::rbegin(v), std::rend(v) #define __popcount(n) __builtin_popcountll(n) #define __clz32(n) __builtin_clz(n) #define __clz64(n) __builtin_clzll(n) #define __ctz32(n) __builtin_ctz(n) #define __ctz64(n) __builtin_ctzll(n) #ifdef __clock__ #include "clock.hpp" #else #define build_clock() ((void)0) #define set_clock() ((void)0) #define get_clock() ((void)0) #endif #ifdef LOCAL #include "dump.hpp" #define mesg(str) std::cerr << "[ " << __LINE__ << " : " << __FUNCTION__ << " ] " << str << "\n" #else #define dump(...) ((void)0) #define mesg(str) ((void)0) #endif #pragma endregion // preprocessor #pragma region std-overload namespace std { // hash template size_t hash_combine(size_t seed, T const &key) { return seed ^ (hash()(key) + 0x9e3779b9 + (seed << 6) + (seed >> 2)); } template struct hash> { size_t operator()(pair const &pr) const { return hash_combine(hash_combine(0, pr.first), pr.second); } }; template ::value - 1> struct tuple_hash_calc { static size_t apply(size_t seed, tuple_t const &t) { return hash_combine(tuple_hash_calc::apply(seed, t), get(t)); } }; template struct tuple_hash_calc { static size_t apply(size_t seed, tuple_t const &t) { return hash_combine(seed, get<0>(t)); } }; template struct hash> { size_t operator()(tuple const &t) const { return tuple_hash_calc>::apply(0, t); } }; // iostream template istream &operator>>(istream &is, pair &p) { return is >> p.first >> p.second; } template ostream &operator<<(ostream &os, const pair &p) { return os << p.first << ' ' << p.second; } template struct tupleis { static istream &apply(istream &is, tuple_t &t) { tupleis::apply(is, t); return is >> get(t); } }; template struct tupleis { static istream &apply(istream &is, tuple_t &t) { return is; } }; template istream &operator>>(istream &is, tuple &t) { return tupleis, tuple_size>::value - 1>::apply(is, t); } template <> istream &operator>>(istream &is, tuple<> &t) { return is; } template struct tupleos { static ostream &apply(ostream &os, const tuple_t &t) { tupleos::apply(os, t); return os << ' ' << get(t); } }; template struct tupleos { static ostream &apply(ostream &os, const tuple_t &t) { return os << get<0>(t); } }; template ostream &operator<<(ostream &os, const tuple &t) { return tupleos, tuple_size>::value - 1>::apply(os, t); } template <> ostream &operator<<(ostream &os, const tuple<> &t) { return os; } template , string>::value, nullptr_t> = nullptr> istream& operator>>(istream& is, Container &cont) { for(auto&& e : cont) is >> e; return is; } template , string>::value, nullptr_t> = nullptr> ostream& operator<<(ostream& os, const Container &cont) { bool flag = 1; for(auto&& e : cont) flag ? flag = 0 : (os << ' ', 0), os << e; return os; } } // namespace std #pragma endregion // std-overload #pragma region executive-setting namespace setting { using namespace std; using namespace chrono; system_clock::time_point start_time, end_time; long long get_elapsed_time() { end_time = system_clock::now(); return duration_cast(end_time - start_time).count(); } void print_elapsed_time() { cerr << "\n----- Exec time : " << get_elapsed_time() << " ms -----\n\n"; } void buffer_check() { char bufc; if(cin >> bufc) cerr << "\n\033[1;35mwarning\033[0m: buffer not empty.\n"; } struct setupper { setupper() { if(iostream_untie) ios::sync_with_stdio(false), cin.tie(nullptr); cout << fixed << setprecision(__precision__); #ifdef stderr_path freopen(stderr_path, "a", stderr); #endif #ifdef LOCAL cerr << fixed << setprecision(__precision__) << boolalpha << "\n----- stderr at LOCAL -----\n\n"; #endif #ifdef __clock__ start_time = system_clock::now(); atexit(print_elapsed_time); #endif #ifdef __buffer_check__ atexit(buffer_check); #endif } } __setupper; // struct setupper } // namespace setting #pragma endregion // executive-setting #pragma region fucntion-utility // lambda wrapper for recursive method. template class make_recursive { lambda_type func; public: make_recursive(lambda_type &&f) : func(std::move(f)) {} template auto operator()(Args &&... args) const { return func(*this, std::forward(args)...); } }; template T read(types... args) noexcept { typename std::remove_const::type obj(args...); std::cin >> obj; return obj; } // #define input(type, var, ...) type var{read(__VA_ARGS__)} // substitute y for x if x > y. template inline bool chmin(T &x, const T &y) { return x > y ? x = y, true : false; } // substitute y for x if x < y. template inline bool chmax(T &x, const T &y) { return x < y ? x = y, true : false; } // binary search on discrete range. template iter_type binary(iter_type __ok, iter_type __ng, pred_type pred) { assert(__ok != __ng); std::ptrdiff_t dist(__ng - __ok); while(std::abs(dist) > 1) { iter_type mid(__ok + dist / 2); if(pred(mid)) __ok = mid, dist -= dist / 2; else __ng = mid, dist /= 2; } return __ok; } // binary search on real numbers. template long double binary(long double __ok, long double __ng, const long double eps, pred_type pred) { assert(__ok != __ng); while(std::abs(__ok - __ng) > eps) { long double mid{(__ok + __ng) / 2}; (pred(mid) ? __ok : __ng) = mid; } return __ok; } // trinary search on discrete range. template iter_type trinary(iter_type __first, iter_type __last, comp_type comp) { assert(__first < __last); std::ptrdiff_t dist(__last - __first); while(dist > 2) { iter_type __left(__first + dist / 3), __right = (__first + dist * 2 / 3); if(comp(__left, __right)) __last = __right, dist = dist * 2 / 3; else __first = __left, dist -= dist / 3; } if(dist > 1 && comp(next(__first), __first)) ++__first; return __first; } // trinary search on real numbers. template long double trinary(long double __first, long double __last, const long double eps, comp_type comp) { assert(__first < __last); while(__last - __first > eps) { long double __left{(__first * 2 + __last) / 3}, __right{(__first + __last * 2) / 3}; if(comp(__left, __right)) __last = __right; else __first = __left; } return __first; } // size of array. template size_t size(A (&array)[N]) { return N; } // be careful that val is type-sensitive. template void init(A (&array)[N], const T &val) { std::fill((T*)array, (T*)(array + N), val); } #pragma endregion // function-utility #pragma region using-alias using namespace std; using i32 = int_least32_t; using i64 = int_least64_t; using u32 = uint_least32_t; using u64 = uint_least64_t; using p32 = pair; using p64 = pair; template > using heap = priority_queue, Comp>; template using hashset = unordered_set; template using hashmap = unordered_map; using namespace __gnu_cxx; #pragma endregion // using-alias #pragma region library #ifndef strongly_connected_components_hpp #define strongly_connected_components_hpp #include class strongly_connected_components { const size_t V; std::vector> adj, mem; std::vector comp, low; size_t cnt; bool is_built; public: strongly_connected_components(size_t _V) : V(_V), adj(V), comp(V), low(V), is_built() {} // add an edge from the vertex s to the vertex t. void add_edge(size_t s, size_t t) { adj[s].emplace_back(t); is_built = false; dump(s,t); } // the number of the components. size_t count() { return build(), cnt; } // the number of vertices in the i-th component. size_t size(size_t i) { return build(), mem[i].size(); } // vertices in the i-th component. const std::vector &component(size_t i) { return build(), mem[i]; } // the component which the vertex v belongs to. size_t operator[](size_t v) { return build(), comp[v]; } // the directed acyclic graph consisting of the components. std::vector> make_dag() { build(); std::vector> res(cnt); bool *apr = new bool[V]{}; size_t *stack_ptr = new size_t[V]; for(size_t i = 0; i != cnt; ++i) { size_t *itr = stack_ptr; for(size_t s : mem[i]) for(size_t t : adj[s]) if(!apr[comp[t]]) apr[comp[t]] = true, *itr++ = comp[t]; res[i].resize(itr - stack_ptr); while(itr != stack_ptr) apr[res[i][--itr - stack_ptr] = *itr] = false; } delete[] apr; delete[] stack_ptr; return res; } protected: void build() { if(is_built) return; is_built = true, cnt = 0; fill(low.begin(), low.end(), -1); fill(comp.begin(), comp.end(), -1); size_t *itr = new size_t[V]; for(size_t v = 0, c = 0; v != V; ++v) affix(v, c, itr); delete[] itr; mem.resize(cnt); for(size_t v = 0; v != V; ++v) mem[comp[v] = cnt - 1 - comp[v]].emplace_back(v); } size_t affix(size_t v, size_t &c, size_t* &itr) { if(~low[v]) return ~comp[v] ? -1 : low[v]; size_t idx = c++; low[v] = idx; *itr++ = v; for(int u : adj[v]) low[v] = std::min(low[v], affix(u, c, itr)); if(low[v] == idx) { do { comp[*--itr] = cnt; } while(*itr != v); ++cnt; } return low[v]; } }; // class strongly_connected_components #endif // strongly_connected_components_hpp #pragma endregion // library #pragma region main-code struct solver; template void main_(); int main() { main_(); } template void main_() { unsigned t = 1; #ifdef LOCAL t = 1; #endif // t = -1; // infinite loop // cin >> t; // case number given while(t--) solver(); } struct solver { solver() { int n; cin>>n; strongly_connected_components scc(n*n*2); vector s(n),t(n); cin>>s>>t; for(int i=0; i>u; v=u>>1; u&=1; int src=0, nsrc=n*n; if(u) swap(src,nsrc); int dst=0, ndst=n*n; if(v) swap(dst,ndst); for(int j=0; j(n)); for(int i=0; iscc[i+n*n]) { ans[i/n][i%n]=1; } } for(auto row: ans) { cout << row << "\n"; } } }; #pragma endregion // main-code