akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define VIEW(x) do {cerr << #x << ": "; for(auto i : x) cerr << i << " "; cerr << endl;} while(0)
#define ALL(x) (x).begin(),(x).end()
template<class T>bool umax(T &a, const T &b) {if(a<b){a=b;return 1;}return 0;}
template<class T>bool umin(T &a, const T &b) {if(b<a){a=b;return 1;}return 0;}

template<typename A,size_t N,typename T> void FILL(A (&array)[N],const T &val){fill((T*)array,(T*)(array+N),val);}
template<typename T> void FILL(vector<T> &v, const T &x) {fill(v.begin(), v.end(), x);}
template<typename T> void FILL(vector<vector<T>> &v, const T &x) {for(auto &i:v)fill(i.begin(), i.end(), x);}

int main() {
  int n; cin >> n;
  int z=0, p=0, m=0;

  multiset<int> a;
  int s = 0;
  rep(i,n) {
    int ai; cin >> ai;
    if(ai==0) z++;
    if(ai>0) p++;
    if(ai<0) m++;
    s+=abs(ai); 
    a.insert(ai);
  }

  if(m==n) {
    s += 2 * (*a.rbegin());
    cout << s << endl;
    int c = *a.rbegin();
    a.erase(prev(a.end()));
    while(a.size()) {
      cout << c << " " << *a.begin() << endl;;
      c -= *a.begin();
      a.erase(a.begin());
    }
    return 0;
  }
  if(p==n) {
    s -= 2 * (*a.begin());
    cout << s << endl;
    int c = *a.begin();
    a.erase(a.begin());
    while(a.size()>1) {
      cout << c << " " << *a.begin() << endl;
      c -= *a.begin();
      a.erase(a.begin());
    }
    cout << *a.begin() << " " << c << endl;
    return 0;
  }

  cout << s << endl;
  int c = *a.begin();
  a.erase(a.begin());
  while(p>1) {
    cout << c << " " << *a.rbegin() << endl;
    c -= *a.rbegin();
    a.erase(prev(a.end()));
    p--;
  }
  a.insert(c);
  c = *a.rbegin();
  a.erase(prev(a.end()));
  while(a.size()) {
    cout << c << " " << *a.begin() << endl;
    c -= *a.begin();
    a.erase(a.begin());
  }
}


Measured memory_bytes: 8212
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <utility>
#include <iomanip>
#include <cmath>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);++i)
#define rep(i,a,b) for(int i=a;i<(b);++i)
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
using ll = long long;
constexpr ll INF = 1LL << 60;
constexpr ll MOD = 1e9 + 7;

int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    int N,M,X,t; cin >> N >> M >> X;
    vector<bool> A(N);
    REP(i,M){
        cin >> t;
        A[t] = true;
    }
    ll ans = INF;
    ll cnt = 0;
    for(int i=X; i>=0; --i){
        if(A[i]) ++cnt;
    }
    chmin(ans,cnt);
    cnt = 0;
    for(int i=X; i<=N; ++i){
        if(A[i]) ++cnt;
    }
    chmin(ans,cnt);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
// Seek Knowledge from the cradle to the grave
// Author : Syed Mujtaba Hadi Jafri
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[100004][104][2];
signed main()
{
	string k;
	int d, ans = -1;
	int mod = 1e9 + 7;
	cin >> k >> d;
	vector < int > dig;
	for(auto z : k)
		dig.push_back(z - '0');
	reverse(dig.begin(), dig.end());
	int n = dig.size();
	for(int i = 0; i < d; i++) // Base Case
	{
		for(int j = 0; j <= 9; j++)
		{
			if((j + i)%d == 0)
				dp[0][i][0]++;		
			if(j <= dig[0])
				if((j + i)%d == 0)
					dp[0][i][1]++;						
		}
	}
	for(int i = 1; i < n; i++)
	{
		for(int j = 0; j < d; j++)
		{
			for(int z = 0; z <= 9; z++)
			{
				dp[i][j][0] = (dp[i][j][0]%mod + dp[i - 1][(j + z)%d][0]%mod)%mod;
				if(z < dig[i])
				{
					dp[i][j][1] = (dp[i][j][1]%mod + dp[i - 1][(j + z)%d][0]%mod)%mod;
				}
				if(z == dig[i])
				{
					dp[i][j][1] = ((dp[i][j][1])%mod + (dp[i - 1][(j + z)%d][1])%mod)%mod;
				}
				
			}
		}
	}
	cout << (dp[n - 1][0][1] - 1 + mod)%mod<< endl;
}

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

// ?????°???????????\?£??????¨???????????????????????°?°????????§£???????????????
// ?????°???????????\?£???? - Wikipedia [https://ja.wikipedia.org/wiki/%E3%83%A9%E3%82%B0%E3%83%A9%E3%83%B3%E3%82%B8%E3%83%A5%E8%A3%9C%E9%96%93]

int main()
{
  int N;
  double v[8];
  
  while(cin >> N, N) {
    for(int i = 0; i < N + 3; i++) cin >> v[i];

    int ret = N + 2;
    for(int i = 0; i <= N + 1; i++) {
      double c = 0;
      for(int j = 0; j <= N + 1; j++) {
        if(i == j) continue;
        double tmp = 1;
        for(int k = 0; k <= N + 1; k++) {
          if(i == k || j == k) continue;
          tmp *= (N + 2 - k) * 1.0 / (j - k);
        }
        c += tmp * v[j];
      }
      if(fabs(c - v[N + 2]) < 1e-3) {
        ret = i;
        break;
      }
    }
    cout << ret << endl;
  }
}

Measured memory_bytes: 1232
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}
 
#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};
 
    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}
 
