#pragma GCC optimize ("Ofast") #include using namespace std; void *wmem; char memarr[96000000]; template inline S min_L(S a,T b){ return a<=b?a:b; } template inline void walloc1d(T **arr, int x, void **mem = &wmem){ static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] ); (*arr)=(T*)(*mem); (*mem)=((*arr)+x); } struct Rand{ unsigned x; unsigned y; unsigned z; unsigned w; Rand(void){ x=123456789; y=362436069; z=521288629; w=(unsigned)time(NULL); } Rand(unsigned seed){ x=123456789; y=362436069; z=521288629; w=seed; } inline unsigned get(void){ unsigned t; t = (x^(x<<11)); x=y; y=z; z=w; w = (w^(w>>19))^(t^(t>>8)); return w; } inline double getUni(void){ return get()/4294967296.0; } inline int get(int a){ return (int)(a*getUni()); } inline int get(int a, int b){ return a+(int)((b-a+1)*getUni()); } inline long long get(long long a){ return(long long)(a*getUni()); } inline long long get(long long a, long long b){ return a+(long long)((b-a+1)*getUni()); } inline double get(double a, double b){ return a+(b-a)*getUni(); } inline int getExp(int a){ return(int)(exp(getUni()*log(a+1.0))-1.0); } inline int getExp(int a, int b){ return a+(int)(exp(getUni()*log((b-a+1)+1.0))-1.0); } } ; inline int my_getchar_unlocked(){ static char buf[1048576]; static int s = 1048576; static int e = 1048576; if(s == e && e == 1048576){ e = fread_unlocked(buf, 1, 1048576, stdin); s = 0; } if(s == e){ return EOF; } return buf[s++]; } inline void rd(int &x){ int k; int m=0; x=0; for(;;){ k = my_getchar_unlocked(); if(k=='-'){ m=1; break; } if('0'<=k&&k<='9'){ x=k-'0'; break; } } for(;;){ k = my_getchar_unlocked(); if(k<'0'||k>'9'){ break; } x=x*10+k-'0'; } if(m){ x=-x; } } struct MY_WRITER{ char buf[1048576]; int s; int e; MY_WRITER(){ s = 0; e = 1048576; } ~MY_WRITER(){ if(s){ fwrite_unlocked(buf, 1, s, stdout); } } } ; MY_WRITER MY_WRITER_VAR; void my_putchar_unlocked(int a){ if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){ fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout); MY_WRITER_VAR.s = 0; } MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a; } inline void wt_L(char a){ my_putchar_unlocked(a); } inline void wt_L(int x){ int s=0; int m=0; char f[10]; if(x<0){ m=1; x=-x; } while(x){ f[s++]=x%10; x/=10; } if(!s){ f[s++]=0; } if(m){ my_putchar_unlocked('-'); } while(s--){ my_putchar_unlocked(f[s]+'0'); } } inline void wt_L(const char c[]){ int i=0; for(i=0;c[i]!='\0';i++){ my_putchar_unlocked(c[i]); } } template inline void arrInsert(const int k, int &sz, S a[], const S aval){ int i; sz++; for(i=sz-1;i>k;i--){ a[i] = a[i-1]; } a[k] = aval; } template inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval){ int i; sz++; for(i=sz-1;i>k;i--){ a[i] = a[i-1]; } for(i=sz-1;i>k;i--){ b[i] = b[i-1]; } a[k] = aval; b[k] = bval; } template inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval){ int i; sz++; for(i=sz-1;i>k;i--){ a[i] = a[i-1]; } for(i=sz-1;i>k;i--){ b[i] = b[i-1]; } for(i=sz-1;i>k;i--){ c[i] = c[i-1]; } a[k] = aval; b[k] = bval; c[k] = cval; } template inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval, V d[], const V dval){ int i; sz++; for(i=sz-1;i>k;i--){ a[i] = a[i-1]; } for(i=sz-1;i>k;i--){ b[i] = b[i-1]; } for(i=sz-1;i>k;i--){ c[i] = c[i-1]; } for(i=sz-1;i>k;i--){ d[i] = d[i-1]; } a[k] = aval; b[k] = bval; c[k] = cval; d[k] = dval; } struct graph{ int N; int *es; int **edge; void setDirectEdge(int N__, int M, int A[], int B[], void **mem = &wmem){ int i; N = N__; walloc1d(&es, N, mem); walloc1d(&edge, N, mem); walloc1d(&edge[0], M, mem); for(i=(0);i<(N);i++){ es[i] = 0; } for(i=(0);i<(M);i++){ es[A[i]]++; } for(i=(0);i<(N);i++){ walloc1d(&edge[i], es[i], mem); } for(i=(0);i<(N);i++){ es[i] = 0; } for(i=(0);i<(M);i++){ edge[A[i]][es[A[i]]++] = B[i]; } } int TopologicalSort(int res[], void *mem=wmem){ int i; int j; int k; int rs; int *deg; int *q; int qs = 0; int qe = 0; walloc1d(°, N, &mem); walloc1d(&q, N, &mem); rs = 0; for(i=(0);i<(N);i++){ deg[i] = 0; } for(i=(0);i<(N);i++){ for(j=(0);j<(es[i]);j++){ deg[edge[i][j]]++; } } for(i=(0);i<(N);i++){ if(deg[i]==0){ q[qe++] = i; } } while(qs < qe){ i = q[qs++]; res[rs++] = i; for(j=(0);j<(es[i]);j++){ k = edge[i][j]; deg[k]--; if(deg[k]==0){ q[qe++] = k; } } } if(rs==N){ return 1; } return 0; } } ; struct dimcomp2{ int B; dimcomp2(){ } dimcomp2(int b){ B = b; } dimcomp2(int a, int b){ B = b; } inline void set(int b){ B = b; } inline void set(int a, int b){ B = b; } inline int mask(int a, int b){ return a * B + b; } inline int operator()(int a, int b){ return a * B + b; } inline void para(int mask, int &a, int &b){ a = mask / B; b = mask % B; } inline void operator()(int mask, int &a, int &b){ a = mask / B; b = mask % B; } } ; int N; int K; int res[1000][1000]; Rand rnd; int arr[1000]; int rev[1000]; int tar1[1000]; int tar2[1000]; graph g; int n; int m; int a[3000000]; int b[3000000]; int ind[1000000]; int sz; int lis[1000]; void doit(){ int i; sz = 0; for(i=(1);i<(N);i++){ if(arr[i-1] < arr[i]){ lis[sz++] = i; } } i = lis[rnd.get(sz)]; swap(arr[i-1], arr[i]); } int main(){ int k; wmem = memarr; int i; int j; int k1; int k2; int cnt; void *tmem; rd(N); rd(K); dimcomp2 dm(N,N); if(K > N*(N-1)){ wt_L("No"); wt_L('\n'); return 0; } wt_L("Yes"); wt_L('\n'); tmem = wmem; for(;;){ wmem = tmem; k1 =min_L(N*(N-1)/2, K); k2 = K - k1; if(k1 && k2){ k = rnd.get(k1-k2); k1 -= k; k2 += k; } cnt = 0; for(i=(0);i<(N);i++){ arr[i] = i; } for(;;){ if(cnt==k1){ for(i=(0);i<(N);i++){ tar1[i] = arr[i]; } } if(cnt==k2){ for(i=(0);i<(N);i++){ tar2[i] = arr[i]; } } if(cnt >= k1 && cnt >= k2){ break; } doit(); cnt++; } if(k1==0){ for(i=(0);i<(N);i++){ tar1[i] = 0; } } if(k2==0){ for(i=(0);i<(N);i++){ tar2[i] = 0; } } n = N*N; m = 0; cnt = 0; for(i=(0);i<(N);i++){ arr[i] = i; } for(;;){ int fg = 0; for(i=(0);i<(N);i++){ if(tar1[i]==cnt){ for(j=(0);j<(N);j++){ rev[arr[j]] = j; } for(j=(1);j<(N);j++){ arrInsert(m, m, a, dm(i,rev[j-1]), b, dm(i,rev[j])); } } } for(i=(0);i<(N);i++){ if(tar2[i]==cnt){ for(j=(0);j<(N);j++){ rev[arr[j]] = j; } for(j=(1);j<(N);j++){ arrInsert(m, m, a, dm(rev[j-1],i), b, dm(rev[j],i)); } } } for(i=(0);i<(N);i++){ if(tar1[i] > cnt){ fg = 1; } } for(i=(0);i<(N);i++){ if(tar2[i] > cnt){ fg = 1; } } if(fg==0){ break; } doit(); cnt++; } g.setDirectEdge(n, m, a, b); if(g.TopologicalSort(ind)==0){ continue; } break; } for(k=(0);k<(n);k++){ dm(ind[k], i, j); res[i][j] = k; } { int OC5CYxKD; int o3WxPXbE; for(OC5CYxKD=(0);OC5CYxKD<(N);OC5CYxKD++){ if(N==0){ wt_L('\n'); } else{ for(o3WxPXbE=(0);o3WxPXbE<(N-1);o3WxPXbE++){ wt_L(res[OC5CYxKD][o3WxPXbE]); wt_L(' '); } wt_L(res[OC5CYxKD][o3WxPXbE]); wt_L('\n'); } } } return 0; } // cLay varsion 20200509-1 // --- original code --- // int N, K; // int res[1000][1000]; // // Rand rnd; // int arr[1000], rev[1000]; // int tar1[1000], tar2[1000]; // // graph g; // int n, m, a[3d6], b[3d6], ind[1d6]; // // int sz, lis[1000]; // void doit(){ // int i; // sz = 0; // rep(i,1,N) if(arr[i-1] < arr[i]) lis[sz++] = i; // i = lis[rnd.get(sz)]; // swap(arr[i-1], arr[i]); // } // // { // int i, j, k1, k2, cnt; // void *tmem; // rd(N,K); // // dimcomp2 dm(N,N); // // if(K > N*(N-1)) wt("No"), return 0; // wt("Yes"); // // tmem = wmem; // for(;;){ // wmem = tmem; // k1 = min(N*(N-1)/2, K); // k2 = K - k1; // // wt("K",k1,k2); // // if(k1 && k2){ // k = rnd.get(k1-k2); // k1 -= k; // k2 += k; // } // // cnt = 0; // rep(i,N) arr[i] = i; // // for(;;){ // if(cnt==k1) rep(i,N) tar1[i] = arr[i]; // if(cnt==k2) rep(i,N) tar2[i] = arr[i]; // if(cnt >= k1 && cnt >= k2) break; // doit(); cnt++; // } // // if(k1==0) rep(i,N) tar1[i] = 0; // if(k2==0) rep(i,N) tar2[i] = 0; // // // wt("tar1", tar1(N)); // // wt("tar2", tar2(N)); // // n = N*N; // m = 0; // // cnt = 0; // rep(i,N) arr[i] = i; // for(;;){ // int fg = 0; // rep(i,N) if(tar1[i]==cnt){ // rep(j,N) rev[arr[j]] = j; // rep(j,1,N) arrInsert(m, m, a, dm(i,rev[j-1]), b, dm(i,rev[j])); // } // rep(i,N) if(tar2[i]==cnt){ // rep(j,N) rev[arr[j]] = j; // rep(j,1,N) arrInsert(m, m, a, dm(rev[j-1],i), b, dm(rev[j],i)); // } // rep(i,N) if(tar1[i] > cnt) fg = 1; // rep(i,N) if(tar2[i] > cnt) fg = 1; // if(fg==0) break; // // doit(); cnt++; // } // // // puts("hoge"); // // rep(i,m) wt(a[i],b[i]); // g.setDirectEdge(n, m, a, b); // if(g.TopologicalSort(ind)==0) continue; // break; // } // // rep(k,n){ // dm(ind[k], i, j); // res[i][j] = k; // } // wt(res(N,N)); // }