class Transform{
public:
	string trans(string s,int n){
		auto left = s.begin();
		auto right = s.begin();
		while (right != s.end())
		{
			if(*right == ' '){
				reverse(left,right);
				left = next(right);
			}
			right++;
		}
		reverse(left,right);
		reverse(s.begin(),s.end());
		for (int i=0;i<s.length();++i)
		{
			if(isupper(s[i])){s[i] -= 'A'-'a';}
			else if(islower(s[i])){s[i] += 'A'-'a';}
		}
		return s;
	}
};

class Patrition{
public:
	vector<int> getpartition(vector<vector<int>> & land,int n,int m){
		vector<int> left(n+1,0);
		vector<int> right(n+1,0);
		vector<int> res;
		for (int j=0;j<n;++j)
		{ 
			for (int i=0;i<m;++i)
			{
				if(land[i][j] == 0){
					left[j+1]++;
				}
			}
			left[j+1] += left[j];
		}

		for (int j=n-1;j>=0;--j)
		{
			for (int i=m-1;i>=0;--i)
			{
				if (land[i][j] == 1)
				{
					right[j]++;
				}
			}
			right[j] += right[j+1];
		}

		int resmax = -1;
		int pos = -1;
		for (int i=0;i<left.size();++i)
		{
			if (resmax < left[i] + right[i])
			{
				resmax = left[i] + right[i];
				pos = i;
			}
		}
		res.push_back(pos);
		res.push_back(pos+1);
		return res;
	}
};



struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};

class LongestPath {
public:
	void longestpath(TreeNode* root,int &count,int &countincluderoot){
		if(root == NULL) {count = 0;return ;}
		int countleft = 0,countright = 0;
		int countincluderootLeft = 0,countincluderootRight = 0;
		longestpath(root->left,countleft,countincluderootLeft);
		longestpath(root->right,countright,countincluderootRight);

		countincluderoot = 1;
		count = 1;
		if (root->left && root->right && root->left->val == root->val && root->right->val == root->val)
		{
			count += countincluderootLeft+countincluderootRight;
			countincluderoot = 1+ max(countincluderootLeft,countincluderootRight);
		}
		else if (root->left && root->left->val == root->val)
		{
			count += countincluderootLeft;
			countincluderoot = max(1,countincluderootLeft)+1;
		}
		else if (root->right && root->right->val == root->val)
		{
			count += countincluderootRight;
			countincluderoot = max(1,countincluderootRight)+1;
		}
		
		count = max(count,max(countleft,countright));
	}
    int findPath(TreeNode* root) {
        // write code here
		int cnt = 0;
		int cc;
		longestpath(root,cnt,cc);
		return cnt;
    }
};