#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };
 
    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };
 
    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };
 
    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };
 
    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };
 
    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        S: String, 
        T: String, 
    }
    let mut start = vec![None;26];
    let mut goal = vec![None;26];

    for (s, t) in S.chars().zip(T.chars()) {
        let a = s as usize - 'a' as usize;
        let b = t as usize - 'a' as usize;

        if start[a].is_some() | goal[b].is_some() {
            if start[a] != Some(b) || goal[b] != Some(a) {
                println!("No");
                return;
            }
        }

        start[a] = Some(b);
        goal[b] = Some(a);

    }
    println!("Yes");
}


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

#define step(i, s, n, d) for(int i=s; i<n; i+=d)
#define FOR(i,s,n) step(i,s,n,1)
#define rep(i,n) FOR(i,0,n)
#define gets(x) x; cin >> x;
#define puts(x) x; cout << x << endl;
#define list_input(x, n) x[n]; rep(i,n){ gets(x[i]);}
#define ll long long

ll h, w, Sa, Sb, Sc, BWidth, now1, now2, result = 100000;

ll Calc(ll h, ll w, int i){
  Sa = i*w;
  BWidth = w/2;
  Sb = (h-i)*BWidth;
  Sc = (h-i)*(w-BWidth);
  now1 = max({Sa, Sb, Sc}) - min({Sa, Sb, Sc});

  BWidth = (h-i)/2;
  Sb = w*BWidth;
  Sc = w*((h-i)-BWidth);
  now2 = max({Sa, Sb, Sc}) - min({Sa, Sb, Sc});

  return min(now1, now2);
}


int main(){
  cin >> h >> w;
  if (h == 2 && w == 2) {
    puts(1)
    exit(0);
  }
  FOR(i, 1, h-1){
    result = min(result, Calc(h,w,i));
  }
  FOR(i, 1, w-1){
    result = min(result, Calc(w,h,i));
  }
  puts(result)
}


Measured memory_bytes: 256
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    S=ST()
    before = " "
    RLE = []
    string = []
    for s in S:
        if s==before:
            RLE[-1] += 1
        else:
            RLE.append(1)
            string.append(s)
        before = s
    # print(RLE)
    # print(string)

    A = [-1]*(len(S)+1) ##最後に0で初期化
    if string[0]=="<":
        A[0]=0
    now = 0
    for i,x in enumerate(RLE):
        s = string[i]
        now += x
        if s=="<":
            pass
        else: #>
            A[now] = 0
    i=0
    while i<(len(S)+1):
        if A[i]==0:
            j=i-1
            while j>=0:
                if S[j]==">":
                    A[j]=max(A[j],A[j+1]+1)
                    j-=1
                else:
                    break

            j=i
            while j<len(S):
                if S[j]=="<":
                    A[j+1]=max(A[j+1],A[j]+1)
                    j+=1
                else:
                    break
        i+=1


    # print(A)
    print(sum(A))

if __name__ == '__main__':
    main()

Measured memory_bytes: 73508
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
using namespace std;
static const double EPS = 1e-10;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define sz(a) a.size()
#define all(a) a.begin(),a.end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define SS stringstream
#define DBG1(a) rep(_X,sz(a)){printf("%d ",a[_X]);}puts("");
#define DBG2(a) rep(_X,sz(a)){rep(_Y,sz(a[_X]))printf("%d ",a[_X][_Y]);puts("");}
#define bitcount(b) __builtin_popcount(b)
#define REP(i, s, e) for ( int i = s; i <= e; i++ )  

string b;
string p[4] = {"0xxxxxxx","110yyyyx10xxxxxx","1110yyyy10yxxxxx10xxxxxx","11110yyy10yyxxxx10xxxxxx10xxxxxx"};

int dp[8010][4][33][2];
int dfs(int x,int pat,int pos,int done){
	int &res = dp[x][pat][pos][done];
	if( res != -1 ) return res;
	int ans = 0;
	if( pos == p[pat].size() ){
		if( !done ) return 0;
		if( x == b.size() ) return 1;
		ans += dfs(x,0,0,1);
		ans += dfs(x,1,0,0);
		ans += dfs(x,2,0,0);
		ans += dfs(x,3,0,0);
		ans %= 1000000;
		return ans;
	}
	if( x == b.size() ) return 0;
	for(int num = '0' ; num <= '1' ; num++){
		if( b[x] != 'x' && b[x] != num ) continue;
		int nextDone = done;
		if( p[pat][pos] == 'y' && num == '1' ) nextDone = 1;
		if( p[pat][pos] != 'x' && p[pat][pos] != 'y' && p[pat][pos] != num ) continue;
		ans += dfs(x+1,pat,pos+1,nextDone);
	}
	ans %= 1000000;
	return res = ans;
}
int main(){
	int N;
	while(cin >> N && N){
		memset(dp,-1,sizeof(dp));
		b = "";
		for(int i = 0 ; i < N ; i++){
			string s;
			cin >> s;
			b += s;
		}
		int ans = 0;
		ans += dfs(0,0,0,1);
		ans += dfs(0,1,0,0);
		ans += dfs(0,2,0,0);
		ans += dfs(0,3,0,0);
		ans %= 1000000;
		cout << ans << endl;
	}
	
}

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

int main()
{
    ll N,A,B;
    cin >> N >> A >> B;
    ll count=A*(N/(A+B));
    ll t=N%(A+B);
    if(t>A){
        count+=A;
    }else{
        count+=t;
    }
    cout << count << endl;
}

Measured memory_bytes: 256
import sys
from collections import deque
n,q = map(int, input().split())
S = []
for i in range(n):
    S.append(deque())

