Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline

n,u,v = ( int(x) for x in input().split() )

u,v = u-1,v-1

# -1なら行先なし
a = [[] for i in range(n)]
b = [[] for i in range(n)]

for i in range(n-1):
	# 配列indexは0開始だからinputは-1
	l,m = ( int(x)-1 for x in input().split() )
	a[l].append(m)
	a[m].append(l)


def distance(cr,p,dist): # cr:current node, p:pathed or not, dist:out;each distance
	for i in a[cr]: #a[cr]から行ける各頂点へ
		p[cr] = 1
		if p[i] == 0: #まだ通っていなかったら
			p[i] = 1
			dist[i] = dist[cr]+1
			distance(i,p,dist)

# 欲しいのはdist of u-v, back way of u
# u視点のdistを調べる
p = [0]*(n)
dist_v = [0]*(n)
distance(v,p,dist_v)
# v視点のdistを調べる
p = [0]*(n)
dist_u = [0]*(n)
distance(u,p,dist_u)

for i in range(n):
	if dist_u[i] >= dist_v[i]:
		dist_u[i] = -1

tmp = max(dist_u)
max_idx = dist_u.index(tmp)

print(dist_v[max_idx] - 1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

# 再帰上限を引き上げる
sys.setrecursionlimit(10**6)

# G:graph, cr:current node, seen:is seen?, dist:out;each distance
def dfs(G,cr,seen,dist):
	seen[cr] = 1
	for i in G[cr]: #G[cr]から行ける各頂点へ
		if seen[i] == 0: #まだ通っていなかったら
			dist[i] = dist[cr]+1
			dfs(G,i,seen,dist)


n,u,v = (int(x) for x in input().split())

u,v = u-1,v-1

a = [[] for i in range(n)]

for i in range(n-1):
	# 配列indexは0開始だからinputは-1
	l,m = (int(x)-1 for x in input().split())
	a[l].append(m)
	a[m].append(l)

# v視点のdistを調べる
dist_u = [0]*n
dist_v = [0]*n

dfs(a,u,[0]*n,dist_u)
# u視点のdistを調べる
dfs(a,v,[0]*n,dist_v)

for i in range(n):
	if dist_u[i] >= dist_v[i]: # vが追いつける距離なら
		dist_v[i] = -1

print(max(dist_v) - 1)
from itertools import permutations

n,m,q = map(int,input().split())
a = [0]*q
b = [0]*q
c = [0]*q
d = [0]*q

for i in range(q):
    a[i],b[i],c[i],d[i] = map(int,input().split())
    a[i] -= 1
    b[i] -= 1


arr = [0]*(n+m)
for j in range(m):
    arr[j] = 1

ans = 0

for vec in permutations(arr):
    zero_cnt = 0
    score = 0
    A = []
    for k in range(n+m):
        if vec[k] == 0:
            zero_cnt += 1
        else:
            A.append(zero_cnt)

    for l in range(q):
        if A[b[l]] - A[a[l]] == c[l]:
            score += d[l]

    ans = max(ans,score)


print(ans)

### FIXED CODE ###

from itertools import combinations_with_replacement

n,m,q = map(int,input().split())
a = [0]*q
b = [0]*q
c = [0]*q
d = [0]*q

for i in range(q):
    a[i],b[i],c[i],d[i] = map(int,input().split())
    a[i] -= 1
    b[i] -= 1


arr = [0]*(n+m)
for j in range(m):
    arr[j] = 1

ans = 0

for A in combinations_with_replacement(range(1,m+1),n):
    score = 0
    for l in range(q):
        if A[b[l]] - A[a[l]] == c[l]:
            score += d[l]

    ans = max(ans,score)

print(ans)
A, B, T = input()
ans = int(T)/int(A)*int(B)
print(ans)

### FIXED CODE ###

A, B, T = map(int,input().split())
n = (T+0.5) // A
print(int(n*B))
def main():
    N = int(input())
    A = list(map(int, input().split()))
    d = {}
    def prime_factorize(n):
        a = set()
        while n % 2 == 0:
            a.add(2)
            n //= 2
        f = 3
        while f * f <= n:
            if n % f == 0:
                a.add(f)
                n //= f
            else:
                f += 2
        if n != 1:
            a.add(n)
        for i in a:
            d[i] = d.get(i, 0) + 1
    for x in A:
        prime_factorize(x)
    m = max(d.values())
    if m == 1:
        return 'pairwise coprime'
    if m == N:
        return 'not coprime'
    return 'setwise coprime'
print(main())


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    d = {-1:1}
    def prime_factorize(n):
        a = set()
        while n % 2 == 0:
            a.add(2)
            n //= 2
        f = 3
        while f * f <= n:
            if n % f == 0:
                a.add(f)
                n //= f
            else:
                f += 2
        if n != 1:
            a.add(n)
        for i in a:
            d[i] = d.get(i, 0) + 1
    for x in A:
        prime_factorize(x)
    m = max(d.values())
    if m == 1:
        return 'pairwise coprime'
    if m == N:
        return 'not coprime'
    return 'setwise coprime'
print(main())
import sys
sys.setrecursionlimit(10000)


def process():
    for data in get_dataset():
        H = len(data)
        W = len(data[0])
        field = create_field(H, W)
        print search(H, W, data, field)


def search(H, W, data, field):
    count = 0
    for i in xrange(H):
        for j in xrange(W):
            if field[i][j] == 0:
                continue
            _search(i, j, H, W, data[i][j], data, field)
            count += 1
    return count


def _search(i, j, H, W, cell, data, field):
    field[i][j] = 0
    for a in xrange(i-1, i+2):
        if -1 < a < H:
            pass
        else:
            continue
        for b in xrange(j-1, j+2):
            if -1 < b < W:
                pass
            else:
                continue

            if a != i and b != j:
                continue

            if field[a][b] == 0:
                continue
            if cell == data[a][b]:
                _search(a, b, H, W, cell, data, field)
    return


def create_field(H, W):
    field = []
    for i in xrange(H):
        raw = []
        for j in xrange(W):
            raw.append(1)
        field.append(raw)
    return field


def get_dataset():
    dataset = []
    while True:
        line = raw_input().rstrip().split()
        H = int(line[0])
        if H == 0:
            break

        data = []
        for i in xrange(H):
            data.append(raw_input().rstrip())
        dataset.append(data)
    return dataset

process()

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)


