class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回牛牛能喝的最多的酒
     * @param m int整型 酒单价
     * @param n int整型 牛牛的现金
     * @return int整型
     */
    int countWine(int m, int n) {
        // write code here
        int ans=n/m;
        int jp=ans,pg=ans;
        while (jp>=2||pg>=4){
            int te=pg/4;
            ans+=te;
            jp+=te;
            pg=pg%4+te;
            te=jp/2;
            ans+=te;
            jp=jp%2+te;
            pg+=te;
        }
        return ans;
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param x string字符串 
     * @return int整型
     */
    string t;
    bool che(int x){
        int te=0;
        int i=0;
        for(;i<t.length();++i){
            if (t[i]=='a') ++te;
            if (te==x) break;
        }
        if (i==t.length()) return 0;
        te=0;
        for(;i<t.length();++i){
            if (t[i]=='b') ++te;
            if (te==x) break;
        }
        if (i==t.length()) return 0;
        te=0;
        for(;i<t.length();++i){
            if (t[i]=='c') ++te;
            if (te==x) break;
        }
        if (i==t.length()) return 0;        
        return 1;
    }
    int Maximumlength(string x) {
        // write code here
        int n=x.length();
        int l=0;
        int r=n/3;
        int mid;
        t=x;
        while (l<r){
            mid=(l+r+1)>>1;
            if (che(mid)) l=mid;else r=mid-1;
        }
        return l*3;
    }
};

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    int Gameresults(int n, int p, int q) {
        // write code here
        if (p<q){
            return (n<=p)?1:-1;
        }
        if (p>q){
            return 1;
        }
        if (p==q){
            return (n%(p+1))?1:-1;
        }
        return 0;
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 节点个数
     * @param u int整型vector 
     * @param v int整型vector 
     * @return int整型
     */
    vector<int> e[110000];
    int d[110000],q[110000],he,ta,r1,r2,las[110000],dep[110000],ma;
    bool b[110000],ind[110000];
    void bfs(int st){
        q[he=ta=1]=st;
        d[st]=0;
        las[st]=0;
        memset(b,0,sizeof b);
        b[st]=1;
        while (he<=ta){
            int &x=q[he];
            for(int y:e[x]) if (!b[y]){
                b[y]=1;
                d[y]=d[x]+1;
                las[y]=x;
                q[++ta]=y;
            }
            ++he;
        }        
    }
    void dfs(int x,int fa){
        if (dep[x]==ma) ind[x]=1;
        for(int y:e[x]) if (y!=fa&&!ind[y]){
            dep[y]=dep[x]+1;
            dfs(y,x);
            if (ind[y]) ind[x]=1;
        }
    }
    int PointsOnDiameter(int n, vector<int>& u, vector<int>& v) {
        // write code here
        for(int i=0;i<u.size();++i){
            e[u[i]].push_back(v[i]);
            e[v[i]].push_back(u[i]);
        }
        bfs(1);
        r1=1;
        for(int i=2;i<=n;++i) if (d[i]>d[r1]) r1=i;
        bfs(r1);
        r2=1;
        for(int i=2;i<=n;++i) if (d[i]>d[r2]) r2=i;
        int te=r2;
        /*for(int i=0;i<=d[r2];++i){
            ind[te]=1;
            dep[te]=min(i,d[r2]-i);
            te=las[te];
        }
        for(int i=1;i<=n;++i) if (ind[i]){
            ma=dep[i];
            dep[i]=0;
            dfs(i,0);
        }*/
        int ans=0;
        //for(int i=1;i<=n;++i) if (dep[i]==d[r2]) ind[i]=1;
        for(int i=1;i<=n;++i) if (d[i]==d[r2]){
            te=i;
            while (te){
                if (ind[te]) break;
                ind[te]=1;
                te=las[te];
            }
        }
        for(int i=1;i<=n;++i) if (ind[i]) ++ans;
        //return d[5];
        return ans;
    }
};