for i in range(q):
    l = list(map(int,input().split()))
    if l[0] == 0:
        S[l[1]].appendleft(l[2])
    elif l[0] == 1:
        if not S[l[1]]:
            continue
        else:
            print(S[l[1]][-1])
    elif S[l[1]]:
        S[l[1]].pop()




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

int main() {
  int n,k,x,y;
  cin >> n >> k >> x >> y;
  if ( n > k ) {
    cout << k * x + (n-k) * y << endl;
  }
  else {
    cout << n * x << endl;
  }
  return 0;
}



Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
    int n;
    scanf("%d", &n);

    int x[n], sum = 0;
    for (int i = 0; i < n; i++) {
        scanf(" %d", &x[i]);
        sum += x[i];
    }

    float center = (float) sum / (float) n, center_diff;
    int p;
    long long int result = 0;
    center_diff = center - (int) center;
    if (!center_diff) {
        p = center;
    } else if (center_diff < 0.5) {
        p = (int) center;
    } else {
        p = (int) center + 1;
    }
    for (int i = 0; i < n; i++) {
        int diff = p - x[i];
        diff *= diff;
        result += diff;
    }

    printf("%lld\n", result);
    return 0;
}

Measured memory_bytes: 128
// Problem: E - Coprime
// Contest: AtCoder - AtCoder Beginner Contest 177
// URL: https://atcoder.jp/contests/abc177/tasks/abc177_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

// Muallif: Azimjon Mehmonali o'g'li

//=========================================================

// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization ("unroll-loops")

//=========================================================
#ifdef DEBUG
#define xtp xtp1
#else
#define xtp(x)
#endif
//=========================================================

#include <bits/stdc++.h>

using namespace std;

#define int long long

typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

#define F first
#define S second
#define pb push_back
#define endl "\n"

#define ALL(a) (a).begin(), (a).end()
#define rALL(a) (a).rbegin(), (a).rend()
#define SORT(a) sort(ALL(a))
#define rSORT(a) sort(rALL(a))
#define REV(a) reverse(ALL(a))
#define sqr(x) ((x) * (x))

#define TEZ                  \
	ios::sync_with_stdio(0); \
	cin.tie(0);

const long double PI = 3.1415926535897;
const int mod = 1000000007LL;
const int INF = 1e18;

int p[1000010], t[1000010];

signed main() {
	TEZ;

	int n;
	cin >> n;

	vi a(n);
	int gc = 0;
	bool pr = 1;
	for (int &i : a) {
		cin >> i, gc = gcd(gc, i);

		if (p[i] && i != 1) {
			pr = 0;
		}

		p[i] = 1;
	}

	memset(t, 1, sizeof(t));

	t[0] = t[1] = 0;

	for (int i = 2; i <= 1000005; i++) {
		if (t[i]) {
			bool ish = 0;
			for (int j = i; j <= 1000005; j += i) {
				t[j] = 0;
				if (p[j]) {
					if (ish) {
						pr = 0;
						i = 2e7;
						break;
					} else {
						ish = 1;
					}
				}
			}
		}
	}

	if (pr)
		cout << "pairwise coprime" << endl;
	else if (gc == 1)
		cout << "setwise coprime" << endl;
	else
		cout << "not coprime" << endl;

	return 0;
}


Measured memory_bytes: 26340
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(int argc, char const *argv[])
{
    string S;
    cin >> S;

    int cnt0 = 0;
    int cnt1 = 0;
    for (char c : S)
    {
        if (c == '1') cnt1++;
        if (c == '0') cnt0++;
    }

    cout << min(cnt1, cnt0) * 2 << endl;

    return 0;
}

Measured memory_bytes: 512
#include<stdio.h>
int main(){
  int n,a[1000];
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  for(int i=n-1;i>0;i--){
    printf("%d ",a[i]);
  }
  printf("%d\n",a[0]);
  return 0;
}



Measured memory_bytes: 2104
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
string s[N];
int p[5],ans[N];
int n;
void solve(int i,int x,int y) {
	int x0,y0;
	if (p[x]>p[y]) {
		ans[i]=y; p[x]--; p[y]++;
	}
	else if (p[x]<p[y]) {
		ans[i]=x; p[x]++; p[y]--;
	}
	else if (p[x]>1) {
		ans[i]=x; p[x]++; p[y]--;
	}
	else if (p[x]==0) {
		cout<<"No"<<endl;
		exit(0);
	}
	else {
		if (i==n) {
			ans[i]=x; p[x]++; p[y]--; return;
		}
		x0=s[i+1][0]-'A'; y0=s[i+1][1]-'A';
		if (x0==x&&y0==y) {
			ans[i]=x; p[x]++; p[y]--; return;
		} 
		if (x==x0||x==y0) {
			ans[i]=x; p[x]++; p[y]--; return;
		}
		else {
			ans[i]=y; p[x]--; p[y]++; return;
		}
	}
}
int main() {
	int i;
	ios::sync_with_stdio(false);
	cin>>n>>p[0]>>p[1]>>p[2];
	for (i=1;i<=n;i++) 
		cin>>s[i];
	for (i=1;i<=n;i++) {
		if (s[i]=="AB") solve(i,0,1);
		else if (s[i]=="BC") solve(i,1,2);
		else solve(i,0,2); 
	}
	cout<<"Yes"<<endl;
	for (i=1;i<=n;i++)
		cout<<char(ans[i]+'A')<<endl;
	return 0;
}

