#pragma GCC optimize("Ofast", "O3")
#include "september.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#include <iostream>
#include <chrono>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
#define loop(x) for (ll i = 0; i < x; i++)
struct custom_hash {
static uint64_t splitmix64(uint64_t x);
size_t operator()(uint64_t x) const;
};
template <typename _Tp, typename Cm_fn=std::less<_Tp>>
using ordered_set = __gnu_pbds::tree<
_Tp, __gnu_pbds::null_type, Cm_fn, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update
>;
template <typename _Tp>
class Fenwick_Tree {
private:
std::vector<_Tp> Tree;
public:
void init() {
for (long long i = 1; i <= this->Tree.size(); i++) {
long long parent = i + (i & -i);
if (parent <= this->Tree.size()) {
this->Tree[parent - 1] += this->Tree[i - 1];
}
}
}
_Tp sum(long long l, long long r) {
long long sum = 0;
while (r > 0) {
sum += this->Tree[r - 1];
r -= (r & -r);
}
l--;
while (l > 0) {
sum -= this->Tree[l - 1];
l -= (l & -l);
}
return sum;
}
void update(long long index, long long difference) {
while (index <= this->Tree.size()) {
this->Tree[index - 1] += difference;
index += (index & -index);
}
}
Fenwick_Tree(const std::vector<_Tp> &array) {
this->Tree = array;
this->init();
}
};
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
map<ll, set<ll>> g {};
for (ll i = 1; i < N; i++) g[F[i]].insert(i);
ll i = 0;
set<ll> w{}; ll res = 0; vector<bool> visited(N, false);
for (ll j = 0; j < N - 1; j++) {
for (auto &v: S) {
w.insert(g[v[j]].begin(), g[v[j]].end());
if (!visited[v[j]]) w.insert(v[j]);
}
g[F[S[i][j]]].erase(S[i][j]);
w.erase(S[i][j]); visited[S[i][j]] = 1;
if (w.empty()) res++;
}
return res;
}
uint64_t custom_hash::splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t custom_hash::operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
