#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

template<typename T>
using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long
#define ull unsigned long long
#define pi pair<ll,ll>
#define pii pair<ll,pi>
#define inf 1000000000000000000
#define iinf -1000000000000000000
#define __   ios_base::sync_with_stdio(0);cin.tie();cout.tie();
#define MOD 1000000007
#define uu first
#define vv second
#define endl '\n'

pi operator+(pi a, ll x)     {return {a.uu + x, a.vv + x} ;}
pi operator- (pi a, ll x)     {return {a.uu - x, a.vv - x} ;}
pi operator* (pi a, ll x)     {return {a.uu * x, a.vv * x} ;}
pi operator+(pi x, pi y) { return {x.uu + y.uu,x.vv + y.vv} ;}
pi operator-(pi x,pi y) { return {x.uu - y.uu, x.vv - y.vv} ;}
pi operator*(pi x,pi y) { return {x.uu * y.uu , x.vv * y.vv} ;}
pi operator%(pi x,pi y) { return {x.uu % y.uu, x.vv % y.vv} ;}

const pi base = {103,101};

const pi  mod = {1000000021, 1e9 + 9 };

ll Set(ll N,ll pos){ return N=N | (1LL<<pos); }
ll reset(ll N,ll pos){ return N= N & ~(1LL<<pos); }
bool check(ll N,ll pos){ return (bool)(N & (1LL<<pos)); }

ll ar[]={0,0,1,-1};
ll br[]={1,-1,0,0};

///*******GEOMETRY**********///
double PI=acos(-1.0);

double gcd(double a,double b){
    return fabs(b)<1e-4?a:gcd(b,fmod(a,b));
}

///*******GEOMETRY**********///

ll sqrt_ (int64_t x) {
    int64_t y = sqrt(x);
    while (y * y > x) {
      --y;
    }
    while (y * y <= x) {
      ++y;
    }
    return y - 1;
}

ll bigmod(ll n,ll pow){
if(pow==0) return 1;
if(pow==1) return n%MOD;

ll ans=bigmod(n,pow/2);
ans=(ans*ans)%MOD;

if(pow%2==1){ans=(ans*n)%MOD;}
return ans%MOD;
}

ll fact[1000005];


ll nCr(ll n,ll r){

ll ans=fact[n];
ans=(ans*bigmod(fact[r],MOD-2))%MOD;
ans=(ans*bigmod(fact[n-r],MOD-2))%MOD;
return ans;
}

string s,s1,s2;
ll n,m;
ll arr[5000010];
ll brr[5000010];
vector<ll>v,v1;

map<ll,ll>mp;
ll vis[5000005];
const ll N = 40005;
vector<ll>gg[N];
ll match[N], dist[N];
ll idx;
bool bfs(){
    queue<ll>q;
    for(ll i=1;i<=idx;i++){
        if(match[i]==0){
            dist[i]=0;
            q.push(i);
        }
        else dist[i]=inf;
    }
    dist[0]=inf;

    while(!q.empty()){
        ll u=q.front();
        q.pop();
        if(u!=0){
            for(auto v:gg[u]){
                if(dist[match[v]]==inf){
                    dist[match[v]]=dist[u]+1;
                    q.push(match[v]);
                }
            }
        }
    }
    return (dist[0] != inf);
}

bool dfs(ll u){
    if(u!=0){
        for(auto v:gg[u]){
            if(dist[match[v]]==dist[u]+1){
                if(dfs(match[v])){
                    match[v]=u;
                    match[u]=v;
                    return true;
                }
            }
        }
        dist[u]=inf;
        return false;
    }
    return true;
}

ll max_match(){
    ll matching =0;
    while(bfs()){
        for(ll i=1;i<=idx;i++){
            if(match[i]==0&&dfs(i)) matching++;
        }
    }
    return matching;
}

// complexity: O(sqrt(V)*E).

int main()
{__
        ll i,j,a,b,c,d,e,f,g,x,y,z,t,k,l,r;
        fact[0]=1;

      //  for(i=1;i<=1000000;i++) fact[i]=(fact[i-1]*i)%MOD;
        ll ans=0,sum=0,temp;


}