#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxN = 500 + 5;
const ll inf64 = (ll)1e18;
ll n, k;
ll f1[maxN][maxN][2]; // for two‐segment DP (one crossing)
ll f2[maxN][maxN][2]; // for simple path DP (no crossing)
vector<ll> adj[maxN];
// Next harbor in circular order
ll nx(ll x) {
x++;
if (x > n) x -= n;
return x;
}
// is x strictly between st and en along the circle (counterclockwise)?
bool irg(ll st, ll en, ll x) {
if (st == en || en == nx(st)) return false;
if (st > en) return (x > st || x < en);
return (st < x && x < en);
}
// inrange depending on direction flag
bool inrange(ll st, ll en, bool dir, ll x) {
return dir ? irg(st, en, x) : irg(en, st, x);
}
// DP for one‐crossing case: you can switch to the other arc once
ll fin2d(ll st, ll en, bool dir) {
ll &res = f1[st][en][dir];
if (res != -1) return res;
res = 0;
for (ll i : adj[st]) {
if (!inrange(st, en, dir, i)) continue;
// either stay on this arc or switch arcs at i
res = max(res,
1 + max(
fin2d(i, en, dir),
fin2d(i, st, !dir)
)
);
}
return res;
}
// DP for classical no‐crossing: longest simple path from st to en along one arc
ll finz(ll st, ll en, bool dir) {
ll &res = f2[st][en][dir];
if (res != -1) return res;
if (st == en) return res = 1;
res = -inf64;
for (ll i : adj[st]) {
if (!inrange(st, en, dir, i)) continue;
ll tmp = finz(i, en, dir);
if (tmp > 0) res = max(res, tmp + 1);
}
return res;
}
// DP wrapper for one‐crossing: try a single cross after the first segment
ll fin1d(ll st, ll en, bool dir) {
ll ans = 0;
for (int mid = 1; mid <= n; mid++) {
if (!inrange(st, en, dir, mid)) continue;
ll prefix = finz(st, mid, dir);
if (prefix <= 0) continue;
for (ll nxt : adj[mid]) {
if (inrange(st, en, dir, nxt)) continue;
// cross at (mid -> nxt)
ans = max(ans, prefix + fin2d(nxt, st, dir));
ans = max(ans, prefix + fin2d(nxt, en, !dir));
}
}
return ans;
}
void solve() {
cin >> n >> k;
// read graph
for (int i = 1; i <= n; i++) {
adj[i].clear();
ll x;
while (cin >> x && x > 0) {
adj[i].push_back(x);
}
}
// init DP tables
memset(f1, -1, sizeof f1);
memset(f2, -1, sizeof f2);
ll bestLen = 0, bestStart = 1;
// try every possible first stage s->t
for (int s = 1; s <= n; s++) {
for (ll t : adj[s]) {
if (k == 0) {
// classical: one segment s->t + simple path back
for (int dir = 0; dir < 2; dir++) {
ll verts = finz(t, s, dir);
if (verts > 0) {
ll edges = 1 + (verts - 1);
if (edges > bestLen) {
bestLen = edges;
bestStart = s;
}
}
}
} else {
// one crossing allowed
for (int dir = 0; dir < 2; dir++) {
ll extra = fin1d(t, s, dir);
ll edges = 1 + extra;
if (edges > bestLen) {
bestLen = edges;
bestStart = s;
}
}
}
}
}
cout << bestLen << " " << bestStart << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