Measured memory_bytes: 7168
#include <iostream>
using namespace std;
int main()
{
	int a;
	cin>>a;
	int b=a, c=a;
	if((a % 10) == 7){
		cout<<"Yes"<<endl;
		return 0;
	}
	b = b / 10;
	if((b % 10) == 7){
		cout<<"Yes"<<endl;
		return 0;
	}
	if((c / 100) == 7){
		cout<<"Yes"<<endl;
		return 0;
	}
	cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define vi vector<ll>
#define vvi vector<vi>
#define DBG_N(hoge) cerr<<" "<<(hoge)<<endl;
#define DBG cerr<<"!"<<endl;
#define BITLE(n) (1LL<<((ll)n))
#define BITCNT(n) (__builtin_popcountll(n))
#define SUBS(s,f,t) ((s).substr((f)-1,(t)-(f)+1))
#define ALL(a) (a).begin(),(a).end()
using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll a,b,c,d,e;
  string s,ss,sss;
  cin>>a>>b;
  b*=2;
  b++;
  cout<<(int)ceil((double)a/(double)(b))<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

int main(){
	int d;
	while(std::cin >> d){
		int sum = 0, num_block = (600 / d) - 1;
		for(int i = 1 ; i <= num_block ; ++i){
			sum += (d * (d * d * i * i));
		}
		std::cout << sum << std::endl;
	}
    return 0;
}

Measured memory_bytes: 1160
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;

class Solution {
public:
    long long solve(string& s) {
        const int N = 2019;
        vector<long long> Ms{3, 673};
        vector<long long> Os{1, 1};
        vector<long long> Xs{0, 0};

        vector<vector<long long>> cnts(Ms[0], vector<long long>(Ms[1], 0));
        cnts[0][0] = 1;
        int n = s.length();

        long long res = 0;
        for (int i = n - 1; i >= 0; --i) {
            int d = s[i] - '0';

            for (int j = 0; j < 2; ++j) {
                Xs[j] = (d * Os[j] % Ms[j] + Xs[j]) % Ms[j];
            }

            if (d != 0) {
                res += cnts[Xs[0]][Xs[1]];
                cnts[Xs[0]][Xs[1]] += 1;
            }
            // cout << i << " " << Xs[0] << " " << Xs[1] << endl;
            for (int j = 0; j < 2; ++j) {
                Os[j] = Os[j] * 10 % Ms[j];
            }
        }

        return res;
    }
};

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    string s;
    cin >> s;
    Solution sol;
    cout << sol.solve(s) << "\n";

    return 0;
}

Measured memory_bytes: 3772
#include<cstdio>
#include<cstring>

int main(){
	char S[1010];
	
	scanf("%s", S);
	int len=strlen(S);
	if(len<2){
		printf("No");
		return 0;
	}

	int n=0, s=0, e=0, w=0;
	for(int i=0;i<len;i++){
		if(S[i]=='N')
			n++;
		if(S[i]=='W')
			w++;
		if(S[i]=='E')
			e++;
		if(S[i]=='S')
			s++;
	}
	int ans=0;
	if((n>0 && s>0) || (n==0 && s==0)){
		if((e>0 && w>0) || (e==0 && w==0))
			ans=1;
	}
	else
		ans=0;

	if(ans==1)
		printf("Yes");
	else
		printf("No");
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

using namespace std;

void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V>
void __print(const pair<T, V> &x) {
    cerr << '{';
    __print(x.first);
    cerr << ',';
    __print(x.second);
    cerr << '}';
}
template <typename T>
void __print(const T &x) {
    int f = 0;
    cerr << '{';
    for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
    cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
    __print(t);
    if (sizeof...(v)) cerr << ", ";
    _print(v...);
}
#ifdef LOCAL
#define debug(x...)               \
    cerr << "[" << #x << "] = ["; \
    _print(x)
#else
#define debug(x...)
#endif

#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    double a, b, x;
    cin >> a >> b >> x;

    double pi = 2.0 * asin(1.0);

    if (x < 0.5 * a * a * b) {
        cout << setprecision(20)
             << 90.0 - atan(2.0 * x / (a * b * b)) * 180.0 / pi << endl;
    } else {
        cout << setprecision(20)
             << 90 - abs(atan((a * a * a) / (2 * (x - a * a * b))) * 180.0 / pi)
             << endl;
    }
    return 0;
}


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

int main() {
	int N, A, B;
	cin >> N >> A >> B;
	if (N != 3) {
		if ((B - A) % 2 == 0) {
			cout << "Alice" << endl;
		}
		else {
			cout << "Borys" << endl;
		}
	}
	else {
		if (A == 1 && B == 3) {
			cout << "Alice" << endl;
		}
		else {
			cout << "Borys" << endl;
		}
	}
}

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

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

  int R, C;
  while (cin >> R >> C, R | C) {
    vector<vector<int>> field(C, vector<int>(R));
    for (int y = 0; y < R; ++y)
      for (int x = 0; x < C; ++x)
        cin >> field[x][y];
    int ans = 0;
    for (int S = 0; S < (1 << R); ++S) {
      int sum = 0;
      for (int x = 0; x < C; ++x) {
        int count = 0;
        for (int y = 0; y < R; ++y)
          count += field[x][y] ^ ((S >> y) & 1);
        sum += max(count, R - count);
      }
      ans = max(ans, sum);
    }
    cout << ans << endl;
  }
}

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

int main(){
  int n;
  int x;
  int ushi;
  int uma;
  int yagi;
  int shika;
  while(true){
    cin>>n>>x;
    if(n==0&&x==0){
      break;
    }else{
      for(int ushi=1;ushi<n+1;ushi++){
    for(int uma=ushi;uma<n+1;uma++){
      for(int yagi=uma;yagi<n+1;yagi++){
	if(ushi==uma||uma==yagi||yagi==ushi){
	  ushi=ushi;
	}else if(ushi+uma+yagi==x){
	  shika++;}
      }
    }
      }
    cout<<shika<<endl;
    shika=0;
    }
  }
}

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

