#include #include #define N_MAX 1000 #define MT_N 624 #define MT_M 397 #define MT_MATRIX_A 0x9908b0dfUL #define MT_UPPER_MASK 0x80000000UL #define MT_LOWER_MASK 0x7fffffffUL static unsigned int mt[MT_N]; static int mti = MT_N + 1; void init_genrand(unsigned int s) { mt[0] = s & 0xffffffffUL; for (mti = 1; mti < MT_N; mti++) { mt[mti] = (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti); mt[mti] &= 0xffffffffUL; } } unsigned int genrand() { unsigned int y; static unsigned int mag01[2] = {0x0UL, MT_MATRIX_A}; if (mti >= MT_N) { int kk; if (mti == MT_N + 1) init_genrand(5489UL); for (kk = 0; kk < MT_N - MT_M; kk++) { y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK); mt[kk] = mt[kk+MT_M] ^ (y >> 1) ^ mag01[y&0x1UL]; } for (; kk < MT_N - 1; kk++) { y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK); mt[kk] = mt[kk+(MT_M-MT_N)] ^ (y >> 1) ^ mag01[y&0x1UL]; } y = (mt[MT_N-1] & MT_UPPER_MASK) | (mt[0] & MT_LOWER_MASK); mt[MT_N-1] = mt[MT_M-1] ^ (y >> 1) ^ mag01[y&0x1UL]; mti = 0; } y = mt[mti++]; y ^= (y >> 11); y ^= (y << 7) & 0x9d2c5680UL; y ^= (y << 15) & 0xefc60000UL; y ^= (y >> 18); return y; } void shuffle_permutation(int N, int p[], int K) { int i, j; while (K--) { i = genrand() % N + 1; j = genrand() % N + 1; if (i != j) { p[i] ^= p[j]; p[j] ^= p[i]; p[i] ^= p[j]; } } } int is_arborescence(int N, int P[]) { int i, j, flag[N_MAX + 1] = {}; for (j = 1; j <= N; j++) if (P[j] == 0) flag[j] = -1; // root for (i = 1; i <= N; i++) { if (flag[i] != 0) continue; for (j = i; flag[j] == 0; j = P[j]) flag[j] = 1; if (flag[j] > 0) return 0; for (j = i; flag[j] == 1; j = P[j]) flag[j] = -1; } return 1; } void solve_random(int N, int K, int P[][N_MAX + 1], int Q[]) { int i, j; static int p[N_MAX + 1], q[N_MAX + 1]; for (i = 1; i <= N - 1; i++) p[i] = i; for (j = 1; j <= N; j++) q[j] = j; shuffle_permutation(N - 1, p, N * 10); shuffle_permutation(N, q, N * 10); while (1) { for (i = 0; i <= N; i++) Q[i] = -1; Q[genrand() % N + 1] = 0; for (i = 1; i <= N - 1; i++) { shuffle_permutation(N, q, N); for (j = 1; j <= N; j++) if (Q[P[p[i]][q[j]]] >= 0 && Q[q[j]] < 0) break; if (j > N) break; Q[q[j]] = p[i]; } if (i > N - 1) break; shuffle_permutation(N - 1, p, N); } } int main() { int i, j, N, K; static int P[N_MAX + 1][N_MAX + 1]; scanf("%d %d", &N, &K); for (i = 1; i <= N - 1; i++) for (j = 1; j <= N; j++) scanf("%d", &(P[i][j])); int Q[N_MAX + 1]; solve_random(N, K, P, Q); printf("Yes\n"); for (j = 1; j <= N; j++) printf("%d ", Q[j]); printf("\n"); fflush(stdout); return 0; }