def main():
    solve()


def solve():
    for data in get_dataset():
        print search(data)


def search(data):
    count = 0
    H = len(data)
    W = len(data[0])
    for i in xrange(H):
        for j in xrange(W):
            if data[i][j] == '.':
                continue
            _search(i, j, H, W, data[i][j], data)
            count += 1
    return count


def _search(i, j, H, W, cell, data):
    data[i][j] = '.'
    for a in xrange(i-1, i+2):
        if not -1 < a < H:
            continue
        for b in xrange(j-1, j+2):
            if not -1 < b < W:
                continue

            if a != i and b != j:
                continue

            if data[a][b] == '.':
                continue

            if cell == data[a][b]:
                _search(a, b, H, W, cell, data)
    return


def get_dataset():
    dataset = []
    while True:
        line = raw_input().rstrip().split()
        H = int(line[0])
        if H == 0:
            break

        data = []
        for i in xrange(H):
            data.append(list(raw_input().rstrip()))
        dataset.append(data)
    return dataset


if __name__ == '__main__':
    main()
n=int(input())
a=list(map(int, input().split()))
count=0 
def h(L):
  for i in range(len(L)):
    if L[i] % 2 != 0:
      return(1)
  return(0)
while h(a) == 0:
    a[j]=a[j]/2
  count=count+1
  
print(count)


### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
count=0 
def h(L):
  for i in range(len(L)):
    if L[i] % 2 != 0:
      return(1)
  return(0)
while h(a) == 0:
  for j in range(n):
    a[j]=a[j]/2
  count=count+1
  
print(count)
N = input()
fn = 0
for i in range(len(N)):
  fn += int(i)
  
print("Yes" if N % fn == 0 else "No")

### FIXED CODE ###

