#include using namespace std; using ll=long long; using vi=vector; using pii=pair; #define all(x) begin(x),end(x) #define sz(x) (int)x.size() #define rep(i,a,b) for(int i=a;i gc, guc; bool chk_a(int r, int c, int v) { rep(i,0,9) { if(a[r][i]==v) return 0; if(a[i][c]==v) return 0; } int br = r/3*3, bc = c/3*3; rep(i,0,3) rep(j,0,3) { if(a[br+i][bc+j]==v) return 0; } return 1; } bool gen_a(int r, int c) { if(r==9) return 1; int nr = c==8 ? r+1 : r; int nc = c==8 ? 0 : c+1; vi p(9); iota(all(p),0); shuffle(all(p),rng); for(int v : p) { if(chk_a(r,c,v)) { a[r][c] = v; if(gen_a(nr,nc)) return 1; a[r][c] = -1; } } return 0; } bool dfs_b(int c) { if(c==9) return 1; rep(idx,0,sz(gc)) { const auto& v = gc[idx]; const auto& u = guc[idx]; bool ok = 1; rep(i,0,9) { if(rb[i] & (1<