#include "september.h" //ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39] //Author: Sazid Hasan #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef double dl; typedef vector<int> vi; typedef vector<vector<int>> vii; typedef vector<ll> vl; typedef vector<bool> vb; typedef pair<int,int> pii; typedef pair<ll, ll> pll; #define ff first #define ss second #define all(a) a.begin(),a.end() #define gcd(a,b) __gcd(a,b) #define lcm(a,b) (a*(b/gcd(a,b))) #define spc " " #ifdef ONLINE_JUDGE #define debarr(array) #define deb(x) #define del #else #define debarr(array) for(int w = 0; w < array.size(); w++) cerr << #array << "-" << w << " = " << array[w] << endl; #define deb(x) cerr << #x << " = " << x << endl; #define del cerr << '\n'; #endif const double PI = acos(-1); const int MOD = 1000000007; const int inf = (2147483647); int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) { vi till(N, -1); for(auto x: S){ for(int i = 0; i < N-1; i++) till[x[i]] = max(till[x[i]], i); } vi deg(N, 0); for(int i = 1; i < N; i++){ deg[F[i]]++; } queue<int> que; for(int i = 0; i < N; i++){ if(deg[i]==0) que.push(i); } while(!que.empty()){ int ff = que.front(); que.pop(); if(ff==0) continue; till[F[ff]] = max(till[F[ff]], till[ff]); deg[F[ff]]--; if(deg[F[ff]]==0) que.push(F[ff]); } int ptr = 0; int cnt = 0; while(ptr < N-1){ int now = ptr; while (now<=ptr) { for(int i = 0; i < M; i++){ ptr = max(ptr, till[S[i][now]]); } now++; } ptr++, cnt++; } return cnt; }