akhauriyash/Code-Regression huggingface dataset:
/*
　　　　　／＞　 フ
　　　　　| 　_　 _|
　 　　　／`ミ _x 彡
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ
 */

#include <queue>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MP make_pair
#define ll long long
#define fi first
#define se second
using namespace std;

template <typename T>
void read(T &x) {
    x = 0; bool f = 0;
    char c = getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=1;
    for (;isdigit(c);c=getchar()) x=x*10+(c^48);
    if (f) x=-x;
}

template<typename F>
inline void write(F x, char ed = '\n') {
	static short st[30];short tp=0;
	if(x<0) putchar('-'),x=-x;
	do st[++tp]=x%10,x/=10; while(x);
	while(tp) putchar('0'|st[tp--]);
	putchar(ed);
}

template <typename T>
inline void Mx(T &x, T y) { x < y && (x = y); }

template <typename T>
inline void Mn(T &x, T y) { x > y && (x = y); }

void exgcd(ll a, ll b, ll &x, ll &y) {
	if (!b) return x = 1, y = 0, void();
	exgcd(b, a % b, x, y); 
	ll t = x; x = y, y = t - y * (a / b);
}

const int N = 2256;
ll st[N], X, x, y, tp, n;
int main() {
	read(n), X = n * 2;
	if (X % 2 == 0) {
		st[++tp] = 1;
		while (X % 2 == 0) X /= 2, st[tp] *= 2;
	}
	for (ll i = 3;i * i <= X; i += 2) {
		if (X % i == 0) {
			st[++tp] = 1;
			while (X % i == 0) X /= i, st[tp] *= i;
		}
	}
	if (X != 1) st[++tp] = X;
	int lim = (1 << tp) - 1;
	ll ans = 1e15;
	for (int i = 0;i <= lim; i++) {
		ll A = 1, B = 1;
		for (int j = 1;j <= tp; j++)
			if (i >> (j - 1) & 1) A = A * st[j];
			else B = B * st[j];
		exgcd(A, B, x, y);
		if (A > B) {
			x = (x % B + B) % B;
			if (!x) x += B;
			Mn(ans, x * A - 1);
		}
		else {
			y = (y % A + A) % A - A; 
			Mn(ans, - y * B);
		}
	}
	write(ans);
	return 0;
}

/*



*/

Measured memory_bytes: 3092
#include<stdio.h>
main()
{
    long long a,b,c,i,x,y;
    while(scanf("%lld %lld %lld",&a,&b,&c)==3){
        x=0;
        while(x!=c){
            if(x%2==0){
                if(a%2!=0){
                    a--;
                    a=a/2;
                    b=b+a;
                    x++;
                }
                else{
                    a=a/2;
                    b=b+a;
                    x++;
                }
            }
            else{
                if(b%2!=0){
                    b--;
                    b=b/2;
                    a=a+b;
                    x++;
                }
                else{
                    b=b/2;
                    a=a+b;
                    x++;
                }
            }
        }
        printf("%lld %lld\n",a,b);
    }
}


