#include <iostream> #include <vector> #include <algorithm> using namespace std; const int MAXN = 1005; // 2 * 500 const int INF = 1e9; int N, K; vector<int> adj[MAXN]; // Danh sách kề xuôi vector<int> rev_adj[MAXN]; // Danh sách kề ngược (để tính g) // f[i][j]: Max đường đi bắt đầu tại i, gói gọn trong [i, j] // g[i][j]: Max đường đi kết thúc tại j, gói gọn trong [i, j] int f[MAXN][MAXN]; int g[MAXN][MAXN]; void solve() { cin >> N >> K; // Đọc dữ liệu for (int i = 0; i < N; ++i) { int v; while (cin >> v && v != 0) { v--; // Chuyển về 0-based // Thêm cạnh cho cả 2 vòng (0..N-1 và N..2N-1) để xử lý quay vòng adj[i].push_back(v); adj[i].push_back(v + N); adj[i + N].push_back(v + N); adj[i + N].push_back(v + 2 * N); rev_adj[v].push_back(i); rev_adj[v].push_back(i + N); rev_adj[v + N].push_back(i + N); rev_adj[v + N].push_back(i + 2 * N); // Chỉ cần đến 2N là đủ bao phủ } } // Sắp xếp danh sách kề để xử lý chặt chẽ hơn nếu cần (không bắt buộc nhưng tốt cho logic) for(int i=0; i<2*N; ++i) { sort(adj[i].begin(), adj[i].end()); sort(rev_adj[i].begin(), rev_adj[i].end()); } // Khởi tạo DP for (int i = 0; i < 2 * N; ++i) { for (int j = 0; j < 2 * N; ++j) { f[i][j] = -INF; g[i][j] = -INF; } f[i][i] = 0; g[i][i] = 0; } // Tính toán DP (Interval DP theo độ dài đoạn) for (int len = 1; len < N; ++len) { for (int i = 0; i < 2 * N; ++i) { int j = i + len; if (j >= 2 * N) break; // Tính f[i][j]: xuất phát từ i, đến k, rồi đi tiếp trong [k, j] // i -> k for (int k : adj[i]) { if (k > i && k <= j) { if (f[k][j] != -INF) { f[i][j] = max(f[i][j], 1 + f[k][j]); } } } // Tính g[i][j]: kết thúc tại j, trước đó là k, nằm trong [i, k] // k -> j for (int k : rev_adj[j]) { if (k >= i && k < j) { if (g[i][k] != -INF) { g[i][j] = max(g[i][j], 1 + g[i][k]); } } } } } int max_stages = 0; int best_start = 1; // Mặc định // Trường hợp K=0 (và nền tảng cho K=1) // Duyệt tất cả các cạnh u -> v làm cạnh đầu tiên for (int u = 0; u < N; ++u) { for (int v : adj[u]) { if (v > u && v < u + N) { // v nằm trong vòng đầu tiên sau u // Đường đi: u -> v -> ... (gói gọn trong [v, u+N]) if (f[v][u + N] != -INF) { int current_len = 1 + f[v][u + N]; if (current_len > max_stages) { max_stages = current_len; best_start = u + 1; } } } } } // Trường hợp K=1 (Xử lý cắt nhau) if (K == 1) { // Duyệt u (điểm đầu cạnh 1) và y (điểm đầu cạnh cắt) // Thứ tự trên vòng tròn: u < y < v < z < u+N for (int u = 0; u < N; ++u) { for (int y = u + 1; y < u + N; ++y) { // Tìm các v (u->v) và z (y->z) thỏa mãn y < v < z < u+N // Lấy danh sách candidate v: là neighbor của u nằm trong (y, u+N) vector<pair<int, int>> cand_v; for (int v : adj[u]) { if (v > y && v < u + N) { if (g[v][y] != -INF) { // Đường đi v...y phải tồn tại cand_v.push_back({v, g[v][y]}); } } } // Lấy danh sách candidate z: là neighbor của y nằm trong (y, u+N) vector<pair<int, int>> cand_z; for (int z : adj[y]) { if (z > y && z < u + N) { if (f[z][u + N] != -INF) { // Đường đi z... phải tồn tại cand_z.push_back({z, f[z][u + N]}); } } } if (cand_v.empty() || cand_z.empty()) continue; // Cần tìm max (val_v + val_z) sao cho v < z // Sử dụng kỹ thuật duyệt tuyến tính (Two Pointers / Suffix Max) // cand_z đã được sort tăng dần theo z do tính chất adj list (hoặc đã sort ở trên) // Precompute suffix max cho cand_z int sz_z = cand_z.size(); vector<int> suf_max_z(sz_z); suf_max_z[sz_z - 1] = cand_z[sz_z - 1].second; for (int i = sz_z - 2; i >= 0; --i) { suf_max_z[i] = max(suf_max_z[i + 1], cand_z[i].second); } int ptr_z = 0; for (auto p : cand_v) { int v_idx = p.first; int val_v = p.second; // Tìm z đầu tiên mà z > v_idx while (ptr_z < sz_z && cand_z[ptr_z].first <= v_idx) { ptr_z++; } if (ptr_z < sz_z) { // Tồn tại z > v, lấy max suffix int current_total = 1 + val_v + 1 + suf_max_z[ptr_z]; // 1 (u->v) + path(v..y) + 1 (y->z) + path(z..u) if (current_total > max_stages) { max_stages = current_total; best_start = u + 1; } } } } } } cout << max_stages << endl; cout << best_start << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); return 0; }