#include "september.h"
//#include "stub.cpp"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<vector<int>> adj;
vector<ll> wt;
vector<vector<bool>> visited;
vector<ll> val;
vector<ll> par_val;
vector<ll> hsh;
random_device rd;
int n, m;
mt19937_64 rng(rd());
uniform_int_distribution<ll> zw(LLONG_MIN, LLONG_MAX);
void dfs(int node, int id, int par)
{
visited[id][node] = true;
for (auto i : adj[node])
{
if (i == par) continue;
if (visited[id][i])
{
par_val[id] ^= wt[i];
continue;
}
dfs(i, id, node);
}
}
bool add_val(int c, vector<int> &F, vector<vector<int>> &S)
{
for (int i = 0; i < m; i++)
{
// cout << "zw";
val[i] ^= hsh[S[i][c]];
if (visited[i][S[i][c]]) continue;
else
{
par_val[i] ^= wt[S[i][c]];
dfs(S[i][c], i, F[S[i][c]]);
}
}
for (int i = 0; i < m; i++)
{
if (par_val[i] != val[i]) return false;
}
// cout << "zw";
for (int i = 0; i < m; i++)
{
if (val[i] != val[0]) return false;
}
return true;
}
int solve(int N, int M, vector<int> F, vector<vector<int>> S)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
n = N;
m = M;
hsh.clear();
hsh.resize(N);
adj.clear(); wt.clear(); visited.clear(); val.clear(); par_val.clear();
adj.resize(N); wt.resize(N); visited.resize(M, vector<bool>(N)); val.resize(M);
par_val.resize(M);
for (int i = 0; i < N; i++) wt[i] = zw(rng);
for (int i = 1; i < N; i++)
{
// cout << "zw";
adj[F[i]].emplace_back(i);
adj[i].emplace_back(F[i]);
}
for (int i = 0; i < N; i++)
{
hsh[i] = wt[i];
}
for (int i = 0; i < N; i++)
{
for (auto j : adj[i])
{
if (j == F[i]) continue;
hsh[i] ^= wt[j];
}
}
// cout << "zw";
int ans = 0;
for (int i = 0; i < N - 1; i++) ans += add_val(i, F, S);
return ans;
}