int main() {
  int A , N , C , B;
  cin >> N >> A >> C >> B;
  if  ((A + N) > (C + B)) {
    cout << "Left" << endl;
  }
  else   if  ((A + N )== (C + B)) {
    cout << "Balanced" << endl;
  }
   else if  ((A + N) < (C + B)) {
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>

using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
typedef long long ll;
typedef unsigned long long ull;

int main()
{
	char C[2][3];
	rep(i, 2) {
		rep(j, 3) cin >> C[i][j];
	}

	if ((C[0][0] == C[1][2])
		&& (C[0][1] == C[1][1])
		&& (C[0][2] == C[1][0])) cout << "YES" << endl;
	else cout << "NO" << endl;

	return 0;
}


Measured memory_bytes: 256
"use strict";
    
const main = arg => {
    arg = arg.trim().split("\n");
    const S = arg[0].split("");
    
    let answer = "-1 -1";
    
    for(let i=0; i<S.length-1; i++) {
        let next = S[parseInt(i) + 1];
        let nextNext = S[parseInt(i) + 2];
         
        // XX が存在すればそれが答え
        if(S[i] === next) {
            answer = (parseInt(i) + 1) + " " +  (parseInt(i) + 2);
            break;
        }
        
        // XYXが存在すればそれが答え
        if(S[i] === nextNext) {
            answer = (parseInt(i) + 1) + " " +  (parseInt(i) + 3);
            break;
        }
    }
    
    console.log(answer);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 8384
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using P=pair<long long,long long>;
#define rep(i,n) for(long long i=0; i<(long long)n; i++)
#define req(i,n) for(long long i=n-1; i>=0; i--)
#define range(i,a,b) for(long long i=a; i<b; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((long long)(x).size())
#define COUT(x) cout << x << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define onBoard(y,x) (y>=0 && y<h && x>=0 && x<w)
#define pri_que priority_queue
#define vint vector<int>
#define vvint vector<vector<int>>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vs vector<string>
#define vvc vector<vector<char>>
#define vc vector<char>
#define vp vector<pair<int,int>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define show(x) cout<<#x<<"="<<x<<endl;
#define SUM(x) accumulate(x.begin(),x.end(),0)
#define MAX(x) *max_element(x.begin(),x.end())
#define MIN(x) *min_element(x.begin(),x.end())
#define couty cout<<"Yes"<<endl
#define coutn cout<<"No"<<endl
#define coutY cout<<"YES"<<endl
#define coutN cout<<"NO"<<endl
#define yn(x) cout<<(x?"Yes":"No")<<endl
#define YN(x) cout<<(x?"YES":"NO")<<endl
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcm(long long a, long long b){return a/gcd(a,b)*b;}
const long long dx[8]={1,0,-1,0,1,-1,-1,1};
const long long dy[8]={0,1,0,-1,1,1,-1,-1};
const long long INF = 1e12;
const long long MOD = 1e9+7;

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(15);

    int n; string s,t;cin>>n>>s>>t;
    int max=0;
    for(int i=1; i<=n; i++){
        if(s.substr(n-i,i)==t.substr(0,i)) chmax(max,i);
    }   
    cout<<2*n-max<<endl;
}

Measured memory_bytes: 3648
#!/usr/bin/env python3

from collections import Counter

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    n = int(input())
    a = list(map(int, input().split()))
    m = Counter([i - elem for i, elem in enumerate(a)])
    ans = 0
    for i, elem in enumerate(a):
        ans += m[i + elem]
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 42928
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(a,b) memset(a,b,sizeof(a))
#define msn(a,n,b) for(int i=0;i<=n;i++)a[i]=b
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define fi first
#define se second
using namespace std;
mt19937 rng_32(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef double db;
const int mod=1e9+7;
const int seed=233;
const double PI=acos(-1.0);
const double eps=1e-7;
const int inf=0x3f3f3f3f;
const int max_n=100005;
ll ceil(ll x,ll y){if(x==0)return 0;if(y<0)x=-x,y=-y;bool sign=x>0;x=abs(x);return sign?(x+y-1)/y:-x/y;}
ll floor(ll x,ll y){if(x==0)return 0;if(y<0)x=-x,y=-y;bool sign=x>0;x=abs(x);return sign?x/y:-(x+y-1)/y;}
namespace {
    inline int Add(int x,int y){return (x+=y)>=mod?x-mod:x;}
    inline int Sub(int x,int y){return (x-=y)<0?x+mod:x;}
    inline int Mul(int x,int y) {return 1ll*x*y%mod;}
    inline int Pow(int x,int y=mod-2){if(y==0)return 1;int res=1;while(y){if(y&1)res=1ll*res*x%mod;x=1ll*x*x%mod;y>>=1;}return res;}
}
/**********************head************************/
ll n;
bool check(ll k){
    if(k==1)return false;
    ll x=n;
    while(x%k==0)x/=k;
    return x%k==1;
}
int main(){
    scanf("%lld",&n);
    ll ans=0;
    for(int i=1;1ll*i*i<=n;i++){
        if(n%i)continue;
        if(check(i))ans++;
        if(n/i!=i&&check(n/i))ans++;
    }
    //cout<<"fff"<<endl;
    ll x=n-1;
    for(int i=1;1ll*i*i<=x;i++){
        if(x%i)continue;
        if(n%i)ans++;
        if(x/i!=i&&n%(x/i))ans++;
    }
    printf("%lld\n",ans);
    return 0;
}

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


ll t[200050][2];
ll MAX = 100005;

class UnionFind{
    public:
    //親の番号を格納する。親だった場合は-(その集合のサイズ)
    vector<int> parent;

    //-1で初期化。最初はすべてバラバラ
    UnionFind(int N){
        parent = vector<int>(N,-1);
    }

    //Aがどのグループに属しているか(Aの根)を調べる
    int root(int A){
        if(parent[A] < 0) return A;
        return parent[A]=root(parent[A]);
    }

    //自分のいるグループの頂点数を調べる
    int size(int A){
        return -parent[root(A)];
    }

    //AとBをくっつける
    bool unite(int A, int B) {
    //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        //既にくっついているからくっつけない
        if(A == B) return false; 

        //大きいほう(A)に小さいほう(B)をくっつける
        //大小が逆ならひっくり返す
        if(size(A) < size(B)) swap(A,B);

        //Aのサイズを更新する
        parent[A] += parent[B];
        //Bの親をAに変更する
        parent[B] = A;
        t[A][0] += t[B][0];
        t[A][1] += t[B][1];
        return true;
    }

    //AとBが同じグループならtrueを返す
    bool same(int A, int B){
        return root(A)==root(B);
    } 
};


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
    
    ll n;
    cin>>n;
    UnionFind uni(200050);
    for(int i=0;i<MAX;i++){
        t[i][0]=1;
    }
    for(int i=MAX;i<MAX+MAX;i++){
        t[i][1]=1;
    }
    for(int i=0;i<n;i++){
        ll x,y;
        cin>>x>>y;
        uni.unite(x,y+MAX);
    }
    ll ans = 0;
    for(int i=0;i<MAX+MAX;i++){
        if(uni.root(i) == i && t[i][0] && t[i][1]){
            ll ret = t[i][0] * t[i][1];
            ans += ret;
            //cerr<<t[i][0] * t[i][1]<<endl;
        }
    }
    ans -= n;
    cout << ans << endl;
}

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

int main() {
	while (1) {
		int a;
		cin >> a;
		if (a == 0)break;
		for (int b = 0; b < a; b++) {
			int  c, d, e;
			cin >> c >> d >> e;
			if (c == 100 || d == 100 || e == 100)cout << "A" << endl;
			else if (c+d>179)cout << "A" << endl;
			else if(c+d+e>239)cout << "A" << endl;
			else if(c+d+e>209)cout << "B" << endl;
			else if((c+d+e>149)&&(c>79||d>79))cout << "B" << endl;
			else cout << "C" << endl;
		}
   }
}

Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
#define int long long
//ask the right questions.		

int32_t main() 
{
	int N, W;
	cin >> N >>W;
	int weights[N];
	int value[N];

	int x;
	for(int i=0;i<2*N;i++)
	{
		cin >> x;
		if(i%2==0)
		{
			weights[i/2]=x;
		}
		else
		{
			value[(i-1)/2]=x;
		}
	}

	//let denote the max value when you have capacity_left of w and deciding upon nth item.
	int dp[W+1];

	for(int i=0;i<=W;i++)
		dp[i]=0;


	//TIP:
	//you are deciding on the ith item: to take or not
	//if you want to take then you look previously for a state with wight gap of at least 
	//weight[i-1] (ie weight of ith item)
	//you need not look for a greater gap as the max value obtained by a state with greater
	//weight capacity will always be equal or greater than max value obtained by a lower weight capacity state.


	// shift i-1 in weights and values
	for(int i=1; i<=N; i++)
	{
		for(int j=W; j>=1; j--)
		{
			if(j>=weights[i-1])      		
			{				
				dp[j] = max(dp[ j-weights[i-1] ] + value[i-1], dp[j]);
			}
		}		
	}

	cout << dp[W] <<endl;

	return 0;
	
}

Measured memory_bytes: 4352
from functools import lru_cache
N = int(input())

A = []
B = []
food = []

for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
    food.append((a + b, i))

food.sort(reverse=True)
X = 0
Y = 0
cnt = 0

for _, i in food:
    if cnt % 2 == 0:
        X += A[i]
    else:
        Y += B[i]
    cnt += 1

print(X - Y)

Measured memory_bytes: 25828
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  int n;
  cin >> n;
  vector <int>num(n);
  rep(i,n) cin >> num[i];
  int ans=0;
  while(true){
    int x = 0;
    rep(i,n){
      if(num[i]%2==0) x++;
    }
    if (x == n){
      ans++;
      rep(i,n) num[i] /= 2;
    }
      else break;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

int main(){
    int N, M, X; cin >> N >> M >> X;
    vector<int> a(M);

    for(int i=0; i<M; ++i) cin >> a[i];
    int left = 0, right = 0;
    for(int i=0; i<M; ++i){
        if(a[i] < X) ++left;
        else ++right;
    }

    cout << min(left, right) << endl;

    return 0;
}

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

#define int long long
#define itn int
#define For(i, a, b) for (int i = (a); i <= static_cast<int>(b); i++)
#define Forr(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) For(i, 0, n - 1)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'
#define dump2(x, y) \
    cerr << #x << " = " << (x) << " " << #y << " = " << (y) << '\n'
#define SZ(x) ((int)(x).size())
#define bit(n) (1LL << (n))
constexpr int MOD = 1e9 + 7;

// clang-format off
template<typename T>
bool chmax(T& a, const T& b) {if (a<b){a=b;return true;}return false;}
template<typename T>
bool chmin(T& a, const T& b) {if (a>b){a=b;return true;}return false;}
// clang-format on

template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = LLONG_MAX / 2;
using P = pair<int, int>;
using vec = vector<int>;
using mat = vector<vec>;

template <typename T1, typename T2>
ostream& operator<<(ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << " " << p.second;
}
template <typename T>
void print(const vector<T> vec) {
    unsigned int len = vec.size();
    rep (i, len - 1)
        cout << vec[i] << ' ';
    cout << vec[len - 1] << '\n';
}
template <typename Arg>
void print(const Arg arg) {
    cout << arg << '\n';
}
template <typename Head, typename... Args>
void print(const Head head, const Args... args) {
    cout << head << " ";
    print(args...);
}
template <typename T>
T sum_(vector<T> vec, T init = 0) {
    return std::accumulate(all(vec), T(init));
}

void yn(bool tf) { print(tf ? "Yes" : "No"); }
void YN(bool tf) { print(tf ? "YES" : "NO"); }

template <typename T>
void init(vector<T>& v) {
    rep (i, v.size())
        cin >> v[i];
}

template <typename T, typename U>
void init(vector<T>& v, vector<U>& w) {
    assert(v.size() == w.size());
    rep (i, v.size())
        cin >> v[i] >> w[i];
}

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

// -------------------------------------------------------------------
// sort 1 2 3 4
// pqr 1 2 3 must impl >

signed main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vec a(n);
    init(a);
    multiset<int, greater<int>> m;
    m.insert(a[0]);

    For(i, 1, n - 1) {
        auto ho = m.upper_bound(a[i]);
        if (ho != m.end()) m.erase(ho);
        m.insert(a[i]);
    }
    print(m.size());

    return 0;
}


Measured memory_bytes: 5760
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }
        Arrays.sort(a);
        long[] sum = new long[n];
        sum[0] = a[0];
        for (int i = 1; i < n; i++) {
            sum[i] += sum[i - 1] + a[i];
        }
        int limit = 0;
        for (int i = 0; i < n - 1; i++) {
            if (2 * sum[i] < a[i + 1]) {
                limit = i + 1;
            }
        }
        System.out.println(n - limit);
    }

}