N = input()
fn = 0
for i in N:
  fn += int(i)
  
print("Yes" if int(N) % fn == 0 else "No")
from collections import Counter
import sys

N = int(input())
D = list(map(int, input().split()))
D = sorted(D)
D_counter = Counter(D)


M = int(input())
T = list(map(int, input().split()))
T = sorted(T)
T_counter = Counter(T)


#一つずつずらしていく、Tのkeyとvalueを取り出す
D_keylist = (list(D_counter.items()))

#一つずつずらしていく、Tのkeyとvalueを取り出す
T_keylist = (list(T_counter.keys()))
T_Valuelist = (list(T_counter.values()))

 
ans = 0
T_index = 0
for i in D_keylist:
    D_key = i[0]
    D_value = i[1]

    T_key = T_keylist[T_index]
    T_value = T_Valuelist[T_index]


    if D_key == T_key and (D_value >= T_value):
        T_index = T_index + 1
        ans = ans + 1
    else:
        pass


if len(T_keylist) == ans:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

from collections import Counter
import sys

N = int(input())
D = list(map(int, input().split()))
D = sorted(D)
D_counter = Counter(D)


M = int(input())
T = list(map(int, input().split()))
T = sorted(T)
T_counter = Counter(T)



D_keylist = (list(D_counter.items()))

T_keylist = (list(T_counter.keys()))
T_Valuelist = (list(T_counter.values()))


ans = 0
T_index = 0

for i in D_keylist:
    D_key = i[0] # N個の問題案の中のi個めの問題案の番号
    D_value = i[1] # N個の問題案の中のi個めの問題案の難易度

    T_key = T_keylist[T_index] # M個の問題案の中のi個めの問題案の番号
    T_value = T_Valuelist[T_index] # M個の問題案の中のi個めの問題案の番号


    if D_key == T_key and (D_value >= T_value): #もしNとMの番号問題が一致しており、なおかつN個の問題の方が難易度が多かったら加算
        T_index = T_index + 1 #もし一致していたら、Mの問題番号を横にひとつずらす
        ans = ans + 1 #加算

        if T_index == M:
            break
    else:
        pass


if len(T_keylist) == ans: #M個の問題を作る事ができればYES,無理ならNO
    print("YES")
else:
    print("NO")
N, M=map(int, input().split())
ac=[0]*N
wa=[0]*N

for i in range(M):
    p, S=input().split()
    p=int(p)
    if ac[p-1]==0:
        if S=="AC":
            ac[p-1]=1
        elif S=="WA":
            wa[p-1]+=1
            
wacnt=0
for i in range(N):
	if ac[i]>=1:
      wacnt+=wa[i]
		
print(sum(ac), wacnt)

### FIXED CODE ###

N, M=map(int, input().split())
ac=[0]*N
wa=[0]*N

for i in range(M):
    p, S=input().split()
    p=int(p)
    if ac[p-1]==0:
        if S=="AC":
            ac[p-1]=1
        elif S=="WA":
            wa[p-1]+=1
            
wacnt=0
for i in range(N):
	if ac[i]>=1:
		wacnt+=wa[i]
		
print(sum(ac), wacnt)
n = int(input())
a = input().split()
m = 1
k = a.index(“B”)
if k == 0:
    print("0")
else:
    for i in range(n):
        m = m * int(a[i])
        if m > 10**18:
        break
    if m > 10**18:
        print("-1")
    else:
        print(m)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
m = 1
for i in range(n):
    if a[i] == 0:
        m = 0
        print("0")

if m == 1:
    for j in range(n):
        m = m * a[j]
        if m > 10**18:
            break
    if m > 10**18:
        print("-1")
    else:
        print(m)
s=list(input())
al=[chr(ord('a') + i) for i in range(26)]
al=[i for i in al if i not in s]
if al:
    print(''.join(s)+al[0])
    #exit()
for i in range(25,0,-1):
    if s[i-1]<s[i]:
        s=s[:i-1]+[s[-1]]
        print(''.join(s))
        exit()
else:print(-1)

### FIXED CODE ###

