#include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std; const int MAXN = 1005; // 2 * N const int INF = 1e9; int N, K; vector<int> adj[MAXN]; int dp[MAXN][MAXN][2]; // dp[i][j][0]: max path in range [i, j] starting at i // dp[i][j][1]: max path in range [i, j] starting at j // For K=1 specific calculation int memo_bonus[MAXN][MAXN][2]; int visited_bonus[MAXN][MAXN][2]; int bonus_token = 0; int W[MAXN]; // W[u] stores max extension from u crossing to the other side // Function to find max path in [L, R] starting at 'side' (0 for L, 1 for R) // that ends at some node u and adds W[u]. int solve_bonus(int L, int R, int side) { if (L == R) return W[L] > -INF ? W[L] : -INF; if (visited_bonus[L][R][side] == bonus_token) return memo_bonus[L][R][side]; int res = -INF; int u = (side == 0) ? L : R; // Option 1: Stop here if (W[u] > -INF) res = max(res, W[u]); // Option 2: Continue path for (int v : adj[u]) { if (v > L && v < R) { // Strict interior of [L, R] // Edge u -> v. // Split into [L, v] and [v, R]. // If we go L -> v (side 0), we are at v. v is R of [L, v] and L of [v, R]. // We can recurse into [L, v] (start at R) or [v, R] (start at L). int val_left = solve_bonus(L, v, 1); // inside [L, v], start v int val_right = solve_bonus(v, R, 0); // inside [v, R], start v int best_next = max(val_left, val_right); if (best_next > -INF) { res = max(res, 1 + best_next); } } } visited_bonus[L][R][side] = bonus_token; memo_bonus[L][R][side] = res; return res; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); if (!(cin >> N >> K)) return 0; for (int i = 0; i < N; ++i) { int v; while (cin >> v && v != 0) { v--; // 0-based // Add edges in doubled space to handle modular arithmetic easily // u -> v implies u -> v and u+N -> v+N (and potentially u -> v+N if v < u) // We normalize so v is in [u+1, u+N-1] // For u in [0, N-1] int target = v; if (target <= i) target += N; adj[i].push_back(target); adj[i + N].push_back(target + N); } } // Initialize DP for (int i = 0; i < 2 * N; ++i) { for (int j = 0; j < 2 * N; ++j) { dp[i][j][0] = dp[i][j][1] = -INF; } dp[i][i][0] = dp[i][i][1] = 0; } // Compute standard DP (K=0 logic) for (int len = 1; len < N; ++len) { for (int i = 0; i < 2 * N; ++i) { int j = i + len; if (j >= 2 * N) break; // dp[i][j][0]: start at i for (int k : adj[i]) { if (k > i && k <= j) { int val = 1 + max(dp[i][k][1], dp[k][j][0]); dp[i][j][0] = max(dp[i][j][0], val); } } // dp[i][j][1]: start at j // We need reverse edges for this, or just check 'k' neighbors // Since graph is directed, we check outgoing from j? // NO. The path starts at j. So we look for neighbors of j. // But problem input is "direct destinations FROM harbor". // So if path starts at j, we look at adj[j]. for (int k : adj[j]) { if (k >= i && k < j) { int val = 1 + max(dp[i][k][1], dp[k][j][0]); dp[i][j][1] = max(dp[i][j][1], val); } } } } int max_stages = 0; int start_harbor = 1; // Check K=0 solutions and base for K=1 // A path is defined by the first edge u -> v. // Length = 1 + max path from v inside [v, u+N] for (int u = 0; u < N; ++u) { for (int v : adj[u]) { if (v > u && v < u + N) { // Path starts u -> v. Next part in [v, u+N]. // We are at v. We can go L (towards v) or R (towards u+N)? // In [v, u+N], v is the left boundary. // So we need path starting at v inside [v, u+N]. // This is dp[v][u+N][0]. // Also need to check if we treat v as right boundary of [u, v]? // No, the remaining circle is [v, u+N]. int val = dp[v][u + N][0]; if (val > -INF) { if (1 + val > max_stages) { max_stages = 1 + val; start_harbor = u + 1; } } else { // Just the edge u->v if (1 > max_stages) { max_stages = 1; start_harbor = u + 1; } } } } } if (K == 1) { // Iterate all possible first edges S->T for (int i = 0; i < N; ++i) { // S = i for (int k : adj[i]) { // T = k if (k > i && k < i + N) { // Region 1 (Left): [i, k] // Region 2 (Right): [k, i + N] // 1. Calculate W[u] for all u inside (i, k) // W[u] = max over crossing edges u->v (v in Region 2) of (1 + PathFrom(v)) // PathFrom(v) in Region 2 is max(dp[k][v][1], dp[v][i+N][0]) // We only need to compute W for u in [i+1, k-1] vector<int> nodes_in_left; for (int u = i + 1; u < k; ++u) { W[u] = -INF; nodes_in_left.push_back(u); for (int v : adj[u]) { if (v > k && v < i + N) { // Crossing edge int path_from_v = -INF; // Option A: v goes towards k (Left in [k, v]) -> dp[k][v][1] // Option B: v goes towards i+N (Right in [v, i+N]) -> dp[v][i+N][0] path_from_v = max(dp[k][v][1], dp[v][i+N][0]); if (path_from_v > -INF) { W[u] = max(W[u], 1 + path_from_v); } else { W[u] = max(W[u], 1); // Edge exists but no further path } } } } // 2. Compute max path in [i, k] starting at k ending at some u with bonus W[u] // We use solve_bonus(i, k, 1) -> starts at k (Right side of [i, k]) bonus_token++; int bonus_path = solve_bonus(i, k, 1); if (bonus_path > -INF) { if (1 + bonus_path > max_stages) { max_stages = 1 + bonus_path; start_harbor = i + 1; } } } } } } cout << max_stages << endl; cout << start_harbor << endl; return 0; }