Measured memory_bytes: 50900
// Author: Tyler Wang

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdlib>
#include <deque>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>

using namespace std;

template <typename Container>
std::vector<int> topo_sort(const std::vector<Container>& graph) {
  int n = (int)graph.size();
  std::vector<int> degree(n, 0);
  for (int u = 0; u < n; ++u) {
    for (int v : graph[u]) {
      ++degree[v];
    }
  }
  std::queue<int> q;
  for (int u = 0; u < n; ++u) {
    if (degree[u] == 0) {
      q.push(u);
    }
  }
  std::vector<int> sorted;
  sorted.reserve(n);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    sorted.push_back(u);
    for (int v : graph[u]) {
      if (--degree[v] == 0) {
        q.push(v);
      }
    }
  }
  if ((int)sorted.size() < n) {  // cycle
    return std::vector<int>();
  }
  return sorted;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.precision(12);
  std::cerr.precision(12);
  std::mt19937 rng((std::uint_fast32_t)std::chrono::high_resolution_clock::now()
                       .time_since_epoch()
                       .count());
  int n, m;
  cin >> n >> m;
  vector<vector<int>> graph(n);
  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    graph[x].push_back(y);
  }
  vector<int> sorted = topo_sort(graph);
  vector<int> dp(n);
  for (int u : sorted) {
    for (int v : graph[u]) {
      dp[v] = dp[u] + 1;
    }
  }
  cout << *max_element(dp.begin(), dp.end()) << '\n';
  return 0;
}

