#include <bits/stdc++.h>
// #include <tr2/dynamic_bitset>
using namespace std;
// using namespace tr2;
#pragma GCC optimize("O3,unroll-loops,Ofast")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const long double eps = 1e-9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randgen(int left, int right) {
return uniform_int_distribution<int>(left, right)(rng);
}
long long randgenll(long long left, long long right) {
return uniform_int_distribution<long long>(left, right)(rng);
}
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
struct Mint
{
int val;
Mint(int x = 0)
{
val = x % mod;
}
Mint(long long x)
{
val = x % mod;
}
Mint operator+(Mint oth)
{
return val + oth.val;
}
Mint operator*(Mint oth)
{
return 1LL * val * oth.val;
}
Mint operator-(Mint oth)
{
return val - oth.val + mod;
}
Mint fp(Mint a, long long n){
Mint p = 1;
while(n){
if(n & 1){
p = p * a;
}
a = a * a;
n /= 2;
}
return p;
}
Mint operator/(Mint oth){
Mint invers = fp(oth, mod - 2);
return 1LL * val * invers.val;
}
friend ostream& operator << (ostream& os, const Mint& lol){
os << lol.val;
return os;
}
};
struct AINT{
vector<ll> aint;
vector<ll> lazy;
AINT(int n){
aint.assign(n * 4 + 1,-1e9);
//lazy.assign(n * 4 + 1, -1);
}
void update(int v, int tl, int tr, int pos, int val){
if(tl == tr){
aint[v] = val;
return;
}
int tm = (tl + tr) / 2;
if(pos <= tm) update(v * 2, tl ,tm, pos, val);
else update(v * 2 + 1, tm + 1, tr, pos,val);
aint[v] = max(aint[v * 2], aint[v * 2 + 1]);
}
int query(int v, int tl, int tr, int l, int r){
int tm = (tl + tr) / 2;
if(l <= tl && r >= tr) return aint[v];
if(l > tr || r < tl) return -1e9;
return max(query(v * 2, tl, tm,l,r), query(v * 2 + 1, tm + 1, tr, l,r));
}
};
struct AIB{
vector<int> aib;
AIB(int n){
aib.assign(n + 1,0);
}
void update(int pos, int val){
for(; pos < aib.size(); pos += (pos & -pos)){
aib[pos] += val;
}
}
int query(int pos){
int pl = 0;
for(; pos > 0; pos -= (pos & -pos)) pl += aib[pos];
return pl;
}
};
int red = 0;
int ______________________________________________________________________________________________________________________________________________;
int solve(int n, int m, vector<int> f, vector<vector<int>> s){
vector<int> nrf(n + 1);
vector<vector<int>> liste(n + 1);
for(int i = 1; i < n; i++){
liste[i].push_back(f[i]);
liste[f[i]].push_back(i);
}
vector<int> leaves(n + 1);
function<void(int,int)> dfs = [&](int nod, int p){
for(auto i : liste[nod]){
if(i == p) continue;
nrf[nod]++;
// if(nod == 0){
// cout << i << " ";
// }
dfs(i,nod);
}
if(liste[nod].size() == 1 && nod != 0){
leaves[nod] = 1;
}
};
dfs(0,0);
map<set<int>,int> mp;
int ans = 0;
vector<set<int>> lp(m + 1);
for(int i = 0; i < n - 1; i++){
for(int l = 0; l < m; l++){
if(!leaves[s[l][i]]){
//cout << leaves[s[l][i]] << " ";
return 1;
}
lp[l].insert(s[l][i]);
mp[lp[l]]++;
if(mp[lp[l]] == m){
for(auto k : lp[l]){
if(--nrf[f[k]] == 0){
leaves[f[k]] = 1;
}
}
for(int k = 0; k < m; k++){
lp[k].clear();
}
ans++;
}
}
}
return ans;
}
// int32_t main(){
// cin.tie(0)->sync_with_stdio(0);
// // int t = 1;
// // if(red) cin >> t;
// // while(t--){
// // solve();
// // }
// cout << solve(5, 2, {-1, 0, 0, 1, 1}, {{1, 2, 3, 4}, {4, 1, 2, 3}});
// }
/*
4 1
0 0 1
dp[i][0] = s
*/
