#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<long long int, long long int>;
const int inf = numeric_limits<int>::max();
const ll INF = numeric_limits<ll>::max();
const char sp = ' ';
const char nl = '\n';
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S){
//root is 0
vector<vector<int> > adj(N); //children only
unordered_set<int> leafs;
vector<int> outdegree(N,0);
for(int i = 0; i < N; i++){
if(F[i] != -1){
adj[F[i]].push_back(i);
outdegree[F[i]]++;
}
}
for(int i = 0; i < N; i++){
if(adj[i].size() == 0 && i != 0){
leafs.insert(i);
}
}
vector<unordered_set<int> > leafnodes(M, leafs);
vector<bool> incompletes(M,false);
vector<vector<int> > outdegreelist(M, outdegree);
vector<vector<bool> > present(M, vector<bool>(N,true));
vector<unordered_set<int> > tofind(M);
vector<unordered_set<int> > segments(M); // tracks segments across all M
int count = 0;
for(int i = 0; i < N - 1; i++){
for(int m = 0; m < M; m++){
if(!incompletes[m]){
if(leafnodes[m].count(S[m][i])){
outdegreelist[m][F[S[m][i]]]--;
leafnodes[m].erase(S[m][i]);
present[m][S[m][i]] = false;
if(outdegreelist[m][F[S[m][i]]] == 0){
leafnodes[m].insert(F[S[m][i]]);
}
} else {
present[m][S[m][i]] = false;
for(int children: adj[S[m][i]]){
if(present[m][children]){
tofind[m].insert(children);
}
}
if(!tofind[m].empty()){
incompletes[m] = true;
}
}
} else {
if(leafnodes[m].count(S[m][i])){
outdegreelist[m][F[S[m][i]]]--;
leafnodes[m].erase(S[m][i]);
present[m][S[m][i]] = false;
if(outdegreelist[m][F[S[m][i]]] == 0){
leafnodes[m].insert(F[S[m][i]]);
}
if(tofind[m].count(S[m][i])){
tofind[m].erase(S[m][i]);
}
if(tofind[m].empty()){
incompletes[m] = false;
}
} else {
if(tofind[m].count(S[m][i])){
tofind[m].erase(S[m][i]);
}
present[m][S[m][i]] = false;
for(int children: adj[S[m][i]]){
if(present[m][children]){
tofind[m].insert(children);
}
}
if(tofind[m].empty()){
incompletes[m] = false;
}
}
}
segments[m].insert(S[m][i]);
}
bool okay = true;
//if segments of all M are the same
//if all not incomplete
for(int m = 0; m < M; m++){
if(incompletes[m]){
okay = false;
// cout << i << sp << "incomplete searchspace" << nl;
break;
}
if(!tofind[m].empty()){
okay = false;
// cout << i << sp << "need to find something pa" << nl;
break;
}
}
for(int m = 1; m < M; m++){
if(segments[0] != segments[m]){
okay = false;
// cout << i << sp << "unequal sets" << nl;
break;
}
}
if(okay){
for(int m = 0; m < M; m++){
segments[m].clear();
}
count++;
}
}
return count;
}
// int main(){
// // cout << solve(5, 1, {-1, 0, 0, 1, 2}, {{1,3,4,2}}) << nl;
// // cout << solve(5, 1, {-1, 0, 0, 1, 1}, {{4,3,1,2}}) << nl;
// // cout << solve(5, 2, {-1, 0, 0, 1, 1}, {{1, 2, 3, 4}, {4, 1, 2, 3}}) << nl;
// // cout << solve(3, 1, {-1, 0, 0}, {{1, 2}}) << nl;
// // cout << solve(7,1,{-1,0,0,1,1,2,2},{{2,6,5,3,1,4}}) << nl;
// // cout << solve(5, 1, {-1, 0, 0, 1, 1}, {{4, 1, 3, 2}}) << nl;
// // cout << solve(7,1,{-1,0,0,1,1,2,2},{{2,6,5,4,1,3}}) << nl;
// }
