#include <bits/stdc++.h> using namespace std; #define fi first #define se second // edge[i][j] = 1 nếu có cung (i -> j) int edge[505][505]; // dp[l][r][x] : k = 0, đường đi tối đa từ l đến r, // trên cung theo hướng x (0 = chiều kim, 1 = ngược chiều) // dp1[l][r][x] : k <= 1, cho phép 1 giao cắt trên cung đó int dp[505][505][2]; int dp1[505][505][2]; // nx[i][0] = i+1 (mod n); nx[i][1] = i-1 (mod n) int nx[505][2]; int n, type; // giải cho đoạn (l -> r) theo hướng x void solve(int l, int r, int x) { // TH chọn cung trực tiếp (l -> r) if (edge[l][r]) { dp[l][r][x] = 1; // Sau đó tiếp tục đi từ r, sang phía còn lại (x^1), cho phép 1 giao cắt dp1[l][r][x] = 1 + dp1[r][nx[l][x]][x ^ 1]; } else { dp[l][r][x] = -n; dp1[l][r][x] = -n; } // Thử tách tại m: (l -> m) rồi (m -> r), không giao cắt (k = 0) for (int m = nx[l][x]; m != r; m = nx[m][x]) { dp[l][r][x] = max(dp[l][r][x], dp[l][m][x] + dp[m][r][x]); dp1[l][r][x] = max(dp1[l][r][x], dp[l][m][x] + dp1[m][r][x]); } // Cho phép 1 giao cắt ở đâu đó “đi vòng” qua nx[r][x^1] dp1[l][r][x] = max(dp1[l][r][x], dp1[l][nx[r][x ^ 1]][x]); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> type; for (int i = 0; i < n; i++) { int x; cin >> x; while (x != 0) { edge[i][x - 1] = 1; // input là 1-based cin >> x; } nx[i][0] = (i + 1) % n; // đi “xuôi” nx[i][1] = (i + n - 1) % n; // đi “ngược” } // DP theo độ dài d (cung ngắn hơn vòng tròn) for (int d = 1; d < n; d++) { for (int l = 0, r = (l + d) % n; l < n; l++, r = nx[r][0]) { solve(l, r, 0); solve(r, l, 1); } } // ans = {số cạnh tối đa, điểm bắt đầu 1-based} pair<int,int> ans = { -1, 0 }; // Trường hợp k = 0: chỉ dùng dp1 (đã include k = 0) trên mọi (l,r,x) for (int l = 0; l < n; l++) { for (int r = 0; r < n; r++) { for (int x = 0; x < 2; x++) { ans = max(ans, { dp1[l][r][x], l + 1 }); } } } // Nếu type = 1 thì cho phép thêm cấu hình có đúng 1 giao cắt “đặc biệt” if (type) { for (int l = 0; l < n; l++) { for (int r = 0; r < n; r++) { for (int x = 0; x < 2; x++) { if (dp[l][r][x] <= 0) continue; // không có đường k=0 từ l->r int st = nx[r][x]; // tìm st sao cho có cung (st -> l) cắt được (l->r) while (st != l && edge[st][l] == 0) st = nx[st][x]; if (st == l) continue; // không tìm được // ed chạy từ sau st tới trước l theo hướng x for (int ed = nx[st][x]; ed != l; ed = nx[ed][x]) { if (edge[r][ed]) { // cung (r -> ed) là cung cắt // chọn tốt nhất giữa 2 phía sau khi cắt int tail = max( dp1[ed][nx[l][x ^ 1]][x], dp1[ed][nx[st][x]][x ^ 1] ); // dp[l][r][x]: đoạn k=0 từ l tới r // +1 cho (st->l), +1 cho (r->ed), +tail cho phần còn lại ans = max( ans, make_pair(tail + 1 + 1 + dp[l][r][x], st + 1) ); } } } } } } cout << ans.fi << "\n" << ans.se; return 0; }