int i,n;
int sum[1000005];
vector < int > a , c;
class Solution {
public:
    /**
     *
     * @param x string字符串
     * @return int整型
     */
    int Maximumlength(string x) {
       n=x.size();
        for(i=0;i<n;i++)
        {
            if(i!=0)sum[i]=sum[i-1];
            if(x[i]== 'a' )a.push_back(i);
            else if(x[i] =='c')c.push_back(i);
            else if(x[i] =='b' )sum[i]++;
        }
        reverse(c.begin(),c.end());
        int pos=0;
        for(i=0;i<a.size()&&i<c.size();i++)
        {
            if(c[i]<a[i])break;
            if(sum[c[i]]-sum[a[i]]<i+1)break;
            pos++;
        }
        return 3*pos;
    }
};

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
        int ans;
        if(p>q)ans=1;
        else if(q>p)
        {
            if(p>=n)ans=1;
            else ans=-1;
        }
        else
        {
            if(n%(p+1))ans=1;
            else ans=-1;
        }
        return ans;
    }
};

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param n int整型 节点个数
     * @param u int整型vector
     * @param v int整型vector
     * @return int整型
     */
    int dp[100005][3],mx,ans;
    vector<int>edge[100005];
    void dfs(int x,int fa) {
        for(int i = 0;i<(int)edge[x].size();i++) {
            int y = edge[x][i];
            if(y == fa) continue;
            dfs(y,x);
            if(dp[y][0] + 1 > dp[x][0]) {
                dp[x][1] = dp[x][0];
                dp[x][0] = dp[y][0] + 1;
            } else {
                dp[x][1] = max(dp[x][1],dp[y][0] + 1);
            }
        }
    }
    void dfs1(int x,int fa) {
        for(int i = 0;i<(int)edge[x].size();i++) {
            int y = edge[x][i];
            if(y == fa) continue;
            if (1 + dp[y][0]==dp[x][0]){
                dp[y][2] = max(dp[y][2],dp[x][1] + 1);
            }
            else {
                dp[y][2] = max(dp[y][2],dp[x][0] + 1);
            }
            dp[y][2] = max(dp[y][2],dp[x][2] + 1);
            dfs1(y,x);
        }
    }
    int PointsOnDiameter(int n, vector<int>& u, vector<int>& v) {
        // write code here
        memset(dp,0,sizeof(dp));
        for(int i = 0;i<n-1;i++) {
            edge[u[i]].push_back(v[i]);
            edge[v[i]].push_back(u[i]);
        }
        dfs(1,0);
        dfs1(1,0);
        for(int i =1;i<=n;i++) {
            mx = max(mx,dp[i][0] + dp[i][2]);
            mx = max(mx,dp[i][0] + dp[i][1]);
        }
        for(int i = 1;i<=n;i++) {
            if(dp[i][0] + dp[i][2] == mx || dp[i][0] + dp[i][1] == mx) {
                ans++;
            }
        }
        return ans;
    }
};