We want to mention BamiTorabi who we thank for helping us with translating the problems and writing the tutorials, and also we apologize for div1 A2 and B hopefully you will forgive us :( .
Tutorial is loading...
Prepared by Mohammad.H915 Editorial by Mehrdad_Sohrabi
official solution
// In The Name Of Allah
#include <bits/stdc++.h>
#define ss second
#define ff first
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ret(n) return cout << n, 0
#define se(n) cout << setprecision(n) << fixed
#define pb push_back
#define ll long long
#define ld long double
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const int N = 3e5 + 100, OO = 1e9 + 7, T = 50, M = 1e9 + 7, P = 6151, SQ = 280, lg = 20;
typedef pair <int, int> pii;
void solve() {
int n, c0, c1, t;
string s;
cin >> n >> c0 >> c1 >> t >> s;
int ans = 0;
for(auto u : s) {
if(u == '0')
ans += min(c0, c1 + t);
else
ans += min(c1, c0 + t);
}
cout << ans << endl;
}
int32_t main() {
int t;
cin >> t;
while(t--)
solve();
return 0;
}
Tutorial is loading...
Prepared by Mohammad.H915 Editorial by Mehrdad_Sohrabi
official solution
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < int , int >
#define F first
#define S second
#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=2e5+100;
ll a[N];
int Main(){
ll n, k;
cin >> k >> n;
for (int i=1;i<=n*k;i++){
cin >> a[i];
}
ll x=(k+1)/2 - 1;
x = k - x;
ll z=n*k+1;
ll ans=0;
while(n--){
z-=x;
if (z<=0) break;
ans+=a[z];
}
cout << ans << endl;
}
int32_t main(){
ll t;
cin >> t;
while(t--){
Main();
}
}
Tutorial is loading...
Prepared by Mohammad.H915 Editorial by Mehrdad_Sohrabi
official solution
// In The Name Of Allah
#include <bits/stdc++.h>
#define ss second
#define ff first
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ret(n) return cout << n, 0
#define se(n) cout << setprecision(n) << fixed
#define pb push_back
#define ll long long
#define ld long double
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const int N = 200, OO = 1e9 + 7, T = 50, M = 1e9 + 7, P = 6151, SQ = 280, lg = 20;
typedef pair <int, int> pii;
char c[N][N];
bool cnt[N][N];
struct node {int x1, y1, x2, y2, x3, y3;} p[5];
vector <node> v;
void upd(int x, int y, int tp, bool is) {
if(is)
v.pb({x + p[tp].x1, y + p[tp].y1, x + p[tp].x2, y + p[tp].y2, x + p[tp].x3, y + p[tp].y3});
else
cnt[x + p[tp].x1][y + p[tp].y1] ^= 1, cnt[x + p[tp].x2][y + p[tp].y2] ^= 1, cnt[x + p[tp].x3][y + p[tp].y3] ^= 1;
}
void solve() {
int n, m, od = 0;
v.clear();
cin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> c[i][j];
if(c[i][j] == '1')
od++, cnt[i][j] = true;
else
cnt[i][j] = false;
}
}
if(od == 0) {
cout << 0 << endl;
return;
}
if(n == 1 || m == 1) {
cout << -1 << endl;
return;
}
for(int i = 1; i <= n - 2; i++) {
for(int j = 1; j <= m; j++) {
if(cnt[i][j]) {
if(j != m) {
v.pb({i, j, i + 1, j, i + 1, j + 1});
cnt[i][j] ^= 1, cnt[i + 1][j] ^= 1, cnt[i + 1][j + 1] ^= 1;
}
else {
v.pb({i, j, i + 1, j, i + 1, j - 1});
cnt[i][j] ^= 1, cnt[i + 1][j] ^= 1, cnt[i + 1][j - 1] ^= 1;
}
}
}
}
for(int i = 1; i <= m - 2; i++) {
if(cnt[n - 1][i]) {
v.pb({n - 1, i, n - 1, i + 1, n, i + 1});
cnt[n - 1][i] ^= 1, cnt[n - 1][i + 1] ^= 1, cnt[n][i + 1] ^= 1;
}
if(cnt[n][i]) {
v.pb({n, i, n - 1, i + 1, n, i + 1});
cnt[n][i] ^= 1, cnt[n - 1][i + 1] ^= 1, cnt[n][i + 1] ^= 1;
}
}
for(int msk = 0; msk < (1 << 4); msk++) {
for(int j = 0; j < 4; j++)
if(msk & (1 << j))
upd(n - 1, m - 1, j, 0);
if(!cnt[n - 1][m - 1] && !cnt[n - 1][m] && !cnt[n][m - 1] && !cnt[n][m]) {
for(int j = 0; j < 4; j++)
if(msk & (1 << j))
upd(n - 1, m - 1, j, 1);
break;
}
for(int j = 0; j < 4; j++)
if(msk & (1 << j))
upd(n - 1, m - 1, j, 0);
}
cout << (int)v.size() << endl;
for(auto u : v)
cout << u.x1 << " " << u.y1 << " " << u.x2 << " " << u.y2 << " " << u.x3 << " " << u.y3 << endl;
}
int32_t main(){
use_fast;
p[0] = {0, 0, 0, 1, 1, 0}, p[1] = {0, 1, 0, 0, 1, 1}, p[2] = {1, 0, 1, 1, 0, 0}, p[3] = {1, 1, 0, 1, 1, 0};
int t;
cin >> t;
while(t--)
solve();
return 0;
}
Tutorial is loading...
Prepared by AliShahali1382 Editorial by Amoo_Safar
official solution
// In The Name Of Allah
#include <bits/stdc++.h>
#define ss second
#define ff first
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define se(n) cout << setprecision(n) << fixed
#define pb push_back
//#define int long long
#define ld long double
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const int N = 1e5 + 100, OO = 1e9 + 7, T = 22, M = 1e9 + 7, P = 6151, SQ = 1300, lg = 22;
typedef pair <int, int> pii;
int mark[N], deg[N], ct[N];
bool ans[N], can[N];
vector <int> v[N], A;
vector <pii> ch[N];
bool cmp(int x, int y) {
return mark[x] < mark[y];
}
void solve() {
int n, m, k;
cin >> n >> m >> k;
A.clear();
for(int i = 0; i <= n; i++)
v[i].clear(), ch[i].clear(), mark[i] = deg[i] = ct[i] = 0, ans[i] = can[i] = false;
for(int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
v[x].pb(y);
v[y].pb(x);
}
if(k > 500) {
cout << -1 << endl;
return;
}
set <pii> st;
for(int i = 1; i <= n; i++)
st.insert({deg[i] = (int)v[i].size(), i});
int cnt = 1;
while((int)st.size()) {
pii p = *st.begin();
if(p.ff >= k) {
cout << 1 << " " << (int)st.size() << endl;
for(auto u : st)
cout << u.ss << " ";
cout << endl;
return;
}
else {
st.erase(p);
mark[p.ss] = cnt;
for(auto u : v[p.ss])
if(!mark[u])
st.erase({deg[u], u}), st.insert({--deg[u], u});
A.pb(p.ss);
}
cnt++;
}
for(auto i : A) {
int nxt = 0;
for(auto u : v[i])
if(mark[u] > mark[i])
ct[nxt++] = u, can[u] = true;
for(auto u : ch[i])
if(!can[u.ff])
ans[u.ss] = false;
for(int j = 0; j < nxt; j++)
can[ct[j]] = false;
if(nxt != k - 1)
continue;
ans[i] = true;
sort(ct, ct + nxt, cmp);
for(int j = 0; j < nxt; j++)
for(int k = j + 1; k < nxt; k++)
ch[ct[j]].pb({ct[k], i});
}
for(auto i : A) {
if(!ans[i])
continue;
cout << 2 << endl;
cout << i << " ";
for(auto u : v[i])
if(mark[u] > mark[i])
cout << u << " ";
cout << endl;
return;
}
cout << -1 << endl;
return;
}
int32_t main() {
use_fast;
int t;
cin >> t;
while(t--)
solve();
return 0;
}
Tutorial is loading...
prepared by Mehrdad_Sohrabi Editorial by Mehrdad_Sohrabi
official solution
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=200010, LOG=20;
ll n, m, k, u, v, x, y, t, a, b, ans;
ll A[MAXN];
ll seg[MAXN<<2], lazy[MAXN<<2];
int Mn[MAXN<<2], Mx[MAXN<<2];
void Build(int id, int tl, int tr){
if (tr-tl==1){
Mn[id]=Mx[id]=seg[id]=A[tl];
return ;
}
int mid=(tl+tr)>>1;
Build(id<<1, tl, mid);
Build(id<<1 | 1, mid, tr);
Mn[id]=min(Mn[id<<1], Mn[id<<1 | 1]);
Mx[id]=max(Mx[id<<1], Mx[id<<1 | 1]);
seg[id]=seg[id<<1] + seg[id<<1 | 1];
}
inline void add_lazy(int id, int len, ll val){
Mn[id]=val;
Mx[id]=val;
lazy[id]=val;
seg[id]=len*val;
}
inline void shift(int id, int tl, int tr){
if (!lazy[id]) return ;
int mid=(tl+tr)>>1;
add_lazy(id<<1, mid-tl, lazy[id]);
add_lazy(id<<1 | 1, tr-mid, lazy[id]);
lazy[id]=0;
}
void Maximize(int id, int tl, int tr, int pos, ll val){
if (pos<=tl || val<=Mn[id]) return ;
if (tr<=pos && Mx[id]<=val){
add_lazy(id, tr-tl, val);
return ;
}
shift(id, tl, tr);
int mid=(tl+tr)>>1;
Maximize(id<<1, tl, mid, pos, val);
Maximize(id<<1 | 1, mid, tr, pos, val);
Mn[id]=min(Mn[id<<1], Mn[id<<1 | 1]);
Mx[id]=max(Mx[id<<1], Mx[id<<1 | 1]);
seg[id]=seg[id<<1] + seg[id<<1 | 1];
}
int BS1(int id, int tl, int tr, int pos, ll val){
if (tr<=pos || val<Mn[id]) return tr;
if (tr-tl==1) return tl;
shift(id, tl, tr);
int mid=(tl+tr)>>1, tmp=BS1(id<<1, tl, mid, pos, val);
if (tmp==mid) return BS1(id<<1 | 1, mid, tr, pos, val);
return tmp;
}
int BS2(int id, int tl, int tr, ll val){
if (seg[id]<=val) return tr;
if (tr-tl==1) return tl;
shift(id, tl, tr);
int mid=(tl+tr)>>1, tmp=BS2(id<<1, tl, mid, val);
if (tmp<mid) return tmp;
return BS2(id<<1 | 1, mid, tr, val-seg[id<<1]);
}
ll Get(int id, int tl, int tr, int l, int r){
if (r<=tl || tr<=l) return 0;
if (l<=tl && tr<=r) return seg[id];
shift(id, tl, tr);
int mid=(tl+tr)>>1;
return Get(id<<1, tl, mid, l, r) + Get(id<<1 | 1, mid, tr, l, r);
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin>>n>>m;
for (int i=1; i<=n; i++) cin>>A[i];
Build(1, 1, n+1);
while (m--){
cin>>t>>x>>y;
if (t==1) Maximize(1, 1, n+1, x+1, y);
else{
ans=0;
while (1){
x=BS1(1, 1, n+1, x, y);
if (x==n+1) break ;
ll val=y+Get(1, 1, n+1, 1, x);
int xx=BS2(1, 1, n+1, val);
// buy [x, xx)
ans+=xx-x;
y-=Get(1, 1, n+1, x, xx);
x=xx;
}
cout<<ans<<"\n";
}
}
return 0;
}
Tutorial is loading...
prepared by Mehrdad_Sohrabi Editorial by Mehrdad_Sohrabi
official solution
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int MAXN=505, LOG=20;
ll n, m, k, u, v, x, y, t, a, b, ans, mod;
ll dp1[MAXN], dp2[MAXN];
ll dp3[MAXN][MAXN], dp4[MAXN][MAXN];
ll C[MAXN][MAXN];
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin>>n>>m>>mod;
for (int i=0; i<MAXN; i++){
C[i][0]=C[i][i]=1;
for (int j=1; j<i; j++) C[i][j]=(C[i-1][j] + C[i-1][j-1])%mod;
}
dp1[0]=1;
for (int n=1; n<MAXN; n++){
for (int i=1; i<=n; i++) dp1[n]=(dp1[n] + dp1[i-1]*dp1[n-i]%mod*C[n-1][i-1])%mod;
dp1[n]=(n+1)*dp1[n]%mod;
for (int i=1; i<=n; i++){
dp2[n]=(dp2[n] + (n+1)*C[n-1][i-1]%mod*((dp1[i-1]*dp2[n-i] + dp2[i-1]*dp1[n-i])%mod))%mod;
dp2[n]=(dp2[n] + C[n-1][i-1]*dp1[i-1]%mod*dp1[n-i]%mod*((i*(i-1)/2+(n-i)*(n-i+1)/2)%mod))%mod;
}
}
dp3[0][0]=1;
for (int n=1; n<MAXN; n++){
for (int m=0; m<n; m++){
dp3[n][m]=dp3[n-1][m];
dp4[n][m]=dp4[n-1][m];
for (int i=1; i<=m; i++){
dp3[n][m]=(dp3[n][m] + dp3[n-i-1][m-i]*dp1[i]%mod*C[m][i])%mod;
dp4[n][m]=(dp4[n][m] + dp3[n-i-1][m-i]*dp2[i]%mod*C[m][i])%mod;
dp4[n][m]=(dp4[n][m] + dp4[n-i-1][m-i]*dp1[i]%mod*C[m][i])%mod;
}
}
dp3[n][n]=dp1[n];
dp4[n][n]=dp2[n];
}
cout<<dp4[n][m]<<"\n";
return 0;
}
O(n2) solution
// And you curse yourself for things you never done
// Shayan.P 2020-08-29
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 510, inf = 1e9 + 10, mod=1e9+7;
ll n, m;
ll Pow(ll a, ll b){
b = (b + (mod-1)) % (mod-1); // to handle b == -1
int ans=1;
for(; b; b>>=1, a=a*a%mod) if (b&1) ans=ans*a%mod;
return ans;
}
inline void add(ll &a, ll b){
a = (a + b) % mod;
}
ll fac[maxn], ifac[maxn];
ll C(ll n, ll k){
if (n<k || k<0) return 0;
return fac[n]*ifac[k]%mod*ifac[n-k]%mod;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
fac[0] = 1;
for(int i = 1; i < maxn; i++) fac[i]=fac[i-1]*i%mod;
ifac[maxn-1] = Pow(fac[maxn-1], mod-2);
for(int i = maxn-2; i >= 0; i--) ifac[i]=ifac[i+1]*(i+1)%mod;
cin >> n >> m;
++n; //!
int ans = 0;
for(ll bef = 0; bef < m; bef++){
for(ll w = 1; w + bef < m; w++){ // corner case : bef == 0
ll cnt1=Pow(w+1, w-1)*Pow(2, w)%mod;
ll cnt2=Pow(n-w-1, bef-1)*Pow(2, bef)%mod*(n-w-1-bef)%mod;
ll cnt=cnt1*cnt2%mod*C(w+bef, bef)%mod;
ll score=w*(w+1)%mod*n%mod;
ll after=Pow(n, m-bef-w-1)*Pow(2, m-bef-w-1) % mod;
ans=(ans + cnt*score%mod*after) % mod;
}
}
cout << 1ll * (n-m) * ans % mod * Pow(n, -1) % mod << "\n";
return 0;
}
Tutorial is loading...
Prepared by AliShahali1382 Editorial by AliShahali1382
official solution
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=400010, LOG=30;
int n, m, k, u, v, x, y, t, a, b, root, ans;
pii A[MAXN], V[MAXN];
int par[MAXN], sum[MAXN];
bool is[MAXN];
vector<int> G[MAXN], grundy;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int GetH(pii p){ return p.first+p.second;}
inline pii GetPar(pii p, int k){
int x=p.first, y=p.second;
while (k){
int xx=(x&-x), yy=(y&-y);
if (!xx) xx=2*inf;
if (!yy) yy=2*inf;
int tmp=min(k, min(xx, yy));
k-=tmp;
if (xx<yy) x-=tmp;
else y-=tmp;
}
return {x, y};
}
inline int Zone(pii p, int n){
if (p.first&(1<<(n-1))) return 2;
if (p.second&(1<<(n-1))) return 1;
return 0;
}
void dfs_order(vector<pii> &vec, int n=LOG) {
if (n==0 || vec.size()==0) return ;
vector<pii> v[3];
for (pii p:vec) {
int z=Zone(p, n);
p.first&=(1<<(n-1))-1;
p.second&=(1<<(n-1))-1;
v[z].pb(p);
}
vec.clear();
for (int i:{0, 1, 2}) dfs_order(v[i], n-1);
for (pii p:v[0]) if (!p.first) vec.pb(p);
for (pii p:v[1]) vec.pb({p.first, p.second|(1<<(n-1))});
for (pii p:v[0]) if (p.first) vec.pb(p);
for (pii p:v[2]) vec.pb({p.first|(1<<(n-1)), p.second});
}
pii Lca(pii u, pii v, int n=LOG) {
if (n==0) return {0, 0};
int zu = Zone(u, n), zv = Zone(v, n);
if (zu > zv) swap(u, v), swap(zu, zv);
u.first&=(1<<(n-1))-1;
u.second&=(1<<(n-1))-1;
v.first&=(1<<(n-1))-1;
v.second&=(1<<(n-1))-1;
if (zu == 1 && zv == 2) return {0, 0};
if (zu == 2 && zv == 2){
pii A = Lca(u, v, n-1);
return {A.first+(1<<(n-1)), A.second};
}
if (zu == 1 && zv == 1) {
pii A = Lca(u, v, n-1);
return {A.first, A.second+(1<<(n-1))};
}
if (zv == 1) return Lca(u, {0, (1<<(n-1))-1}, n-1);
if (zv == 2) return Lca(u, {(1<<(n-1))-1, 0}, n-1);
return Lca(u, v, n-1);
}
inline int GetId(pii p){
return lower_bound(V, V+n, p)-V;
}
inline bool IsPar(pii u, pii v){
if (GetH(u)>GetH(v)) return 0;
return GetPar(v, GetH(v)-GetH(u))==u;
}
int dfs(int node){
for (int v:G[node]) sum[node]+=dfs(v);
return sum[node];
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
vector<pii> vec;
cin>>m;
for (int i=0; i<2*m; i++) cin>>A[i].first>>A[i].second, vec.pb(A[i]);
sort(all(vec));
vec.resize(unique(all(vec))-vec.begin());
dfs_order(vec);
for (int i=vec.size()-1; i; i--) vec.pb(Lca(vec[i], vec[i-1]));
sort(all(vec));
vec.resize(unique(all(vec))-vec.begin());
dfs_order(vec);
n=vec.size();
debug("sorted")
for (int i=0; i<n; i++) V[i]=vec[i];
sort(V, V+n);
vector<int> stk={root=GetId(vec[0])};
for (int i=1; i<n; i++){
int v=GetId(vec[i]);
while (!IsPar(V[stk.back()], V[v])) stk.pop_back();
par[v]=stk.back();
G[stk.back()].pb(v);
stk.pb(v);
}
for (int i=0; i<2*m; i+=2){
int u=GetId(A[i]), v=GetId(A[i+1]), lca=GetId(Lca(A[i], A[i+1]));
sum[u]++;
sum[v]++;
sum[lca]-=2;
is[lca]=1;
}
dfs(root);
for (int v=0; v<n; v++){
if (sum[v]){
grundy.pb(GetH(V[par[v]])+1);
grundy.pb(GetH(V[v])+1);
}
else if (is[v]){
grundy.pb(GetH(V[v]));
grundy.pb(GetH(V[v])+1);
}
}
sort(all(grundy));
vec.clear();
int last=-1;
for (int x:grundy){
if (last==-1){
if (vec.empty() || vec.back().second<x) last=x;
else{
last=vec.back().first;
vec.pop_back();
}
}
else{
if (last<x) vec.pb({last, x});
last=-1;
}
}
ans=2*vec.size();
if (ans && vec[0].first==0) ans--;
cout<<ans<<"\n";
return 0;
}