Measured memory_bytes: 128
#include <cstdio>
int n, a[100005];
char s[100005];
int main() {
	int i, j;
	scanf("%d%s", &n, s);
	s[n]=s[0];
	for(i=0; i<4; i++) {
		a[0] = i%2, a[1] = i/2%2;
		for(j=2; j<n+2; j++) a[j] = a[j-1] ^ a[j-2] ^ s[j-1]=='x';
		if(a[0]==a[n] && a[1]==a[n+1]) {
			for(j=0; j<n; j++) putchar(a[j] ? 'W':'S');
			return 0;
		}
	}
	puts("-1");
	return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ll long long
#define lld long double
#define ALL(x) x.begin(), x.end()
using namespace std;

int main(int argc, char const *argv[])
{
    int n, m;
    cin >> n >> m;
    map<int, vector<int>> g;
    rep(i, n)
    {
        int k;
        cin >> k;
        rep(j, k)
        {
            int l;
            cin >> l;
            l--;
            g[l].push_back(m + i);
            g[m + i].push_back(l);
        }
    }
    vector<bool> visited(n + m, false);
    deque<int> que;
    que.push_back(m);
    while (!que.empty())
    {
        int cur = que.front();
        que.pop_front();
        if (visited[cur])
            continue;
        visited[cur] = true;
        for (auto x : g[cur])
        {
            if (visited[x] == false)
            {
                que.push_front(x);
            }
        }
    }
    bool ok = true;
    rep(i, m, n + m)
    {
        ok &= visited[i];
    }
    if (ok)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
    return 0;
}


Measured memory_bytes: 12024
s = gets.chomp
arr = [
  ["eraser", 6],
  ["erase", 5],
  ["dreamer", 7],
  ["dream", 5],
]

ind = 0
flag = true
max_len = s.length
while ind < max_len
  f = false
  arr.each do |word, len|
    if word == s[(-ind-len)..(-ind-1)]
      f = true
      ind += len
      break
    end
  end

  unless f
    flag = false
    break
  end
end

puts flag ? "YES" : "NO"

Measured memory_bytes: 14476
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric> // accumulate(v.begin(), v.end(), 0)

using namespace std;
#define ll long long

ll gcd(ll x, ll y) {
  if(x > y)
    return gcd(y, x);
  else if(x == 0)
    return y;
  else
    return gcd(y % x, x);
}

int main(){
  int N;
  cin >> N;
  vector<ll> A(N);
  for(int i=0; i<N; i++)
    cin >> A[i];
  vector<ll> gcdLeft(N), gcdRight(N);
  gcdLeft[0] = A[0];
  for(int i=1; i<N; i++)
    gcdLeft[i] = gcd(gcdLeft[i-1], A[i]);
  gcdRight[N-1] = A[N-1];
  for(int i=N-2; i>=0; i--)
    gcdRight[i] = gcd(gcdRight[i+1], A[i]);
  ll ans = 1;
  ans = max(gcdRight[1], max(gcdLeft[N-2], ans));
  for(int i=1; i<N-1; i++) {
    ans = max(gcd(gcdLeft[i-1], gcdRight[i+1]), ans);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
#include<cmath>
#include<algorithm>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int s[n][2];
    int temp=0;
    
    for(int i=0;i<n;i++){
    	cin>>s[i][0]>>s[i][1];
    	
	}
	
	for(int i=0;i<n;i++){
		if(s[i][0]==s[i][1]){
    		temp++;
		}else{
			temp=0;
		}
		if(temp==3){
			break;
		}
	}
    if(temp==3){
    	cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
    
    return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits.h>
#include <climits>
#include <map>
#include <unordered_map>
#include <cmath>
#include <set>
#include <iterator>
#include <deque>
#include <assert.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
ull min(ull x, ull y){ if (x<y) return x; return y;}
ull max(ull x, ull y){ if (x<y) return y; return x;}
ll min(ll x, ll y){ if (x<y) return x; return y;}
ll max(ll x, ll y){ if (x<y) return y; return x;}
double min(double x, double y){ if (x<y) return x; return y;}
double max(double x, double y){ if (x<y) return y; return x;}
ull gcd(ull x, ull y){
    if (!x) return y;
    if (!y) return x;
    if (x>y) swap(x,y);
    return gcd(x, y%x);
}
ull inv(ull a, ull c){ // a,c are coprime and a<c
    if (a==1){
        return 1;
    }
    return ((c-(c/a))*inv(c%a,c))%c;
}


int main(){
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    
    double l, three = 3.0;
    cin>>l;
    
    double ans = (l/three)*(l/three)*(l/three);

    printf("%.7f\n", ans);
    return 0;
    
}



Measured memory_bytes: 256
#include <bits/stdc++.h>

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define rep(i, n) repd(i, 0, n)

using namespace std;

using ll = long long;
using ul = unsigned long long;
using ld = long double;
ll mod = 1000000007;

int main() {
    ll k;
    cin >> k;
    bool exist[k] = {};
    ll ans = 0;
    ll num = 7 % k;
    while (num != 0) {
        num = (num * 10 + 7) % k;
        ans++;
        if (exist[num]) {
            cout << "-1" << endl;
            return 0;
        } else {
            exist[num] = true;
        }
    }
    cout << ans + 1 << endl;
    return 0;
}



Measured memory_bytes: 4604
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int main(void)
{
	int n,w,v[100],ww[100],i,j,dp[10001],mx;
	scanf("%d %d",&n,&w);
	for(i=0;i<n;i++)	scanf("%d %d",&v[i],&ww[i]);
	for(i=0;i<=w;i++)	dp[i]=-1;
	dp[0]=0;
	for(i=0;i<n;i++)	{
		for(j=0;j<w;j++)	{
			if(j+ww[i]<=w && dp[j]!=-1)	{
				dp[j+ww[i]]=max(dp[j+ww[i]],dp[j]+v[i]);
			}
		}
//		for(j=0;j<=w;j++)	printf("%d ",dp[j]);	printf("\n");
	}
	mx=-1;
	for(i=0;i<=w;i++)	{
		mx=max(mx,dp[i]);
	}
	printf("%d\n",mx);
	return 0;
}


Measured memory_bytes: 1064
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define MAX 1000

int top,S[MAX];

int pop(void);
void push(int);

int main(){
  int a,b;
  char s[MAX];

  top = 0;

  while(scanf("%s",s) != EOF){
    if(s[0] == '+'){
      a = pop();
      b = pop();
      push(a + b);
    }
    else if(s[0] == '-'){
      a = pop();
      b = pop();
      push(b - a);
    }
    else if(s[0] == '*'){
      a = pop();
      b = pop();
      push(a * b);
    }
    else push(atoi(s));
  }

  printf("%d\n",pop());
  return 0;
}

int pop(){

  top--;
  return S[top+1];
}

void push(int c){

  S[++top] = c;
}

Measured memory_bytes: 548
N, M = map(int, input().split())
a_list = tuple(map(int, input().split()))
b_list = tuple(map(int, input().split()))
mod = 10 ** 9 + 7

# 同じもの含んでいたらアウト
a_set = set(a_list)
b_set = set(b_list)
if len(a_set) < N or len(b_set) < M:
    print(0)
    exit()

# 大きいものから順にみていく
a_list = sorted(a_list, reverse=True)
b_list = sorted(b_list, reverse=True)

# １つ余分につけておく
a_list.append(-1)
b_list.append(-1)
ans = 1
a_i = 0
b_i = 0
for i in range(N*M, 0, -1):
    if i == a_list[a_i] and i == b_list[b_i]:
        # iが両方に出現
        a_i += 1
        b_i += 1
    elif i == a_list[a_i]:
        # iがAのみに出現
        a_i += 1
        ans *= b_i
        ans %= mod
    elif i == b_list[b_i]:
        # iがBのみに出現
        b_i += 1
        ans *= a_i
        ans %= mod
    else:
        # iがA, Bどちらにも出現しない、置き場がないときans = 0になる
        ans *= (a_i*b_i - (N * M - i))
        ans %= mod
print(ans % mod)



Measured memory_bytes: 3316
import java.util.Scanner;

class Main {
	public static void main(String args[]) {
		Scanner scanner = new Scanner(System.in);
		int  num = scanner.nextInt();//要素数
		int  time = scanner.nextInt();//要素数
		int[] array = new int[num];
		String[] pro = new String[num];
		
		for(int i = 0; i < num; i ++ ){
			pro[i] = scanner.next();
			array[i] = scanner.nextInt();
		}
		
		Queue(pro, array,num,time);
		
		scanner.close();
	}

	public static void Queue( String[] pro, int[] array,int num,int time){
		int sub;
		int i;
		int end_count = 0;
		int end_count_now;
		int time_count = 0;
		int judge[] = new int[num];
		boolean judge_end = false;
		int count = 0;
		
		while( end_count < num  ){
			end_count_now = 0;
			judge_end = false;

			//System.out.println(count +  "週目");		//出力
			
			for( i = 0; i < num - end_count; i ++ ){
				sub = array[i] - time;
				if(sub <= 0){
					time_count += array[i];
					System.out.println(pro[i] +  " " + time_count);		//出力
					end_count_now ++;
					judge_end = true;
				}else{
					array[i] -= time;
					time_count += time;
					if(judge_end) {
						array[i - end_count_now] = array[i];
						pro[i - end_count_now] = pro[i];
					}
				}
				continue;
			}
			end_count += end_count_now;
			count ++;
		}
	}
}


Measured memory_bytes: 74596
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int n = Integer.parseInt(sa[0]);
		long m = Long.parseLong(sa[1]);
		sa = br.readLine().split(" ");
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(sa[i]);
		}
		br.close();

		Arrays.parallelSort(a);
		int ng = 1;
		int ok = a[n - 1] * 2 + 1;
		while (ok - ng > 1) {
			int mid = (ok + ng) / 2;
			long cnt = 0;
			for (int i = 0; i < n; i++) {
				int idx = binarySearch(a, mid - a[i] - 0.5);
				cnt += n - idx;
			}
			if (cnt < m) {
				ok = mid;
			} else {
				ng = mid;
			}
		}

		long[] b = new long[n + 1];
		for (int i = 0; i < n; i++) {
			b[i + 1] = b[i] + a[i];
		}

		long ans = 0;
		long cnt = 0;
		for (int i = 0; i < n; i++) {
			int idx = binarySearch(a, ng - a[i] - 0.5);
			long c = n - idx;
			cnt += c;
			long val = a[i] * c + (b[n] - b[idx]);
			ans += val;
		}
		ans -= (cnt - m) * ng;
		System.out.println(ans);
	}

	static int binarySearch(int[] array, double val) {
		int start = -1;
		int end = array.length;

		while (Math.abs(end - start) > 1) {
			int mid = (end + start) / 2;
			if (mid == array.length) {
				return mid;
			}
			if (array[mid] >= val) {
				end = mid;
			} else {
				start = mid;
			}
		}
		return end;
	}
}


Measured memory_bytes: 37900
#include<iostream>
using namespace std;

int main(){
  int a,b;
  
  cin >> a >> b ;
  
  if (a < b) {
    cout << "a < b" << endl;
  }
  else if (a > b) {
    cout << "a > b" << endl;
  }
  else {
    cout << "a == b" << endl;
  }
  
  return 0;
}


Measured memory_bytes: 3080
# C - Splitting Pile
N = int(input())
A = list(map(int,input().split()))

s = [0]*(N+1)
for i in range(N-1):
    s[i+1] = s[i] + A[i]

ans = 10**10
for i in range(1,N):
    diff = abs((s[N-1] + A[-1] - s[i]) - s[i])
    ans = min(ans,diff)
print(ans)

Measured memory_bytes: 30536
require 'set'
n, k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
a = a.map{|e| e -= 1}
c = 0
s = Set.new
list = Array.new
s.add(c)
list.push(c)
l = 1
([n, k]).min.times do
    c = a[c]
    if s.include?(c)
        break
    else
        l += 1
        s.add(c)
        list.push(c)
    end
end
if k <= n
    puts c + 1
else
    l -= list.index(c)
    k -= list.index(c)
    k %= l
    k.times do
        c = a[c]
    end
    puts c + 1
end

Measured memory_bytes: 39468
#include <bits/stdc++.h>
using namespace std;
using ll = unsigned long long;


int main() {
  int A, B;
  cin >> A >> B;
  int add = A + B;
  int dif = A - B;
  int daa = A * B;
  int result = max(add, max(dif, daa));
  cout << result << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define MAX 3

int pane[MAX][MAX];
int temp[MAX][MAX];
int d_x[4]={0,1,0,-1};
int d_y[4]={1,0,-1,0};

void empty(int *row,int *col){
  int i,j;
  for(i=0;i<MAX;i++)
    for(j=0;j<MAX;j++)
      if(!pane[i][j]){
	*row=j;
	*col=i;
	return;
      }  
}
   
void swap(int *a,int *b){
  int temp;
  temp = *a;*a = *b;*b = temp;
}
  
int cal(){
  int i,e;
  int count=0; 
  for(i=0;i<9;i++){
    e=pane[i/3][i%3];
    if(e){
      e--;
      count+=abs(i/3-e/3)+abs(i%3-e%3);
    }
  }   
  return count;
}
  
int dfs(int x,int y,int p,int deep,const int limt){
  int i;
  int len;
  int x_2,y_2;
  int emc;   
  len=cal();
  if(len==0) return deep;
  if(deep+len>limt) return -1; 
  for(i=0;i<4;i++){
    x_2=x+d_x[i];
    y_2=y+d_y[i];      
    if(~p&&i==(p+2)%4) continue;
    if(!(0<=x_2 && x_2<3 && 0<=y_2 && y_2<3)) continue;    
    swap(&pane[y][x],&pane[y_2][x_2]);
    emc=dfs(x_2,y_2,i,deep+1,limt);
    if(~emc) return emc;       
    swap(&pane[y][x],&pane[y_2][x_2]);
  }   
  return -1;
} 

int main() {
  int i,j;
  int h,a,row,col;
      
  for(i=0;i<MAX;i++){
    for(j=0;j<MAX;j++)
      scanf("%d",&pane[i][j]);
  }  
  empty(&row,&col);  
  for(h=0;h<100;h++){
    for(i=0;i<MAX;i++){
      for(j=0;j<MAX;j++)
	temp[i][j]=pane[i][j];
    }    
    a=dfs(row,col,-1,0,h);    
    if(a!=-1){
      printf("%d\n",a);
      break;
    }    
    for(i=0;i<MAX;i++){
      for(j=0;j<MAX;j++)
	pane[i][j]=temp[i][j];
    }    
    a=-1;
    if(h==99) printf("%d\n\n",a);
  }      
  return 0;
}



Measured memory_bytes: 2108
#include <bits/stdc++.h>
using namespace std;

const int Maxn = 100005;

int n, m;
int par[Maxn], siz[Maxn];
int comp;

int getPar(int x) { return par[x] == x? x: par[x] = getPar(par[x]); }

void unionSet(int a, int b)
{
    a = getPar(a), b = getPar(b);
    if (a == b) return;
    if (siz[a] < siz[b]) swap(a, b);
    siz[a] += siz[b]; par[b] = a;
    comp--;
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        par[i] = i, siz[i] = 1;
    comp = n;
    while (m--) {
        int a, b, c; scanf("%d %d %d", &a, &b, &c);
        unionSet(a, b);
    }
    printf("%d\n", comp);
    return 0;
}


Measured memory_bytes: 1024
// #include <bits/stdc++.h>
// #define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
// #define int long long
// #define pb push_back
// #define sz(i) (int)(i.size())
// #define F first
// #define S second
// #define L long double
// #define P pair<int, int>
// const int inf = 0x3f3f3f3f3f3f3f3LL;
// const int mod = (int)1e9 + 7;
// using namespace std;
// #if LOCAL
// #include "../../tr.h"
// #else
// #define tr(...)
// #define endl '\n'
// #endif
// template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
// const int N = 5*(int)1e5 + 10;

// int n;
// vector<int> v;
// set<vector<int> > s;
// map<vector<int>, bool> dp[N];

// void solve(int idx, vector<int> a){
//    if(idx >= n){
//       s.insert(a);
//       return ;
//    }

//    if(dp[idx].count(a))
//       return ;

//    dp[idx][a] = 1;
//    solve(idx+1, a);

//    for (int i = idx+1; i < n; ++i)
//    {
//       if(a[i] == a[idx]){
//          vector<int> tmp = a;

//          for (int j = idx; j <= i; ++j)
//             tmp[j] = a[idx];

//          solve(i+1, tmp);
//       }
//    }
// }

// int32_t main(){_

//    cin>>n;
//    v.resize(n);

//    for (int i = 0; i < n; ++i)
//    {
//       cin>>v[i];
//    }

//    vector<int> tmp;
//    for (int i = 0, j = 0; i < n; i=j)
//    {
//       j = i;
//       tmp.pb(v[j]);
//       while(j < n and v[i] == v[j])++j;
//    }

//    v = tmp;
//    n = sz(v);
//    solve(0, v);
//    tr(s);
//    cout<<sz(s);

//    #warning make sure N size is correct!
//    return 0;
// }
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define pb push_back
#define sz(i) (int)(i.size())
#define F first
#define S second
#define L long double
#define P pair<int, int>
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
const int N = 2*(int)1e5 + 10;

int n, a[N];
int dp[N], dp_on_num[N];

int32_t main(){_

   cin>>n;

   vector<int> v;
   v.pb(0);
   for (int i = 1; i <= n; ++i)
   {
      int x;
      cin>>x;
      if(v.back() == x)continue;
      v.pb(x);
   }

   tr(v);

   n = sz(v);
   dp[0] = 1;

   for (int i = 1; i < n; ++i)
   {
      dp[i] = dp[i-1];
      dp[i] += dp_on_num[v[i]];
      dp[i] %= mod;
      dp_on_num[v[i]] = dp[i];
   }
   
   cout<<dp[n-1];
   #warning make sure N size is correct!
   return 0;
}

Measured memory_bytes: 6000
class UnionFind():
    def __init__(self, n):
        # 正==子: 根の頂点番号 / 負==根: 連結頂点数
        self.n = n
        self.parents = [-1] * n
 
    def find(self, x):
        #要素xが属するグループの根を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def union(self, x, y):
        #要素xが属するグループと要素yが属するグループとを併合する
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def size(self, x):
        # 要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]
 
    def same(self, x, y):
        # 要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)
 
    def members(self, x):
        # 要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
 
    def roots(self):
        # すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]
 
    def group_count(self):
        # グループの数を返す
        return len(self.roots())
 
    def all_group_members(self):
        # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
        return {r: self.members(r) for r in self.roots()}
 
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
        
########################################
n,m = map(int, input().split())
u = UnionFind(n)

for i in range(m):
    a,b = map(int,input().split())
    u.union(a-1,b-1)

ans = 0
for i in range(n):
    ans = max(ans,u.size(i))

print(ans)

Measured memory_bytes: 76204
#include <bits/stdc++.h>

#define get_variable_name(x) #x
#define debug(x) cout << #x << " = " << x << endl
#define rep(i,n) for(int (i) = 0; (i) < (n); (i)++)

#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort((x).begin(), (x).end())
#define REVERSE(x) reverse( (x).begin(),(x).end())
#define UNIQUE(x) (x).erase(unique(ALL((x))), (x).end())
#define PW(x) (1LL<<(x))

using namespace std;
using ll = int64_t;
using P = pair<int, int>;

template<class T,class U>
ostream& operator<<(ostream &os, const pair<T, U> &p) {
    os << get_variable_name(p) << " = (" << p.first <<", " << p.second << ")";
    return os;
}

template<class T>
ostream& operator <<(ostream& os, const vector<T> &v){
    cout << get_variable_name(v) << " = [";
    for(auto i : v) 
        os << " " << i;
    os << " ]";
    return os;
}


const int INF = 1e8;

int main() {
    ios::sync_with_stdio(false);
    int W, H, N;
    cin >> W >> H >> N;
    int min_x = 0, min_y = 0, max_x = W, max_y = H;
    int x, y, a;
    rep(i, N) {
        cin >> x >> y >> a;
        switch(a) {
            case 1:
                min_x = max(min_x, x);
                break;
            case 2:
                max_x = min(max_x, x);
                break;
            case 3:
                min_y = max(min_y, y);
                break;
            case 4:
                max_y = min(max_y, y);
                break;
        }
    }

    int h = max_y-min_y;
    int w = max_x-min_x;
    if(h < 0 or w < 0) {
        cout << 0 << endl;
    } else {
        cout << h*w << endl;
    }
}


Measured memory_bytes: 384
#include <bits/stdc++.h>

using namespace std;


int BubbleData[100];

void judge(const int n) {
	int cnt,tmp;

	cnt = 0;
	for (int i = n; i > 0; i--) {
		for (int j = 0; j < i; j++) {
			if (BubbleData[j] > BubbleData[j + 1]) {
				cnt++;
				tmp = BubbleData[j];
				BubbleData[j] = BubbleData[j + 1];
				BubbleData[j + 1] = tmp;
			}
		}
	}
	cout << cnt << endl;
}


int main(void) {
	int n;

	while (cin >> n, n) {
		for (int i = 0; i < n; i++) {
			cin >> BubbleData[i];
		}
		judge(n-1);
	}

	return 0;
}


Measured memory_bytes: 3104
#include <iostream>
#include <fstream>
#include <typeinfo>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<25;
const double pi=acos(-1);
const double eps=1e-10;
const vi emp;

struct point{
	int x,y;
	point operator+(point p){
		return point{x+p.x,y+p.y};
	}
	point operator-(point p){
		return point{x-p.x,y-p.y};
	}
	point operator*(int p){
		return point{x*p,y*p};
	}
	point operator/(int p){
		if(!p) return point{0,0}; 
		return point{x/p,y/p};
	}
	bool operator==(point p)const{
		return x==p.x&&y==p.y;
	}
	bool operator!=(point p)const{
		return !(*this==p);
	}
	bool operator<(point p)const{
		if(x!=p.x) return x<p.x;
		return y<p.y;
	}
	bool operator>=(point p)const{
		return !(*this==p);
	}
};

typedef pair<point,point> pp;
typedef vector<point> VP;
const point O{0,0};

int Square_Area(point x,point y){
	point z=y-x;
	return z.x*z.x+z.y*z.y;
}

point Normal(point p){
	return point{p.y,-p.x};
}

void Point_in(point& p){
	cin>>p.x>>p.y;
}

int n;

int main(){
	while(1){
		cin>>n;
		if(!n) break;
		int ans=0;
		VP p(n);
		set<point> st;
		for(auto i=p.begin();i!=p.end();i++){
			Point_in(*i);
			st.insert(*i);
		}
		for(auto i=p.begin();i!=p.end()-1;i++) for(auto j=i+1;j!=p.end();j++){
			point q=Normal(*j-*i);
			if(st.find(*i+q)!=st.end()&&st.find(*j+q)!=st.end()) ans=max(ans,Square_Area(*i,*j));
		}
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 3228
#include<iostream>
using namespace std;
int main() {
	double a, b;
	int ans[111], an,aa,bb;
	an = 0;
	while (cin >> a >> b) {
		an = an + 1;
		if (a <35.5 ) {
			aa = 1;
			goto h;
		}
		if (a < 37.5) {
			aa = 2;
			goto h;
		}
		if (a < 40) {
			aa = 3;
			goto h;
		}
		if (a < 43) {
			aa = 4;
			goto h;
		}
		if (a < 50) {
			aa = 5;
			goto h;
		}
		if (a < 55) {
			aa =6 ;
			goto h;
		}
		if (a <70 ) {
			aa = 7;
			goto h;
		}
		aa = 8;
	h:;
		if (b < 71) {
			bb= 1;
			goto m;
		}
		if (b < 77) {
			bb = 2;
			goto m;
		}
		if (b < 83) {
			bb = 3;
			goto m;
		}
		if (b < 89) {
			bb =4 ;
			goto m;
		}
		if (b < 105) {
			bb = 5;
			goto m;
		}
		if (b < 116) {
			bb = 6;
			goto m;
		}
		if (b < 148) {
			bb = 7;
			goto m;
		}
		bb = 8;
	m:;
		if (aa < bb) {
			ans[an] = bb;
		}
		else {
			ans[an] = aa;
		}
	}
	for (int i = 1; i <= an; i++) {
		if (ans[i] == 1) {
			cout << "AAA"<< endl;
		}
		if (ans[i] == 2) {
			cout<<"AA" <<endl;
		}
		if (ans[i] == 3) {
			cout<<"A" <<endl;
		}
		if (ans[i] == 4) {
			cout<< "B"<<endl;
		}
		if (ans[i] == 5) {
			cout<< "C"<<endl;
		}
		if (ans[i] == 6) {
			cout<<"D"<<endl;
		}
		if (ans[i] == 7) {
			cout << "E" << endl;
		}
		if (ans[i] == 8) {
			cout << "NA" << endl;
		}




	}

}


Measured memory_bytes: 3196
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            long[] inputLongArray = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();
            long N = inputLongArray[0];
            long D = inputLongArray[1];
            int cnt = 0;
            while(D * 2 + 1 < N)
            {
                    N -= (D * 2 + 1);
                    cnt++;
            }
            if (N != 0)
            {
                cnt += 1;
            }
            Console.WriteLine(cnt);

        }
    }
}
// 文字列の入力
//string s = Console.ReadLine();

// 整数の入力
//long n = long.Parse(Console.ReadLine());

// 文字列配列の入力
//string[] inputStrArray = Console.ReadLine().Split(' ');

// 整数配列の入力
//long[] inputLongArray = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();


Measured memory_bytes: 11348
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mod = 1e9+7;
vector<ll> a(300000);
vector<bool> seen(300000,false);
vector<ll> cnt(300000);

int main(){
    ll n,k;
    cin >> n >> k;   
    for(ll i = 0; i < n; i++){
        ll b;
        cin >>b;
        b--;
        a[i] = b;
    } 
    ll tmp = 0;
    ll mae;
    ll roop;
    for(ll i = 0; i < n; i++){
        if(seen[tmp]){
            roop = cnt[mae]-cnt[tmp]+1;
            break;
        }
        seen[tmp] = true;
        cnt[tmp] = i;
        mae = tmp;
        tmp = a[tmp];
    }  

    if(k <= cnt[tmp]){
        ll ans = 0;
        for(ll i= 0; i < k; i++){
            ans = a[ans];
        }
        cout << ans+1 << endl;
    }
    else {
        k -= cnt[tmp];
        k %= roop;
        ll ans = tmp;
        for(ll i = 0; i < k; i++){
            ans = a[ans];
        }
        cout << ans+1 << endl;
    }
}

Measured memory_bytes: 7788
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long a,b,k;
cin>>a>>b>>k;
    long long  c=a;
    a-=k;
    if(a<0){a=0;k-=c;}
    else k=0;
    b-=k;
    if(b<0)b=0;
    cout<<a<<" "<<b<<endl;
    return 0;
}


