class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m long长整型 
     * @return long长整型vector
     */
    long sum[1005];
    vector<long> FarmerNN(int n, long long m) {
        // write code here
        long every = 2*n-2;
        long t = m/every;
        int re = m%every;
        for(int i=2;i<n;i++)
            sum[i] = 2*t;
        sum[1] = t;
        sum[n] = t;
        int flag = 0;
        int now = 1;
        while(re>0){
            sum[now]++;
            re--;
            if(flag == 0)
            {
                now++;
                if(now == n)
                    flag = 1;
            }
            else
                now--;
        }
        vector<long>ans;
        for(int i=1;i<=n;i++)
            ans.push_back(sum[i]);
        return ans;
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param k int整型 
     * @return string字符串
     */
    int alive[26];
    string NS_String(string s, int k) {
        // write code here
        int len = s.length();
        for(int i=0;i<len;i++)
            alive[s[i]-'a'] = 1;
        for(int i=1;i<=k;i++){
            for(int j=0;j<26;j++)
            {
                if(alive[j] == 1){
                    alive[j] = 0;
                    break;
                }
            }
        }
        string ans = "";
        for(int i=0;i<len;i++){
            if(alive[s[i]-'a'] == 1)
                ans.push_back(s[i]);
        }
        return ans;
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @param t int整型 
     * @return long长整型
     */
    long long dp[100005];
    int dir[1000005];
    long long section(vector<int>& a, int t) {
        // write code here
        memset(dir,-1,sizeof(dir));
        long long big = -1;
        int size = a.size();
        for(int i=0;i<size;i++){
            int another = t^a[i];
            dp[i] = max(big,(long long)dir[another]);
            dir[a[i]] = i;
            big = max(big,dp[i]); 
        }
        long long cnt = 0;
        for(int i=0;i<size;i++)
            cnt = cnt + (dp[i] + 1);
        long s = size;
        s = s*(s-1)/2;
        return s - cnt;
    }
};

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    vector<TreeNode*>vec;
    unordered_map<TreeNode*,int>sum;
    int c[100005];
    bool seven;
    void add(TreeNode* root){
        if(root == nullptr)
            return;
        vec.push_back(root);
        add(root->left);
        add(root->right);
        int cnt = 1;
        if(root->left != nullptr)
            cnt += sum[root->left];
        if(root->right != nullptr)
            cnt += sum[root->right];
        sum[root] = cnt;
    }
    void dfs(TreeNode* x,TreeNode* y){
        if(seven == false)
            return;
        if(x == nullptr && y == nullptr)
            return;
        if(x == nullptr || y == nullptr){
            seven = false;
            return;
        }
        dfs(x->left,y->left);
        dfs(x->right,y->right);
    }
    int maxSubTree(TreeNode* root) {
        // write code here
        add(root);
        int size = vec.size();
        for(int i=0;i<size;i++){
            c[i] = sum[vec[i]];
        }
        int ans = 0;
        for(int i=0;i<size;i++){
            int p = c[i];
            if(p < ans)
                continue;
            for(int j=i+1;j<size;j++){
                int q = c[j];
                if(p != q)
                    continue;
                seven = true;
                dfs(vec[i],vec[j]);
                if(seven)
                    ans = max(ans,p);
            }
        }
        
        return ans;
    }
};