s=list(input())
al=[chr(ord('a') + i) for i in range(26)]
al=[i for i in al if i not in s]
if al:
    print(''.join(s)+al[0])
    exit()
for i in range(25,0,-1):
    if s[i-1]<s[i]:
        a=[j for j in s[i-1:] if s[i-1]<j]
        s=s[:i-1]+[sorted(a)[0]]
        print(''.join(s))
        break
        exit()
else:print(-1)
from itertools import combinations

n = int(input())
list = list(map(int, input().split()))
combination = combinations(lst, 3)
count = 0
for i in combination:
  if i[0] != i[1] and i[1] != i[2] and i[0] != i[2]:
    if i[0] + i[1] > i[2] and i[1] + i[2] > i[0] and i[0] + i[2] > i[1]:
      count += 1

print(count)

### FIXED CODE ###

from itertools import combinations

n = int(input())
num_list = list(map(int, input().split()))
combination = combinations(num_list, 3)
count = 0
for i in combination:
  if i[0] != i[1] and i[1] != i[2] and i[0] != i[2]:
    if i[0] + i[1] > i[2] and i[1] + i[2] > i[0] and i[0] + i[2] > i[1]:
      count += 1
print(count)
import math

def main():
    N, M = map(int, input().split())
    s = input().strip()
    t = input().strip()
    if M > N:
        tmp = s
        s = t
        t = tmp
        tmp = N
        N = M
        M = tmp
    # N >= Mと仮定して良い
    gcd_ = math.gcd(N, M)
    len_ = N * (M//gcd_)
    st = [""] * len_
    tmp = len_ // N
    for i in range(N):
        st[i*tmp] = s[i]
    ok = True
    tmp = len_ // M
    for i in range(M):
        if st[i*tmp] == "" or st[i*tmp] == t[i]:
            st[i*tmp] = t[i]
        else:
            ok = False
            break
    # print(st)
    if ok:
        print(len_)
    else:
        print(-1)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

def main():
    N, M = map(int, input().split())
    s = input().strip()
    t = input().strip()
    if M > N:
        tmp = s
        s = t
        t = tmp
        tmp = N
        N = M
        M = tmp
    # N >= Mと仮定して良い
    gcd_ = gcd(N, M)
    len_ = N * (M//gcd_)
    tmp1 = len_ // N
    tmp2 = len_ // M
    # print(tmp1, tmp2)
    ok = True
    for i in range(0, len_, tmp1 * (tmp2//gcd(tmp1, tmp2))):
        # print(i, s[i//tmp1], t[i//tmp2])
        if s[i//tmp1] != t[i//tmp2]:
            ok = False
            break
    if ok:
        print(len_)
    else:
        print(-1)

if __name__ == "__main__":
    main()
#!/usr/bin/env python3
import decimal
from math import sqrt
 
a, b, c = map(decimal, input().split())
if sqrt(a) + sqrt(b) < sqrt(c):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

from decimal import *
 
a, b, c = map(Decimal, input().split())
if a.sqrt() + b.sqrt() < c.sqrt():
    print('Yes')
else:
    print('No')
from sys import stdin, stdout
from collections import defaultdict
n = int(stdin.readline().strip())
word_map = defaultdict(lambda: 0)
maxi = 0
for i in range(n):
  word = stding.readline().strip()
  x = word_map[word]
  word_map[word] = x + 1
  maxi = max(maxi, x+1)
  
word_list = []
for key, value in word_map.items():
  if value == maxi:
    word_list.append(key)
word_list.sort()
for word in word_list:
  stdout.write(word+'\n')
  

### FIXED CODE ###

from sys import stdin, stdout
from collections import defaultdict
n = int(stdin.readline().strip())
word_map = defaultdict(lambda: 0)
maxi = 0
for i in range(n):
  word = stdin.readline().strip()
  x = word_map[word]
  word_map[word] = x + 1
  maxi = max(maxi, x+1)
  
word_list = []
for key, value in word_map.items():
  if value == maxi:
    word_list.append(key)
word_list.sort()
for word in word_list:
  stdout.write(word+'\n')
n = int(input())
XY = [[] for _ in range(n)]
for i in range(n):
    for j in range(int(input())):
        x, y = map(int, input().split())
        XY[i].append([x-1, y])
honest = 0
for bit in range(1<<n):
    flag = True 
    for i in range(n):
        if bit & (1<<i) :
            for a, b in XY[i]:
                if bit & (1<<a) != b:
                    flag = False 
                    break
    if flag:
        honest = max(honest, bin(i)[2:].count('1'))
print(ans)


### FIXED CODE ###

n = int(input())
evidences = [[] for _ in range(n)]
for i in range(n):
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        evidences[i].append((x-1, y))
result = 0
for i in range(1, 2**n):
    consistent = True 
    for j in range(n):
        if (i>>j) & 1 == 0:
            continue 
        for x, y in evidences[j]:
            if (i>>x)&1 != y:
                consistent = False 
                break
        if not consistent:
            break
    if consistent:
        result = max(result, bin(i)[2:].count('1'))
print(result)
import sys

def main():
    _ = int(input())
    A = list(map(int,input().split()))

    M = set()
    lenA = len(A)
    for i in range(len(A))[::-1]:
        if i > lenA/2:
            if A[i] == 1:
                M.add(i+1)
        else:
            bai = [x*(i+1) for x in range(lenA/(i+1))]
            num = len(M&bai) % 2
            if A[i] != num:
                M.add(i+1)
    
    print(len(M))
    if len(M) > 0:
        print(*M)

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys


def main():
    _ = int(input())
    A = list(map(int,input().split()))

    M = set()
    lenA = len(A)
    for i in range(len(A))[::-1]:
        if i > lenA/2:
            if A[i] == 1:
                M.add(i+1)
        else:
            bai = set([x*(i+1) for x in range(1, int(lenA/(i+1))+1)])
            num = len(M&bai) % 2
            if A[i] != num:
                M.add(i+1)
    
    print(len(M))
    if len(M) > 0:
        print(*M)

if __name__=='__main__':
    main()
import numpy as np
from scipy import signal

N = int(input())
H = list(map(int, input().split(" ")))

H = np.array(H)

ans = 'Yes'
min_ind = signal.argrelmin(H)[0]
tmp_ind = 0
for ind in min_ind:
    
    if H[tmp_ind:ind].max() > H[ind]+1:
        ans = 'No'
        break
    tmp_ind = ind

if H[tmp_ind:ind].max() > H[-1]+1:
    ans = 'No'

print(ans)


### FIXED CODE ###


A, B, C = map(int,input().split(" "))

if C+B > A:
    d = (C+B)-A
else:
    d = 0

print(d)
from math import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

n,m = map(int,input().split())
a = list(map(int,input().split()))
b = [i // 2 for i in a]

def f(n):
    res = 0
    while n % 2 == 0:
        res += 1
        n //= 2
    return res

if not all(f(b[0]) == f(b[i]) for i in range(n)):
    print(0)
    exit(0)

cnt = f(b[0])
g = b[0] >> cnt
for i in b:
    g = lcm(g, i >> cnt)

gg = g << cnt
print((m + gg) // (2 * gg))


### FIXED CODE ###

from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

n,m = map(int,input().split())
a = list(map(int,input().split()))
b = [i // 2 for i in a]

def f(n):
    res = 0
    while n % 2 == 0:
        res += 1
        n //= 2
    return res

if not all(f(b[0]) == f(b[i]) for i in range(n)):
    print(0)
    exit(0)

cnt = f(b[0])
g = b[0] >> cnt
for i in b:
    g = lcm(g, i >> cnt)

gg = g << cnt
print((m + gg) // (2 * gg))
#D - Xor Sum 4

import math
n=int(input())
al=list(map(int,input().split()))
a=['{:060b}'.format(x) for x in al]
a=''.join(a)
 
m=math.ceil(math.log(max(1,max(al)),2))
 
ans=0
for i in range(m):
  sum1=a[59-i::60].count('1')
  sum0=n-sum1
  ans+=2**i*sum1*sum0
 
print(ans%(10**9+7))

### FIXED CODE ###

#A-Blackjack
a1, a2, a3 = map(int, input().split())
total = a1 + a2 + a3

if total >=22:
    print('bust')
else:
    print('win')
N, L = map(int, input().split())

if L >= 0:
  N_eat = 1
elif N+L-1 <= 0:
  N_eat = N
else:
  N_eat = 1-L
pie = double(N*N/2 +N*(L-1) - (L + N_eat-1) ) 
print(pie)


### FIXED CODE ###

N, L = map(int, input().split())
 
if L > -1:
  N_eat = 1
elif N+L-1 < 1:
  N_eat = N
else:
  N_eat = 1-L
 
pie = N*(N+1)/2 +N*(L-1) - (L + N_eat-1) 
print(int(pie) )
#include <iostream>
#include <string>

int main(){
  string S;
  cin >> S;
  if (s.find("a") != std::string::npos && s.find("b") != std::string::npos && s.find("c") != std::string::npos){
  cout << "YES" << endl;
  }
  else
  cout << "NO" << endl;
}

### FIXED CODE ###

S =input()
if "a" in S and "b" in S and "c" in S:
	print("Yes")
else:
  	print("No")
input()
s = input()

check = ['A', 'B', 'C']

count = 0
state = 0
for c in list(s):
	if c != check[state]:
      state = 0
      continue
    
    state += 1
    if state >= len(check):
      count += 1
      state = 0

print(count)

### FIXED CODE ###

_ = input()
s = input()

check = ['A', 'B', 'C']

count = 0
state = 0

for i in range(len(s)):
    c = s[i]
    if c != check[state]:
        if c == check[0]:
            state = 1
        else:
            state = 0
        continue
    
    state += 1
    if state == 3:
        count += 1
        state = 0

print(count)
import sys
input = sys.stdin.buffer.readline
 
 
def main():
    K = int(input())
    A, B = map(int, input().split())
	for i in range(A, B + 1):
        if i % K == 0:
            print('OK')
            sys.exit()
    print('NG')
 
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

K = int(input())

A, B = map(int, input().split())


def main(K, A, B):
    for i in range(A, B + 1):
        if i % K == 0:
            print('OK')
            sys.exit()
    print('NG')


if __name__ == '__main__':
    main(K, A, B)
n,a,b = map(int,input().split())

if (b-a)%2 == 0:
    print(int((b-a)/2))
else:
    if a <= n-b:
        t = a + int((b-a)/2)
    else:
        t = n-b + 1 + int((b-a)/2)
print(t)

### FIXED CODE ###

n,a,b = map(int,input().split())
if (b-a)%2 == 0:
    print((b-a)//2)
else:
    print(min(a,n-b+1)+(b-a-1)//2)
import sys
    input = sys.stdin.readline
    n, m = map(int, input().split())
    a = list(input().split() for _ in range(m))
    flag = [0]*2*n
    if m == 0:
        print("{} {}".format(0, 0))
        exit()
    miss = 0
    correct = 0
    for i in range(m):
        if flag[int(a[i][0])] == 0:
            if a[i][1] == "WA":
                miss += 1
            elif a[i][1] == "AC":
                correct += 1
                flag[int(a[i][0])] = 1
    print("{} {}".format(correct, miss))
resolve()

### FIXED CODE ###

def resolve():
    import sys
    input = sys.stdin.readline
    n, m = map(int, input().split())
    if m == 0:
        print("{} {}".format(0, 0))
        exit()

    a = list(input().split() for _ in range(m))
    flag = [[0] * n for i in range(2)]
    miss = 0
    correct = 0
    for i in range(m):
        if flag[0][int(a[i][0]) - 1] == 0:
            if a[i][1] == "WA":
                flag[1][int(a[i][0]) - 1] += 1
            elif a[i][1] == "AC":
                correct += 1
                miss += flag[1][int(a[i][0]) - 1]
                flag[0][int(a[i][0]) - 1] = 1
    print("{} {}".format(correct, miss))
resolve()
import math

# x 以下でc, d 両方で割れない条件を満たす自然数の個数をf(x, c, d) とすると
# 求める値は f(b, c, d) - f(a-1, c, d)
# x 以下でk で割れる自然数の個数を g(x, k)とすれば
# f(x, c, d) = x - (g(x, c) + g(x, d) - g(x, lcm(c,d)))
# よって計算すべきは
# g(b, c) + g(b, d) - g(b, lcm(c,d)) - ( g(a-1, c) + g(a-1, d) - g(a-1, lcm(c,d)))

def lcm(p, q):
    return p * q // math.gcd(p, q)

def g(x, k):
    return x//k

def f(x, c, d):
    return x - (g(x, c) + g(x, d) - g(x, lcm(c,d)))

a,b,c,d = list(map(lambda x:int(x) ,input().split()))

print(f(b, c, d) - f(a-1, c, d))

### FIXED CODE ###

# x 以下でc, d 両方で割れない条件を満たす自然数の個数をf(x, c, d) とすると
# 求める値は f(b, c, d) - f(a-1, c, d)
# x 以下でk で割れる自然数の個数を g(x, k)とすれば
# f(x, c, d) = x - (g(x, c) + g(x, d) - g(x, lcm(c,d)))
# よって計算すべきは
# g(b, c) + g(b, d) - g(b, lcm(c,d)) - ( g(a-1, c) + g(a-1, d) - g(a-1, lcm(c,d)))
 
def gcd (p, q):
    temp = max(p, q)
    q = min(p, q)
    p = temp
    if q == 0:
        return p
    else:
        return gcd(q, p%q)
    
def lcm(p, q):
    return p * q // gcd(p, q)
 
def g(x, k):
    return x//k
 
def f(x, c, d):
    return x - (g(x, c) + g(x, d) - g(x, lcm(c,d)))
 
a,b,c,d = list(map(lambda x:int(x) ,input().split()))
 
print(f(b, c, d) - f(a-1, c, d))
import math
A, B, K = map(int, input().split())
num = int(math.gcd(A,B))
a = [num]
for i in range(1,num):
    if num % i == 0:
        a.append(i)
b = sorted(a)
print(b[len(b)-K])

### FIXED CODE ###

a,b,k=map(int,input().split())
li=[]
for i in range(1,min(a,b)+1):
    if a%i==0 and b%i==0:
        li.append(i)
print(li[len(li)-k])
n=int(input())
Ns=list(map(int, input().split() ) ) 
ans=0
for i in range(n):
  for j in range(i,j):
    for k in range(j,n):
      a , b , c = sorted([Ns[i] , Ns[j] , Ns[k]])
      if a+b>c and a!=b and b!=c:
        ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
Ns=list(map(int, input().split() ) ) 
ans=0
for i in range(n):
  for j in range(i,n):
    for k in range(j,n):
      a , b , c = sorted([Ns[i] , Ns[j] , Ns[k]])
      if a+b>c and a!=b and b!=c:
        ans+=1
print(ans)
while True:
  a,b = map(int, raw_input().split())
  GCD = a if a > b else b
  LCM = a * b
  tmp = GCD
  for i in range(tmp, 0, -1):
    if a % i == 0 and b % i == 0: GCD = i
  tmp = LCM
  for i in range(tmp, 0, -1):
    if i % a == 0 and i % i == 0: LCM = i
  print str(GCD) + " " + str(LCM)

### FIXED CODE ###

def get_gcd(a,b):
	if a > b: a, b = b, a
	if b % a == 0:
		return a
	else:
		return get_gcd(a, b % a)

def get_lcm(a,b,g):
	return a * b / g

while True:
	try:
		a,b = map(int, sorted(raw_input().split()))
		GCD = get_gcd(a,b)
		LCM = get_lcm(a,b,GCD)
		print "{} {}".format(GCD, LCM)
	except EOFError:
		break
N,A,B=map(int,input.split())
print(min(N*A,B))

### FIXED CODE ###

N,A,B=map(int,input().split())
print(min(N*A,B))
import math
 
n=int(input())
k=0
for i in range(math.sqrt(n)):
    while (i+1)**2 < n:
        k+=1
print((k+1)**2)

### FIXED CODE ###

n=int(input())
print((int(n**0.5))**2)