//                                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;
}

#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();
    }
}

//                             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;
}

//                             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;
}

#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;
}

#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;
}

// 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;
}

#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;
}