Measured memory_bytes: 6528
from collections import deque
#グラフの連結成分を調べる
def Graph(ab):
    G=[[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G

n, m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
G = Graph(ab)

for v in G[0]:
    if n in G[v - 1]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Measured memory_bytes: 106916
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>

using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD (ll)1000000007
#define P pair<ll, ll>


ll n, m, p[100], ans, sz[100];
vector<ll> s[100];
int main() {
	cin >> n >> m;
	REP(i, m) {
		ll a;
		cin >> a;
		REP(j, a) {
			ll b;
			cin >> b;
			s[i].push_back(b);
		}
	}
	REP(i, m)cin >> p[i];
	REP(i, 1ll << n) {
		bool on[110] = {}, ok = true;
		REP(j, n)if (i & (1ll << j))on[j] = true;
		REP(j, m) {
			ll now = 0;
			REP(k, s[j].size()) {
				if (on[s[j][k] - 1])now++;
			}
			if (now % 2 != p[j])ok = false;
		}
		if (ok)ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
// #pragma GCC optimize ("O3")
// #pragma GCC target ("sse4")

#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;
const int NINF = -1*INF;
const long long LLINF = 1ll << 60;
const long long LLNINF = -1*LLINF;

template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ";
    return os << "}";
}

template <class X, class Y>
ostream & operator << (ostream & os, pair <X, Y> const& p) {
	return os << "[ " << p.first << ", " << p.second << "]" ;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<vector<int>> vvi;
 
#define mp make_pair
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()
#define revAll(x) x.rbegin(), x.rend()
#define gcd(a, b) __gcd(a, b)
#define isize(x) (int)(x.size())
#define rep(i,n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define umap unordered_map

// dp[i] = max value at weight i
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	int n, W; cin >> n >> W;
	vi weights = vi(), vals = vi();
	rep(i, n){
		int w, v; cin >> w >> v;
		weights.pb(w);
		vals.pb(v);
	}
	vll dp = vll(W+1, 0);
	dp[0] = 0;
	rep(item, n){
		int w = weights[item], v = vals[item];
		for(int i = W; i >= 0; i--){
			if (i - w < 0) continue;
			dp[i] = max(dp[i], dp[i-w] + v);
		}
	}
	cout << dp[W];
}

Measured memory_bytes: 4000
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)

string s;

int main() {
	getline(cin, s);
	rep(i,s.length()) if ('a'<=s[i] && s[i]<='z') s[i] = s[i] - 'a' + 'A';
	cout << s << '\n';
}


Measured memory_bytes: 3144
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
void add(long long &x, long long y) {
  x += y;
  if (x >= mod) x -= mod;
}
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  string s;
  cin >> s;
  int d;
  cin >> d;
  static long long dp[10005][105][2] = {};
  dp[0][0][0] = 1;
  int n = (int) s.length();
  for (int i = 0; i < n; i++) {
    for (int k = 0; k < 2; k++) {
      int cur = k ? 9 : s[i] - '0';
      for (int j = 0; j < d; j++) {
        for (int l = 0; l <= cur; l++) {
          add(dp[i + 1][(j + l) % d][k || l < cur], dp[i][j][k]);
        }
      }
    }
  }
  cout << (mod + dp[n][0][0] + dp[n][0][1] - 1) % mod << endl; 
  return 0;	
}

Measured memory_bytes: 16640
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>

using namespace std;

typedef long long ll;

int main() {

	int N;
	cin >> N;
	int a = 0, b = 0, c = 0;
	int ans = 0;
	for (int i = 0; i < N; i++) {
		string tmp;
		cin >> tmp;
		if (tmp.front() == 'B' && tmp.back() == 'A')a++;
		else if (tmp.front() == 'B')b++;
		else if (tmp.back() == 'A')c++;
		for (int i = 0; i < tmp.size() - 1; i++) {
			if (tmp[i] == 'A' && tmp[i + 1] == 'B')ans++;
		}
	}

	if (a >= 1)ans += a - 1;
	if (a >= 1 && b >= 1)b--, ans++;
	if (a >= 1 && c >= 1)c--, ans++;
	ans += min(b, c);
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3584
#include<queue>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

#define fir first
#define sec second

typedef long long LL;
typedef pair<int,int> PP;

namespace INPUT{
	const int L=1<<15;
	char _buf[L],*S,*T,c;
	char _gc(){
		if(S==T){
			T=(S=_buf)+fread(_buf,1,L,stdin);
			if(S==T) return EOF;
		}
		return *S++;
	}
	void readi(int &X){
		for(c=_gc();c<'0'||c>'9';c=_gc());X=c&15;
		for(c=_gc();c>='0'&&c<='9';X=X*10+(c&15),c=_gc());
	}
}
using INPUT::readi;

const int Maxn=3E5+5;
const LL INF=(LL)1E17;

int N,X,Y,Z;
PP s[Maxn];
priority_queue<int> q1,q2;
LL Val1[Maxn],Val2[Maxn],Val;
LL Ans;

bool cmp(PP x,PP y){
	return x.fir-x.sec>y.fir-y.sec;
}

int main(){
	readi(X),readi(Y),readi(Z),N=X+Y+Z;
	for(int i=1;i<=N;++i){
		int a,b,c;
		readi(a),readi(b),readi(c);
		Ans+=a,s[i]=PP(b-a,c-a);
	}
	sort(s+1,s+N+1,cmp);
	for(int i=1;i<=Y;++i)
		Val1[Y]+=s[i].fir,q1.push(-s[i].fir);
	for(int i=Y+1;i<=N;++i){
		Val1[i]=Val1[i-1];
		int top=q1.top();
		if(s[i].fir>-top)
			q1.pop(),Val1[i]+=s[i].fir+top,q1.push(-s[i].fir);
	}
	for(int i=N;i>=N-Z+1;--i)
		Val2[N-Z+1]+=s[i].sec,q2.push(-s[i].sec);
	for(int i=N-Z;i>=1;--i){
		 Val2[i]=Val2[i+1];
		 int top=q2.top();
		 if(s[i].sec>-top)
		 	q2.pop(),Val2[i]+=s[i].sec+top,q2.push(-s[i].sec);
	}
	Val=-INF;
	for(int i=Y;i<=N-Z;++i) Val=max(Val,Val1[i]+Val2[i+1]);
	Ans+=Val; cout<<Ans;
	return 0;
}


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

int main() {
	int x, a, b, c, d;
	cin >> x;
	d = x % 10;
	x = (x - d) / 10;
	c = x % 10;
	x = (x - c) / 10;
	b = x % 10;
	a = x / 10;
	if (a + b + c + d == 7)cout << a << "+" << b << "+" << c << "+" << d << "=" << 7 << endl;
	else if (a + b + c - d == 7)cout << a << "+" << b << "+" << c << "-" << d << "=" << 7 << endl;
	else if (a + b - c + d == 7)cout << a << "+" << b << "-" << c << "+" << d << "=" << 7 << endl;
	else if (a + b - c - d == 7)cout << a << "+" << b << "-" << c << "-" << d << "=" << 7 << endl;
	else if (a - b + c - d == 7)cout << a << "-" << b << "+" << c << "-" << d << "=" << 7 << endl;
	else if (a - b + c + d == 7)cout << a << "-" << b << "+" << c << "+" << d << "=" << 7 << endl;
	else if (a - b - c - d == 7)cout << a << "-" << b << "-" << c << "-" << d << "=" << 7 << endl;
	else if (a - b - c + d == 7)cout << a << "-" << b << "-" << c << "+" << d << "=" << 7 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define exrep(i, a, b) for(long long i = a; i <= b; i++)
#define rep(i,n)for(long long i=0;i<(long long)(n);i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vector<ll> > vvl;
typedef vector<vector<P> > vvp;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
const ll MOD=1e9+7;
const ll INF=1e18;
const int MAX=510000;
const double pi=acos(-1);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false); 
  
  int n,k;
  cin >> n >> k;
  vector<bool>vec(n,false);
  rep(i,k){
    int d;
    cin >> d;
    rep(j,d){
      int x;
      cin >> x;
      x--;
      vec[x]=true;
    }
  }
  int cnt=0;
  rep(i,n){
    if(!vec[i])cnt++;
  }
  cout << cnt << endl;
  return 0;     
}


Measured memory_bytes: 3636