Measured memory_bytes: 256
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define REPR(i,n) for(int i=n-1;i>=0;i--)
#define FORR(i,n,m) for(int i=n-1;i>=m;i--)
#define ARR(array) for(int i=0;i<array.size();i++)
#define all(in) in.begin(),in.end()
#define ALL(in,K) in,in+K
#define INF 1e18
#define MOD 100000007
#define SIZE 10005
#define PI 	3.14159265358979323846

unsigned euclidean_gcd(unsigned a, unsigned b) {
  if(a < b) euclidean_gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

char input(){
  char a;
  cin >> a;
  return a;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a,b;
    cin >> a >> b;
    cout << a-b+1 << endl;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	fmt.Printf("ABC%s\n", readLine())
}

/////////////////////////////////////////

//func readLineInt() []int {
//	result := make([]int, 0)
//	for _, v := range strings.Split(readLine(), " ") {
//		i, _ := strconv.Atoi(v)
//		result = append(result, i)
//	}
//	return result
//}

var reader = bufio.NewReaderSize(os.Stdin, 1e6)

func readLine() string {
	result := make([]byte, 0, 1e6)
	for {
		line, remains, e := reader.ReadLine()
		if e != nil {
			panic(e)
		}
		result = append(result, line...)
		if !remains {
			break
		}
	}
	return string(result)
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int main() 
{
	int K, S;
	cin >> K >> S;
	int ans = 0;
	for (int i = 0; i <= K; i++) {
		for (int j = 0; j <= K; j++) {
			if (S - i - j <= K && S - i - j >= 0) ans++;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;

#define ff first
#define ss second
#define pb push_back
#define int long long


signed main(){

int mod=1000000007;

#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#else
// online submission
#endif

int r,c;
cin >> r >> c;

char grid[r][c];

for(int i=0;i<r;i++){
	for(int j=0;j<c;j++){
		cin >> grid[i][j];
	}
}


int dp[r][c];

memset(dp, 0, sizeof(dp)); 





int i=0;

while(i<r && grid[i][0]!='#'){
	dp[i][0]=1;
	i++;
}


i=0;
while(i<c && grid[0][i]!='#'){
	dp[0][i]=1;
	i++;
}



for(int i=1;i<r;i++){
	for(int j=1;j<c;j++){
		if(grid[i][j]=='#')
		continue ;
		
		dp[i][j]=( dp[i-1][j]+dp[i][j-1] )%mod ;
	}
}

cout<<dp[r-1][c-1];	

	return 0;
    
}




Measured memory_bytes: 12344
#include<iostream>

int main(void){
	using namespace std;

	int tanp[1000], si[1000], tans[1000], kazu, rtanp, rsi, rtans, rcal, i, ban[1000], c;
	while(1){
		c = 0;
		cin >> kazu;
		if(kazu == 0){
			break;
		}
		for(i = 0;i < kazu;i++){
			cin >> ban[i] >> tanp[i] >> si[i] >> tans[i];
		}
		cin >> rtanp >> rsi >> rtans >> rcal;
		for(i = 0;i < kazu;i++){
			if(tanp[i] <= rtanp){
				if(si[i] <= rsi){
					if(tans[i] <= rtans){
						if(tanp[i] * 4 + si[i] * 9 + tans[i] * 4 <= rcal){
							cout << ban[i] <<endl;
							c = 1;
							
						}
					}
				}
			}
		}
		if(c == 0){
			cout << "NA" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1172
from collections import deque
n, m, k = map(int, input().split())
ans = []
for i in range(0, n + 1):
    for j in range(0, m + 1):
        cnt = (i * m) + (j * n) - 2 * (i * j)
        # print(i, j, cnt)
        ans.append(cnt)
if k in ans:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 143376
#include <bits/stdc++.h>

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (m); i < (int)(n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define INF 2000000000

#ifdef LOCAL
  #define eprintf(...) fprintf(stdout, __VA_ARGS__)
#else
  #define eprintf(...) 0
#endif

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int uint;

void printall(vector<vector<int>> &vvi) {
  REP(i, vvi.size()) {
    REP(j, vvi[i].size()) {
      cout << vvi[i][j];
    }
    cout << endl;
  }
}

int main() {
  int w, h, n;
  cin >> w >> h >> n;
  eprintf("hello\n");
  vector<vector<int>> vvi(h, vector<int>(w, 0));

  eprintf("hello\n");
  int x, y, a;
  REP(i, n) {
    cin >> x >> y >> a;
    eprintf("hello\n");
    switch(a) {
      case 1:
        REP(ty, h) {
          REP(tx, w) {
            eprintf("i,tx,ty:%d,%d,%d\n", i,tx,ty);
            if(tx < x) {
              vvi[ty][tx] = 1;
            }
          }
        }
        break;
      case 2:
        REP(ty, h) {
          REP(tx, w) {
            if(tx >= x) {
              vvi[ty][tx] = 1;
            }
          }
        }
        break;
      case 3:
        REP(ty, h) {
          REP(tx, w) {
            if(ty < y) {
              vvi[ty][tx] = 1;
            }
          }
        }
        break;
      case 4:
        REP(ty, h) {
          REP(tx, w) {
            if(ty >= y) {
              vvi[ty][tx] = 1;
            }
          }
        }
        break;
    }
  }
  //printall(vvi);
  int ans = 0;
  REP(i, vvi.size()) {
    ans += count(ALL(vvi[i]), 0);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
n = int(input())
dic = {}
for i in range(n):
  temp = 0
  s = input()
  for j in s:
    temp += (12 ** (ord(j) - ord('a') + 1))
  dic.setdefault(temp, 0)
  dic[temp] += 1
#print(dic)
res = 0
for i in dic:
  if dic[i] >= 2:
    res += ((dic[i] * (dic[i] - 1)) // 2)
print(res)

Measured memory_bytes: 20636
import           Control.Monad.State
import qualified Data.ByteString.Char8 as BS
import           Data.Char
import           Data.List

getAsInt :: IO [Int]
getAsInt =  unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

main :: IO ()
main = do
  _ <- getLine
  as <- getAsInt
  let solve = solve2
  print $ solve as

solve2 :: [Int] -> Int
solve2 (x:xs) = evalState go $ if x >= 0 then (-x,True,0,xs) else (x,False,0,xs)

go :: State (Int,Bool,Int,[Int]) Int
go = do
  (m,b,n,xs) <- get
  case xs of
    []     | b -> return $ n - m
           | otherwise -> return $ n + m
    (x:ys) | x >= 0 && - m >=   x -> put (-x,b    ,n-m,ys) >> go
           | x >= 0 && - m <    x -> put (m ,b    ,n+x,ys) >> go
           | x <  0 && - m >= - x -> put (x ,not b,n-m,ys) >> go
           | x <  0 && - m <  - x -> put (m ,not b,n-x,ys) >> go


Measured memory_bytes: 12028
n = int(input())
s = [sorted((input())) for _ in range(n)]
d = [{} for _ in range(n)]
for i in range(n):
  for j in range(len(s[i])):
    if s[i][j] in d[i]:
      d[i][s[i][j]] += 1
    else:
      d[i][s[i][j]] = 1
ans = ''
for i in d[0].keys():
  cnt = d[0][i]
  for j in range(1,n):
    if i in d[j]:
      cnt = min(cnt,d[j][i])
    else:
      break
    if j == n-1:
      ans += '{}'.format(i*cnt)
if n >= 2:
  print(''.join(sorted(ans)))
else:
  print(''.join(sorted(s[0])))

Measured memory_bytes: 3188
#include<iostream>
#include<string>
using namespace std;

int main(){
    int H,W;
    string str[300];
    cin >> H >> W;
    for(int i=0;i<H;i++){
        string input;
        cin >> input;
        for(int s=0;s<W;s++){
            str[s].push_back(input[s]);
        }
    }
    int ans=0;
    //一番右の列をプッシュするタイミングは、その一つ左の列をプッシュするタイミングに合わせて、最小となるようなタイミング。そういうイメージで。
    for(int i=1;i<W;i++){//str[i-1],str[i]で比較する。
        int dp[301][301]={};//dp[a][b]でstr[i-1]がa個、str[i]がb個残っている時、全部を無くすまでに必要な値。
        int plus[301][301]={};
        for(int sa=-300;sa<=300;sa++){//x , x+sa
            for(int x=max(-sa,0);x<=min(300-sa,300);x++){
                if(sa>0){
                    if(x==max(-sa,0)){
                        plus[0][sa]=0;
                    }else{
                        if(str[i-1][x-1] == str[i][x-1+sa]){
                            plus[x][x+sa]=plus[x-1][x-1+sa]+1;
                        }else{
                            plus[x][x+sa]=plus[x-1][x-1+sa];
                        }
                    }
                }else{
                    if(x==max(-sa,0)){
                        plus[x][0]=0;
                    }else{
                        if(str[i-1][x-1] == str[i][x-1+sa]){
                            plus[x][x+sa]=plus[x-1][x-1+sa]+1;
                        }else{
                            plus[x][x+sa]=plus[x-1][x-1+sa];
                        }
                    }
                }
            }
        }
        for(int a=1;a<=H;a++){
            for(int b=1;b<=H;b++){
                dp[a][b]=min(dp[a-1][b],dp[a][b-1]) + plus[a][b];
            }
        }
        ans += dp[H][H];
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1152
strings = ['dream', 'dreamer', 'erase', 'eraser']

reverse_candidates = [s[::-1] for s in strings]
# ['maerd', 'remaerd', 'esare', 'resare']
S = str(input())[::-1]

pointa = 0
while pointa != len(S):
    if S[pointa:pointa+5] in ('maerd', 'esare'):
        pointa += 5
    elif S[pointa:pointa+6] in ('resare'):
        pointa += 6
    elif S[pointa:pointa+7] in ('remaerd'):
        pointa += 7
    else:
        print('NO')
        exit()

print('YES')


Measured memory_bytes: 3188
#include<stdio.h>

int main(void)
{
	int r, c, i, j;
	int table[101][101];
	int temp, not_temp;

	scanf("%d %d", &r, &c);

	for( i = 0; i < r; i++)
	{
		for( j = 0; j < c; j++)
			scanf("%d", &table[i][j]);
	}

	/*for( i = 0; i < r; i++)
	{
		for( j = 0; j < c; j++)
			printf("%d ", table[i][j]);
		printf("\n");
	}*/

	for( i = 0; i < r; i++)
	{	
		temp = 0;
		for( j = 0; j < c; j++)
		{
			printf("%d ", table[i][j]);
			temp += table[i][j];
		}
		printf("%d\n", temp);
	}
	not_temp = 0;
	for (j = 0; j < c; j++)
	{
		temp = 0;
		for(i = 0; i < r; i++)
			temp += table[i][j];
		printf("%d " , temp);
		not_temp += temp;
	}

	printf("%d\n" ,not_temp);

	return 0;
}


Measured memory_bytes: 2036
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <map>
#include <string>
#include <vector>
#define rep(i, n) for (int i = 0; i < static_cast<int>(n); i++)

using namespace std;
using ll = int64_t;

const int N = 100001;
vector<int> graph[N];
int depth[N], longest[N], visit[N], parent[N];

int dfs(int now, int d) {
  if (visit[now])
    return 0;
  depth[now] = d;
  visit[now] = 1;
  int dd = 0;
  for (auto elem : graph[now]) {
    if (!visit[elem])
      parent[elem] = now;
    dd = max(dd, dfs(elem, d + 1) + 1);
  }
  longest[now] = dd;
  return dd;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int n, u, v;
  cin >> n >> u >> v;
  for (int i = 0; i < n - 1; i++) {
    int x, y;
    cin >> x >> y;
    graph[x].push_back(y);
    graph[y].push_back(x);
  }

  // root: v

  dfs(v, 0);

  int now = u, ans = 0;
  for (int i = 0; i < (depth[u] + 1) / 2; i++) {
    int tmp = depth[now] + longest[now] - 2;
    // cout << now << " " << depth[now] << " " << longest[now] << " " << tmp
    //      << endl;
    ans = max(ans, tmp);
    now = parent[now];
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 12416
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;


#define rep(i,n) for(ll (i)=0; (i)<(ll)(n); (i)++)
#define frep(i,m,n) for(ll (i)=(m); (i)<=(ll)(n); (i)++)
#define rrep(i,n) for(ll (i)=(n)-1; (i)>-1; (i)--)
#define frrep(i,m,n) for(ll (i)=(n); (i)>(ll)(m); (i)--)
#define ALL(x) (x).begin(), (x).end()

const ll INF = 100100100100100100;
const ll MOD = 1000000007;

// get abs
ll my_abs(ll a);
// a^n
ll a_n(ll a, ll n);
// get gcd
ll my_gcd(ll a, ll b);
// a^(-1) % MOD 
ll inv(ll a);
// (a+b+c)%MOD
ll madd(ll a, ll b, ll c);
// (a-b)%MOD
ll msub(ll a, ll b);
// (a*b*c)%MOD
ll mtime(ll a, ll b, ll c);


int main() {
    ll n;
    cin >> n;
    n %= 10;
    string ans;
    if(n == 3) ans = "bon";
    else if(n == 0 || n == 1 || n == 6 || n == 8) ans = "pon";
    else ans = "hon";
    cout << ans << endl;

    return 0;
}

ll my_abs(ll a) {
    if(a >= 0) return a;
    else return -1 *a;
}

ll a_n(ll a, ll n) { 
    if(n == 0) return 1;
    
    ll ret = a, count = 1;
    while(count * 2 < n) {
        ret *= ret;
        count *= 2;
    }
    if(count == n) return ret;
    else return (ret * a_n(a, n-count));
}

ll my_gcd(ll a, ll b) {
    if(b == 0) return a;
    return my_gcd(b, a%b);
}

ll inv(ll a) {
    return a_n(a, MOD-2);
}

ll madd(ll a, ll b, ll c) {
    ll ret = (a+b) % MOD;
    return (ret+c) % MOD;
}

ll msub(ll a, ll b) {
    if(a < b) return (a-b+MOD) % MOD;
    else return (a-b) % MOD;
}

ll mtime(ll a, ll b, ll c) {
    ll ret = (a*b) % MOD;
    return (ret*c) % MOD;
}


Measured memory_bytes: 3632
n = int(input())
w = [input() for i in range(n)]
d = []
for i in range(n):
    if w[i] in d:
        print("No")
        exit()
    if i > 0:
        if w[i][0] != w[i - 1][-1]:
            print("No")
            exit()
    d.append(w[i])
print("Yes")

Measured memory_bytes: 3064
ABC = input().split()
A, B, C = int(ABC[0]), int(ABC[1]), int(ABC[2])
memo = set()
i = 1
ans = 'NO'

while True:
  cur = (A * i) % B
  if cur == C:
    ans = 'YES'
    break
  if cur not in memo:
    memo.add(cur)
  else:
    break
  i += 1
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 1000000000;

int main()
{
  int N; scanf("%d", &N);
  string s; cin >> s;
  int cnt = 0;
  string ans;
  for (int i = 0; i < N; ++i) {
    if (s[i] == '(') {
      ans.push_back('(');
      ++cnt;
    }
    else {
      ans.push_back(')');
      if (cnt == 0) { ans = '(' + ans; }
      else { --cnt; }
    }
  }
  ans += string(cnt, ')');
  printf("%s\n", ans.c_str());
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
// statics
using namespace std;
using int64 = long long;
using PAIR = pair<int, int>;
constexpr int INF = 1 << 30;
constexpr int64 LINF = 1LL << 60;
constexpr int MOD = 1e9 + 7;
constexpr int MAX_N = 1e5 + 1;

// init/input
#define int int64
#define INIT ios::sync_with_stdio(false);cin.tie(0);
#define VAR(type, ...) type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T &t) {cin>>t;}
template<typename First, typename...Rest> void MACRO_VAR_Scan(First &first, Rest&...rest) {cin>>first;MACRO_VAR_Scan(rest...);}
#define VEC(type, c, n) vector<type> c(n);for(auto &&i:c)cin>>i;

// out
#define OUT(dist) cout<<(dist);
#define FOUT(n, dist) cout <<fixed<<setprecision(n)<<(dist);
#define SP cout<<" ";
#define BR cout<<"\n";
#define debug(x) cerr << #x << ":" << (x);BR;

// utility
#define ALL(a) (a).begin(), (a).end()
#define EACH(i, a) for(auto &&i:(a))
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RFOR(i, a, b) for(int i=(b)-1;i>=0;--i)
#define REP(i, n) for(int i=0;i<(n);++i)
#define RREP(i, n) for(int i=(n)-1;i>=0;--i)

signed main() {
  INIT;
	VAR(int, x, y);
	int d = abs(x - y);
	
	if (d <= 1) {
		OUT("Brown")BR;
	} else {
		OUT("Alice")BR;
	}
  
  return 0;
}


Measured memory_bytes: 256
#include "stdio.h"
#include "stdlib.h"
#include "math.h"

int compare_int(const void *a, const void *b){
    return *(long long int*)a - *(long long int*)b;
}

int sitigosann(int n){
  if(n==0){return 3;}
  if(n==1){return 5;}
  if(n==2){return 7;}
  return 0;
}

int main(int argc, char const *argv[]) {
  long long int i,j,l,temp;
  long long int M=3*(pow(3,9)-1)/2;
  int S[9][M];
  long long int s[M];
  for ( i = 0; i < M; i++) {
    for (j = 0; j < 9; j++) {
      S[j][i]=0;
    }
  }
  int k=0;
  for (i = 1; i <=9 ; i++) {
    for (j = 0; j <pow(3,i) ; j++) {
      temp=j;
      for (l = 0; l <i ; l++) {
        S[l][k]=sitigosann(temp%3);
        temp=(long long int)temp/3;
      }
      k++;
    }
  }
  int f[8];
  for (i = 0; i < M; i++) {
    s[i]=0;
    for (j = 0; j < 8; j++) {f[j]=0;}
    for ( j = 0; j < 9; j++) {
      s[i]=s[i]+S[j][i]*pow(10,j);
      f[S[j][i]]=1;
    }
    if (f[3]*f[5]*f[7]==0) {s[i]=pow(10,10);}
  }

  qsort(s, M, sizeof(long long int), compare_int);
  /*for (i = 0; i < 100; i++) {
    printf("%lld ", s[i]);
  }*/
  long long int N;
  scanf("%lld", &N);
  long long int ans=0;
  while(s[ans]<=N){ans++;}
  printf("%lld", ans);
  return 0;
}


Measured memory_bytes: 1916
#include <stdio.h>

void core() {
	int a,b,c;
	scanf("%d",&a);
	scanf("%d",&b);
	scanf("%d",&c);

	printf("%d\n", 3-(a==b)-(b==c)-(c==a)+(a==b&&b==c));
}

int main() {
	core();
	return 0;
}



Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

int main() {

  int N;
  Scd(N);
  vi a(N); 
  vi s(N+1);
  Rep(i,N) Scd(a[i]), s[i+1] = s[i] ^ a[i];
  
  Rep(i,N){
    printf( "%d%s", s[i] ^ s[i+1] ^ s[N], i != N ? " " : "\n" );
  }
  
  
}



Measured memory_bytes: 4832
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
int N,D;
int main(){
    cin >> N >> D;
    if(N%(2*D+1)==0)cout << N/(2*D+1) << endl;
    else cout << N/(2*D+1)+1 << endl;
    return 0;

}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    private static final Scanner sc = new Scanner(System.in);

    private void run() {
        int N = sc.nextInt();
        int K = sc.nextInt();

        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < K; i++) {
            int n = sc.nextInt();
            for (int j = 0; j < n; j++) {
                set.add(sc.nextInt());
            }
        }

        int ans = 0;
        for (int i = 1; i <= N; i++) {
            if (!set.contains(i)) {
                ++ans;
            }
        }
        System.out.println(ans);
    }

    public static void main(String[] args) {
        new Main().run();
    }
}


Measured memory_bytes: 46140