#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;
}
