#include "september.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 1; (i) <= (n); ++i)
#define forn(i, l, r) for(int i = (l); i <= (r); ++i)
#define ford(i, r, l) for(int i = (r); i >= (l); --i)
#define FOR(i, n) for(int i = 0; i < (n); ++i)
#define FORD(i, n) for(int i = ((n) - 1); i >= 0; --i)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define endl "\n"
#define task "note"
#define sz(a) int(a.size())
#define C(x, y) make_pair(x, y)
#define all(a) (a).begin(), (a).end()
#define bit(i, mask) (mask >> i & 1)
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
inline int readInt() {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong() {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}
const int MaxN = 1e5 + 3;
const int MaxM = 6;
const int p = 311;
vector<int> g[MaxN];
struct volunteers
{
int num_cc;
int del[MaxN];
int n;
int P[MaxN], cur_hash;
void init(int N)
{
n = N;
num_cc = 1;
FOR(i, N) del[i] = 0;
P[0] = 1;
rep(i, N) P[i] = P[i - 1] * p;
cur_hash = 0;
}
bool check() {return num_cc == 1;}
void add(int x)
{
del[x] = 1;
--num_cc;
for(int v : g[x])
num_cc += !del[v];
cur_hash += P[x];
}
} f[MaxM];
bool check(int M)
{
FOR(i, M) if(!f[i].check() || f[i].cur_hash != f[0].cur_hash) return 0;
return 1;
}
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S)
{
FOR(i, N) g[i].clear();
rep(i, N - 1) g[F[i]].pb(i), g[i].pb(F[i]);
FOR(i, M) f[i].init(N);
int res = 0;
FOR(i, N - 1)
{
FOR(j, M) f[j].add(S[j][i]);
if(check(M)) ++res;
}
return res;
}
