1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include <bits/stdc++.h>
using namespace std;
const int LEN = 1e3 + 50;
int n, m, cnt, tot, ans, head[LEN], val[LEN], ind[LEN];
bool vis[LEN][LEN];
queue<int> q;
struct edge {
int to_, nxt_;
} e[(int)1e6 + 50];
void add(int u, int v) {
e[tot].nxt_ = head[u], e[tot].to_ = v;
head[u] = tot++;
}
void toposort() {
for (int i = 1; i <= n; ++i) {
if (ind[i] == 0) {
q.emplace(i);
val[i] = 1;
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; ~i; i = e[i].nxt_) {
int v = e[i].to_;
val[v] = max(val[v], val[u] + 1);
if (--ind[v] == 0) q.emplace(v);
}
}
for (int i = 1; i <= n; ++i) {
ans = max(ans, val[i]);
}
}
int main() {
memset(head, -1, sizeof(head));
int bg, ed, arr[LEN], used[LEN];
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
memset(arr, 0, sizeof(arr)), memset(used, 0, sizeof(used));
cin >> cnt;
for (int j = 1; j <= cnt; ++j) {
cin >> arr[j];
used[arr[j]] = 1;
}
bg = arr[1], ed = arr[cnt];
for (int u = bg; u <= ed; ++u) {
if (!used[u]) {
for (int v, k = 1; k <= cnt; ++k) {
v = arr[k];
if (!vis[u][v]) {
vis[u][v] = 1;
++ind[v];
add(u, v);
}
}
}
}
}
toposort();
cout << ans;
return 0;
}
|