#include "september.h"
#include <vector>
#include <algorithm>
using namespace std;
#define MaxN 100500
int childCount[MaxN];
bool visited[MaxN];
vector<int> graph[MaxN];
void calc(int N, vector<int>& sequence, bool *validFlag, int *minPos, int *maxPos) {
for (int i = 0; i < N; i++)
visited[i] = false;
int activeCount = 0;
for (int i = 0; i < N - 1; i++) {
int node = sequence[i];
minPos[node] = min(minPos[node], i);
maxPos[node] = max(maxPos[node], i);
visited[node] = true;
activeCount += childCount[node];
for (int j = 0; j < graph[node].size(); j++)
if (visited[graph[node][j]])
activeCount--;
validFlag[i] &= (activeCount == 0);
}
}
int minPos[MaxN], maxPos[MaxN], diff[MaxN];
bool validFlag[MaxN];
int solve(int N, int M, vector<int> parents, vector<vector<int>> sequences) {
for (int i = 0; i < N; i++) {
graph[i].clear();
childCount[i] = 0;
}
for (int i = 1; i < N; i++) {
graph[parents[i]].push_back(i);
graph[i].push_back(parents[i]);
childCount[parents[i]]++;
}
for (int i = 0; i + 1 < N - 1; i++) {
validFlag[i] = true;
diff[i] = 0;
}
for (int i = 1; i < N; i++) {
minPos[i] = N + 1;
maxPos[i] = -1;
}
for (int i = 0; i < M; i++)
calc(N, sequences[i], validFlag, minPos, maxPos);
for (int id = 1; id < N; id++) {
diff[minPos[id]]++;
diff[maxPos[id]]--;
}
int ans = 1;
for (int i = 0; i + 1 < N - 1; i++) {
if (i > 0)
diff[i] += diff[i - 1];
if (!diff[i] && validFlag[i])
ans++;
}
return ans;
}
