#include <bits/stdc++.h>
#include <complex>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "september.h"
using namespace std;
using namespace __gnu_pbds;
#define ll long long
const ll INF = 9e18;
const ll NEGINF = -INF;
const ll MOD = 998244353;
typedef tree<ll,null_type,greater_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> pbds;
ll binpow(ll a, ll b) {
ll res = 1;
while (b > 0) {
if (b & 1) res = (res * a) % MOD;
a = (a * a) % MOD;
b >>= 1;
}
return res;
}
ll modInverse(ll n) {
return binpow(n, MOD - 2);
}
struct COMB{
vector<ll> fact, invFact;
void init(ll n) {
fact.resize(n + 1);
invFact.resize(n + 1);
fact[0] = 1;
for (int i = 1; i <= n; i++) fact[i] = (fact[i - 1] * i) % MOD;
invFact[n] = modInverse(fact[n]);
for (int i = n - 1; i >= 0; i--) invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
}
ll ncr(ll n, ll r) {
if (r < 0 || r > n) return 0;
return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}
ll npr(ll n, ll r) {
if (r < 0 || r > n) return 0;
return fact[n] * invFact[n - r] % MOD;
}
};
struct LCA {
ll n, LOG;
vector<ll> depth;
vector<vector<ll>> dp;
void init(vector<vector<ll>> &adj, ll _n) {
n = _n;
LOG = ceil(log2(n)) + 1;
depth.assign(n, 0);
dp.assign(n, vector<ll>(LOG));
dfs(0, 0, adj);
}
void dfs(ll u, ll p, vector<vector<ll>> &adj) {
dp[u][0] = p;
for (int j = 1; j < LOG; j++) {
dp[u][j] = dp[dp[u][j - 1]][j - 1];
}
for (auto v : adj[u]) {
if (v != p) {
depth[v] = depth[u] + 1;
dfs(v, u, adj);
}
}
}
ll kth_ancestor(ll node, ll k) {
for (int j = 0; j < LOG; j++) {
if (k & (1LL << j)) {
node = dp[node][j];
}
}
return node;
}
ll lca(ll a, ll b) {
if (depth[a] < depth[b]) swap(a, b);
a = kth_ancestor(a, depth[a] - depth[b]);
if (a == b) return a;
for (int j = LOG - 1; j >= 0; j--) {
if (dp[a][j] != dp[b][j]) {
a = dp[a][j];
b = dp[b][j];
}
}
return dp[a][0];
}
};
struct DSU{
vector<ll> parent;
vector<ll> size;
void init(ll n){
parent.resize(n+1);
size.assign(n+1,1);
for(int i = 0; i <= n; i++){
parent[i] = i;
}
}
ll find(ll v){
if(v==parent[v]) return v;
return parent[v] = find(parent[v]);
}
void unite(ll a, ll b){
a = find(a);
b = find(b);
if(a!=b){
if(size[a]>size[b]){
size[a]+=size[b];
parent[b] = a;
}else{
size[b]+= size[a];
parent[a] = b;
}
}
}
};
struct range_segtree{
vector<ll> seg_tree;
vector<ll> lazy;
void init(ll n){
seg_tree.assign(4*n,0);
lazy.assign(4*n,0);
}
void update(ll start, ll end, ll val, ll i, ll l, ll r){
if(lazy[i]){
seg_tree[i] += lazy[i];
if(l!=r){
lazy[2*i+1] += lazy[i];
lazy[2*i+2] += lazy[i];
}
lazy[i] = 0;
}
if(l>end||r<start) return;
if(l>=start && r<=end){
seg_tree[i]+= val;
if(l!=r){
lazy[2*i+1]+=val;
lazy[2*i+2]+=val;
}
}else{
ll mid = (r+l)/2;
update(start,end,val,2*i+1, l,mid);
update(start,end,val,2*i+2, mid+1,r);
seg_tree[i] = seg_tree[2*i+1]+seg_tree[2*i+2];
}
}
ll query(ll start, ll end, ll i, ll l, ll r){
if(lazy[i]){
seg_tree[i] += lazy[i];
if(l!=r){
lazy[2*i+1] += lazy[i];
lazy[2*i+2] += lazy[i];
}
lazy[i] = 0;
}
if(l>end||r<start) return 0;
if(l>=start && r<=end){
return seg_tree[i];
}else{
ll mid = (r+l)/2;
return query(start,end,2*i+1,l,mid)+query(start,end,2*i+2,mid+1,r);
}
}
};
struct segtree{
vector<ll> seg_tree;
ll n;
segtree(ll n) : n(n){
seg_tree.resize(2*n);
}
void build(vector<ll> &arr){
for(int i=0; i < n; i++){
seg_tree[i+n] = arr[i];
}
for(int i = n-1; i>0; i--){
seg_tree[i] = max(seg_tree[i<<1],seg_tree[i<<1|1]);
}
}
ll query(ll l, ll r){
ll res = NEGINF;
for(l+=n, r+=n+1; l<r; l>>=1, r>>=1){
if(r&1) res = max(res,seg_tree[--r]);
if(l&1) res = max(res,seg_tree[l++]);
}
return res;
}
};
struct sparse_tables{
vector<vector<ll>> table;
sparse_tables(vector<ll> &arr) : table(__lg(arr.size())+1,arr){
for(int i = 1; i < table.size(); i++){
for(int j = 0; j + (1<<i)<=arr.size(); j++){
table[i][j] = max(table[i-1][j],table[i-1][j+(1<<(i-1))]);
}
}
}
ll query(ll l, ll r){
ll k = __lg(r-l+1);
return max(table[k][l],table[k][r-(1<<k)+1]);
}
};
void dfs(ll node, ll parent, vector<vector<int>> &adj, multiset<ll> &ms,vector<bool> &dead){
dead[node] = true;
ms.insert(node);
for(auto &v: adj[node]){
if(v!=parent && !dead[v]){
dfs(v,node,adj,ms,dead);
}
}
}
int solve(int N, int M, vector<int> F, vector<vector<int>> S) {
ll k = 0;
ll n = N;
ll m = M;
vector<ll> freq(n);
multiset<ll> ms;
vector<vector<int>> adj(n);
for(int i = 1; i<n; i++){
adj[i].push_back(F[i]);
adj[F[i]].push_back(i);
}
vector<bool> dead(n,false);
for(int j = 0; j <N-1; j++){
for(int i = 0; i < M; i++){
freq[S[i][j]]++;
if(!dead[S[i][j]]){
dfs(S[i][j],F[S[i][j]],adj,ms,dead);
}
if(freq[S[i][j]]==M){
ms.erase(S[i][j]);
}
}
if(ms.size()==0){
k++;
}
}
return (int)k;
}
