#include #include #include using namespace std; typedef long long int LL; typedef pair Kongr; const int MAXN = 1003; const int MAXK = 5*MAXN; const LL INF = 9223372036854775807LL; bool vis[MAXK]; int T[MAXK], P[MAXK], lenC[MAXK], conn[MAXK], parent[MAXK], N, numConn = 0; LL d[5][MAXK]; LL Gcd(LL x, LL y) { return (y == 0) ? x : Gcd(y, x%y); } LL GcdPro(LL x, LL y, LL &k, LL &l) { if (y == 0) { k = 1; l = 0; return x; } LL D = GcdPro(y, x%y, l, k); l -= (x/y)*k; return D; } Kongr equality(LL a, LL b, LL M) { LL k, l, D = GcdPro(a, M, k, l); if (b%D != 0) return Kongr(-1, -1); M /= D; a /= D; b /= D; k = (k%M+M)%M; b = (b*k%M+M)%M; return make_pair(b, M); } Kongr equalities(vector &K) { Kongr res = Kongr(0, 1); for (int i = 0; i < (int)K.size(); i++) { Kongr r = equality(res.second, K[i].first-res.first, K[i].second); if (r.first == -1) return r; res = Kongr(res.second*r.first+res.first, res.second*r.second); res.first %= res.second; } return res; } void Mark(int u, int lenCycle, int started) { //printf("Mark(%d, %d)\n", u, lenCycle); lenCycle++; lenC[u] = lenCycle; while (d[started][u] > 0) { u = parent[u]; lenC[u] = lenCycle; } } void Dfs(int u, int idConn, int started) { //printf("Dfs(%d, %d, %d)\n", u, idConn, started); vis[u] = true; conn[u] = idConn; if (!vis[T[u]]) { parent[T[u]] = u; d[started][T[u]] = d[started][u]+1; Dfs(T[u], idConn, started); } else Mark(u, d[started][u], started); } LL Check(int pl) { int pos[5] = {2*pl, 2*pl+1, 2*N+2*pl, 2*N+2*pl+1, 4*N+pl}; int tt[5] = {0, 1, 2, 3, 4}; LL resulto = INF; do { bool ok = true; //printf("check_player(%d)\n", pl); vector toCheck; for (int i = 0; i < 5; i++) { toCheck.push_back(Kongr(d[tt[i]][pos[i]], lenC[pos[i]])); //printf("%lld %lld\n", toCheck[i].first, toCheck[i].second); if ((toCheck[i].second == 0) || (toCheck[i].first == INF)) ok = false; } if (!ok) continue; //printf("checking player %d, perm %d %d %d %d %d\n", pl, tt[0], tt[1], tt[2], tt[3], tt[4]); //printf("kong\n"); //for (int i = 0; i < 5; i++) // printf("%lld %lld\n", toCheck[i].first, toCheck[i].second); Kongr resso = equalities(toCheck); if (resso.first != -1) { resulto = min(resulto, resso.first); // debug // printf("checking player %d, perm %d %d %d %d %d\n", pl, tt[0], tt[1], tt[2], tt[3], tt[4]); //printf("kong\n"); //for (int i = 0; i < 5; i++) // printf("%lld %lld\n", toCheck[i].first, toCheck[i].second); } } while (next_permutation(tt, tt+5)); return resulto; } int main() { while (true) { numConn = 0; scanf("%d", &N); if (N == 0) return 0; for (int i = 0; i < 5*N; i++) { scanf("%d", &P[i]); P[i]--; } int pos = 5*N-1; for (int pl = N-1; pl >= 0; pl--) { T[4*N+pl] = pos--; T[2*N+2*pl+1] = pos--; T[2*N+2*pl] = pos--; T[2*pl+1] = pos--; T[2*pl] = pos--; } for (int i = 0; i < 5; i++) { int pp = -1; for (int j = 0; j < 5*N; j++) if (P[j] == i) { pp = j; break; } fill(vis, vis+5*N, false); fill(d[i], d[i]+5*N, INF); d[i][pp] = 0; Dfs(pp, numConn++, i); } //for (int i = 0; i < 5*N; i++) // printf("%d: T = %d, P = %d, d = {%lld,%lld,%lld,%lld,%lld}, lenCycle = %d\n", i, T[i], P[i], d[0][i], d[1][i], d[2][i], d[3][i], d[4][i], lenC[i]); int winnPl = -1; LL res = INF, moves; for (int pl = 0; pl < N; pl++) if ((moves = Check(pl)) < res) { winnPl = pl; res = moves; } if (winnPl == -1) printf("Neverending game.\n"); else printf("Player %d wins game number %lld.\n", winnPl+1, res+1); } return 0; }