#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using namespace atcoder; #define rep(i,n) for (int i=0;i using vec = vector; template using vvec = vec>; template using vvvec = vec>; using ll = long long; using pii = pair; using pll = pair; template bool chmin(T &a, T b){ if (a>b){ a = b; return true; } return false; } template bool chmax(T &a, T b){ if (a T sum(vec x){ T res=0; for (auto e:x){ res += e; } return res; } template void printv(vec x){ for (auto e:x){ cout<> boolean_matrix_mul(int n, vec> A, vec> B){ vec> res(n,vec(n,false)); rep(i,n){ rep(j,n){ auto tmp = A[i]&B[j]; res[i][j] = tmp.any(); } } return res; } vec> transtive_closure(int n,vec> edge){ //input graph should be acyclic //1,2,...,n should be topological order //res[i][j] is true iff j->i assert (n==edge.size()); vec> res(n); rep(i,n){ res[i].set(i,true); rep(j,n){ if (edge[i][j]){ res[j] |= res[i]; } } res[i].set(i,false); } return res; } vec transtive_reduction(int N,vec> edge){ // scc -> m3 = edge * transtive_closure -> (edge - m3) -> cyclic expansion scc_graph G(N); rep(i,N){ rep(j,N){ if (edge[i][j]){ G.add_edge(i,j); } } } auto E = G.scc(); int n = E.size(); vec v_to_e(N,-1); rep(i,n){ for (auto v:E[i]){ v_to_e[v] = i; } } vec> scc_edge(n); rep(i,N){ rep(j,N){ if (edge[i][j] && v_to_e[i]!=v_to_e[j]){ scc_edge[v_to_e[i]].set(v_to_e[j],true); } } } auto tra = transtive_closure(n,scc_edge); auto m3 = boolean_matrix_mul(n,scc_edge,tra); vec res; rep(i,n){ rep(j,n){ if (scc_edge[i][j] && !m3[i][j]){ res.append({E[i][0],E[j][0]}); } } } rep(i,n){ if (E[i].size()!=1){ rep(j,E[i].size()-1){ res.append({E[i][j],E[i][j+1]}); } int p = E[i].size(); res.append({E[i][p-1],E[i][0]}); } } return res; } int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); int N,M; cin>>N>>M; assert (N <= 5000); vec A(N),B(N); rep(i,N){ cin>>A[i]; } rep(i,N){ cin>>B[i]; } vec> edge(N); rep(i,N){ rep(j,N){ if (i>u>>v; edge[u-1].set(v-1,false); edge[v-1].set(u-1,false); } auto res = transtive_reduction(N,edge); cout<