Harryxun/stf_run huggingface dataset:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
input = sys.stdin.readline
INF = float("inf")


def dfs(G, visited, v, cnt):
    visited[v] = True

    for nv in G[v]:
        if visited[nv]:
            continue
        cnt = dfs(G, visited, nv, cnt + 1)
    
    return cnt


# 処理内容
def main():
    N, M = map(int, input().split())

    if M == 0:
        print(1)
        return

    P = set()
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1; b -= 1
        if a > b:
            a, b = b, a
        P.add((a, b))

    G = [[] for _ in range(N)]
    for pair in P:
        a, b = pair
        G[a].append(b)
        G[b].append(a)

    visited = [False] * N
    ans = 1
    for i in range(N):
        if visited[i]:
            continue
        tmp = dfs(G, visited, i, 1)
        ans = max(ans, tmp)
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
INF = float("inf")


def dfs(G, visited, v, cnt):
    visited[v] = True

    for nv in G[v]:
        if visited[nv]:
            continue
        cnt = dfs(G, visited, nv, cnt + 1)
    
    return cnt


# 処理内容
def main():
    N, M = map(int, input().split())

    if M == 0:
        print(1)
        return

    P = set()
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1; b -= 1
        if a > b:
            a, b = b, a
        P.add((a, b))

    G = [[] for _ in range(N)]
    for pair in P:
        a, b = pair
        G[a].append(b)
        G[b].append(a)

    visited = [False] * N
    ans = 1
    for i in range(N):
        if visited[i]:
            continue
        tmp = dfs(G, visited, i, 1)
        ans = max(ans, tmp)
    print(ans)


if __name__ == '__main__':
    main()
#!/usr/bin/env python3                                                                     
import sys

#run by python3                                                                            

class Node:
    def __init__(self, key):
        self.key = key
        self.right = None
        self.left = None

def insert(T, z): #z is node which you would like to insert                                
        #initialization                                                                    
    y = None #parent of x                                                                  
    x = T

        #search                                                                            
    while(x!=None):
        y = x
        if(z.key < x.key):
            x = x.left
        else:
            x = x.right

        #insert                                                                            
    if(y==None):
        T = z
    elif(z.key < y.key):
        y.left = z
    else:
        y.right = z

    return T


def inorder_walk(node):
    if node.left:
        inorder_walk(node.left)
    print ('', node.key, end='')
    if node.right:
	inorder_walk(node.right)


def preorder_walk(node):
    print ('', node.key,end='')
    if node.left:
        preorder_walk(node.left)
    if node.right:
	preorder_walk(node.right)

if __name__ == '__main__':

    T = None
    num = int(sys.stdin.readline())

    for _ in range(num):
        cmd = sys.stdin.readline()
        if(cmd.startswith('i')):
            n = Node(int(cmd[7:]))
            T = insert(T, n)
        else:
            inorder_walk(T)
            print()
            preorder_walk(T)
            print()

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
 
 
class Node(object):
    def __init__(self, key=None):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None
 
 
def tree_insert(top, z):
    y = None
    x = top
    while isinstance(x, Node):
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y is None:
        top = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z
    return top
 
 
def inorder_walk(node):
    if node.left:
        inorder_walk(node.left)
    print('', node.key, end='')
    if node.right:
        inorder_walk(node.right)
 
 
def preorder_walk(node):
    print('', node.key, end='')
    if node.left:
        preorder_walk(node.left)
    if node.right:
        preorder_walk(node.right)
 
 
n = int(stdin.readline())
 
top = None
for _ in range(n):
    cmd = stdin.readline()
    if cmd.startswith('i'):
        key = int(cmd[7:])
        #assert -2000000000 <= key <= 2000000000
        top = tree_insert(top, Node(key))
    else:
        inorder_walk(top)
        print()
        preorder_walk(top)
        print()
a = input()
b = input()

if a == 'H':
    if b == 'H':
        print('H')
    elif b == 'D':
        print('D')

elif a == 'D':
    if b == 'H':
        print('D')
    elif b == 'D':
        print('H')

### FIXED CODE ###

a, b = input().split()

if a == 'H':
    if b == 'H':
        print('H')
    elif b == 'D':
        print('D')

elif a == 'D':
    if b == 'H':
        print('D')
    elif b == 'D':
        print('H')
INPUT = list(map(int, input().split()))
processes = [input().split() for _ in range(INPUT[0])]
head, tail, n, quantum = 0, len(processes), INPUT[0], INPUT[1]


def enqueue(x):
    global processes, tail
    processes.append(0)
    processes[tail] = x
    tail += 1


def dequeue():
    global head
    head += 1


for i in range(n):
    int(processes[i][1])

time, count = 0, 0
while count < n:
    y = processes[head][1] - quantum
    if y < 0:
        print(str(processes[head][0]) + " " + str(time + processes[head][1]))
        dequeue()
        time += y
        count += 1
    else:
        processes[head][1] -= quantum
        enqueue(processes[head])
        dequeue()

    time += quantum



### FIXED CODE ###

def parse(l):
    name, time = l.split()
    a = [name, int(time)]
    return a


n, quantum = map(int, input().split())
queue = []
for i in range(n):
    queue.append(parse(input()))
head = 0


def enqueue(x):
    global queue
    queue.append(x)


def dequeue():
    global head
    head += 1


total_time, count = 0, 0
while count < n:
    y = queue[head][1] - quantum
    if y <= 0:
        print(str(queue[head][0]) + " " + str(total_time + queue[head][1]))
        dequeue()
        total_time += y
        count += 1
    else:
        queue[head][1] -= quantum
        enqueue(queue[head])
        dequeue()

    total_time += quantum
x = raw_input()
cube = x * x * x
print cube

### FIXED CODE ###

x = input()
cube = x * x * x
print cube
import math

if __name__ == "__main__":
    x,y = [int(x) for x in input().split()]
    print(x*y // math.gcd(x, y))

### FIXED CODE ###

if __name__ == "__main__":
    x,y = [int(x) for x in input().split()]
    if x < y:
        tmp = x
        x = y
        y = tmp
    a = x * y
    
    r = x % y;
    while(r!=0):
        x = y
        y = r
        r = x % y;
    
    print(int(a/y))
n,k = list(map(int,input().strip().split()))
temp = []
ans = int(0)
for i in range(k+1):
    d = int(input())
    li = list(map(int,input().split()))
    for j in range(d):
        temp += str(li[j])
for m in range(n+1):
    b  = str(m + 1)
    a = temp.count(b)
    if a == 0:
        ans += 1
print(ans)


### FIXED CODE ###

n,k = map(int,input().split())
person = [0]*n
for i in range(k):
    d = int(input())
    A = list(map(int,input().split()))
    for j in range(len(A)):
        person[A[j]-1] = 1
print(person.count(0))
# -*- coding: utf-8 -*-


def main(n, s):
    count = 0
    max_values = []
    for c in s:
        if c == 'I':
            count += 1
            max_values.append(count)
        else:
            count -= 
    max_values = max_values if max_values else [0]
    return max(max_values) if 0 < max(max_values) else 0


if __name__ == '__main__':
    n = int(input())
    s = input()
    answer = main(n, s)
    print(answer)

### FIXED CODE ###

# -*- coding: utf-8 -*-


def main(n, s):
    count = 0
    max_values = []
    for c in s:
        if c == 'I':
            count += 1
            max_values.append(count)
        else:
            count -= 1
    max_values = max_values if max_values else [0]
    return max(max_values) if 0 < max(max_values) else 0


if __name__ == '__main__':
    n = int(input())
    s = input()
    answer = main(n, s)
    print(answer)
N = int(input())
S = input()
 
res = 0
tmp = ""

for i in range(N-1,-1,-1):
    if S[i] == "#":
        continue
    dot = S[:i+1].count(".")
    sha = S[:i+1].count("#")
    break
print(min(dot, sha))

### FIXED CODE ###

N = int(input())
S = input()

res = dot = S.count(".")
sha = 0
for i in range(N):
    if S[i] == "#":
        sha += 1
    else:
        dot -= 1
    tmp = sha + dot
    res = min(res, tmp)

print(res)
N, M = [int(elm) for elm in input().split(" ")]
bridges = [[int(elm) for elm in input().split(" ")] for _ in range(M)]

#graph = {}
#for node in range(1, N+1):
#    graph[node] = [node]
#    #graph_mem[node] = []

#graph_n_mem = [0] + [1 for i in range(N)]
graph_n_mem = [0] + [1] * N
n_all_pairs = N * (N-1) // 2

parent = [-1] * (N+1)

#def get_parent(child_node, tmp_nodes=[]):
def get_parent(child_node):
    parent_node = parent[child_node]

    if parent_node != -1:
        #tmp_nodes.append(child_node)
        #out = get_parent(parent_node, tmp_nodes)
        out = get_parent(parent_node)
    else:
        out = child_node
        #if len(tmp_nodes) >= 1:
        #    tmp_nodes = tmp_nodes[:-1]
        #    for tmp_node in tmp_nodes:
        #        parent[tmp_node] = out
    return out


outs = []
out = n_all_pairs
for A, B in reversed(bridges):
    #A = graph[A][0]
    #B = graph[B][0]

    A = get_parent(A)
    B = get_parent(B)

    if A != B:
        n_b = graph_n_mem[B]
        n_a = graph_n_mem[A]
        graph_n_mem[A] += graph_n_mem[B]
        graph_n_mem[B] = 0

        parent[B] = A

        #old_graph_B = graph[B]
        #graph[A] += graph[B]
        #for node in old_graph_B:
        #    graph[node] = graph[A]
        
        out -= n_a * n_b

    outs.append(out)

outs = outs[::-1]
outs = outs[1:] + [n_all_pairs]
for out in outs:
    print(out)


### FIXED CODE ###

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

n = B // A
out = min(n, C)
print(out)
n = input()
for i in sorted(map(int, raw_input().split()))
 print i,

### FIXED CODE ###

n = input()
for i in sorted(map(int, raw_input().split())):
 print i ,
n,k=map(int,input().split())
d=list(map(int,input().split()))
l=[0,1,2,3,4,5,6,7,8,9]
for i in range(k):
  l.remove(d[i])
L=[]
for j1 in range(len(l)):
  for j2 in range(len(l)):
    for j3 in range(len(l)):
      for j4 in range(len(l)):
        L.append(l[j1]*1000+l[j2]*100+l[j3]*10+l[j4])
for k in range(len(L)):
  if L[k]>=n:
    x=L[k]
    break
print(x)

### FIXED CODE ###

n,k=map(int,input().split())
d=list(map(int,input().split()))
l=[0,1,2,3,4,5,6,7,8,9]
for i in range(k):
  l.remove(d[i])
L=[]
for j1 in range(len(l)):
  for j2 in range(len(l)):
    for j3 in range(len(l)):
      for j4 in range(len(l)):
        for j5 in range(len(l)):
          L.append(l[j1]*10000+l[j2]*1000+l[j3]*100+l[j4]*10+l[j5])
for j1 in range(len(l)):
  for j2 in range(len(l)):
    for j3 in range(len(l)):
      for j4 in range(len(l)):
        L.append(l[j1]*1000+l[j2]*100+l[j3]*10+l[j4])
for j1 in range(len(l)):
  for j2 in range(len(l)):
    for j3 in range(len(l)):
      L.append(l[j1]*100+l[j2]*10+l[j3])
for j1 in range(len(l)):
  for j2 in range(len(l)):
    L.append(l[j1]*10+l[j2])
for j1 in range(len(l)):
  L.append(l[j1])
L.sort()
for k in range(len(L)):
  if L[k]>=n:
    x=L[k]
    break
print(x)
n = int(input())
visited = [0]*n
def dfs(edge, dist, k):
    visited[k]=1
    for i in edge[k]:
        if visited[i[0]]==0:
            dist[i[0]]=i[1]+dist[k]
            dfs(edge, dist, i[0])


    return dist
def main():
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        a,b,c=map(int, input().split())
        edge[a-1].append([b-1,c])
        edge[b-1].append([a-1,c])

    q,k=map(int, input().split())
    #頂点kから各頂点への距離を最初に求めておくdist[i]:頂点kから頂点iまでの距離　 dist[k]=0
    dist = [0]*n
    visited[k-1]=1
    dist = dfs(edge, dist, k-1)

    res = [0]*q
    for i in range(q):
        x,y=map(int, input().split())
        res[i]=dist[x-1]+dist[y-1]


    for i in range(q):
        print(res[i])
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n = int(input())
visited = [0]*n
def dfs(edge, dist, k):
    visited[k]=1
    for i in edge[k]:
        if visited[i[0]]==0:
            dist[i[0]]=i[1]+dist[k]
            dfs(edge, dist, i[0])


    return dist
def main():
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        a,b,c=map(int, input().split())
        edge[a-1].append([b-1,c])
        edge[b-1].append([a-1,c])

    q,k=map(int, input().split())
    #頂点kから各頂点への距離を最初に求めておくdist[i]:頂点kから頂点iまでの距離　 dist[k]=0
    dist = [0]*n
    visited[k-1]=1
    dist = dfs(edge, dist, k-1)

    res = [0]*q
    for i in range(q):
        x,y=map(int, input().split())
        res[i]=dist[x-1]+dist[y-1]


    for i in range(q):
        print(res[i])
if __name__ == '__main__':
    main()
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
c_dict = Counter(A)
B = []
C = []

for k, v in c_dict.items():
    if v >= 4:
        B.append(k)
    elif v >= 2:
        C.append(k)
B.sort(reverse=True)
C.sort(reverse=True)
print(B[0])
print(C[0])

if len(B) < 1 and len(C) < 2:
    print(0)
elif len(B) < 1 and len(C) >= 2:
    print((C[0]*C[1]))
elif len(B) >= 1 and len(C) == 1:
    print(max(B[0] ** 2), (B[0] * C[0]))
elif len(B) >= 1 and len(C) >= 2:
    C = (B[0] ** 2)
    D = (B[0] * C[0])
    E = (C[0] * C[1])
    print(max(C, D, E))


### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int, input().split()))
c_dict = Counter(A)
B = []
C = []

for k, v in c_dict.items():
    if v >= 4:
        B.append(k)
    elif v >= 2:
        C.append(k)
B.sort(reverse=True)
C.sort(reverse=True)

if len(B) < 1 and len(C) < 2:
    print(0)
elif len(B) < 1 and len(C) >= 2:
    F = C[1] * C[0]
    print(F)
elif len(B) >= 1 and len(C) == 1:
    D = B[0] ** 2
    E = C[0] * B[0]
    print(max(D, E))
elif len(B) >= 1 and len(C) >= 2:
    D = B[0] ** 2
    E = C[0] * B[0]
    F = C[1] * C[0]
    print(max(D, E, F))
def li():
    return [int(x) for x in input().split()]


INF = 10 ** 60

N, W = li()
L = [li() for i in range(N)]
V = 1000
# W <= 10**9 なので、
# dp[i][w]: i番目の選択で重さwだった時の価値の最大値、は計算量厳しい
# dp[i][v]: i番目の選択で価値vだった時の重さの最小値、で考えて重さの最小値がW以下のものから最大価値を算出する

dp = [[INF] * V for _ in range(N)]

# 初期条件
# 選ばない
dp[0][0] = 0
# 選ぶ
w0, v0 = L[0]
dp[0][v0] = w0

for i in range(1, N):
    for v in range(V):
        cw, cv = L[i]
        # 選ばない
        dp[i][v] = min(dp[i][v], dp[i-1][v])
        # 選ぶ
        if v + cv >= V:
            continue
        dp[i][v+cv] = min(dp[i][v+cv], dp[i-1][v] + cw)

# 重さの最小値がW以下で達成できるvの最大値
v_max = 0
for v in range(V):
    if dp[N-1][v] <= W:
        v_max = v
print(v_max)

### FIXED CODE ###

def li():
    return [int(x) for x in input().split()]


INF = 10 ** 60

N, W = li()
L = [li() for i in range(N)]
V = 10 ** 5
# W <= 10**9 なので、
# dp[i][w]: i番目の選択で重さwだった時の価値の最大値、は計算量厳しい
# dp[i][v]: i番目の選択で価値vだった時の重さの最小値、で考えて重さの最小値がW以下のものから最大価値を算出する

dp = [[INF] * (V+1) for _ in range(N)]

# 初期条件
# 選ばない
dp[0][0] = 0
# 選ぶ
w0, v0 = L[0]
dp[0][v0] = w0

for i in range(1, N):
    for v in range(V+1):
        cw, cv = L[i]
        # 選ばない
        dp[i][v] = min(dp[i][v], dp[i-1][v])
        # 選ぶ
        if v + cv > V:
            continue
        dp[i][v+cv] = min(dp[i][v+cv], dp[i-1][v] + cw)

# 重さの最小値がW以下で達成できるvの最大値
v_max = 0
for v in range(V+1):
    if dp[N-1][v] <= W:
        v_max = v
print(v_max)
s = input()
t = input()
for i in range(3):
	if s[i] == t[i]:
		ans += 1
		
print(ans)

### FIXED CODE ###

s = input()
t = input()
ans = 0
for i in range(3):
	if s[i] == t[i]:
		ans += 1
		
print(ans)
def max_score(edge,N):
    inf =float("inf")
    w = [-inf for i in range(int(N)+1)]
    w[1] = 0;
    while True:
        update = False
        negative = False
        for e in edge:
            if e[0] > e[1] and e[2]>0:
                negative = True
                update = True
                break

            elif w[e[0]] != -inf and w[e[1]] < w[e[0]]+e[2] and e[0] < e[1]:
                w[e[1]] = w[e[0]]+e[2]
                update = True

        if not update:
            break

    if not negative:
        return w[int(N)]
    else:
        return "inf"


N, M = raw_input().split()
edge = []
for i in range(int(M)):
    edge.append(map(int,raw_input().split()))

print max_score(edge,int(N))

### FIXED CODE ###

#coding:utf-8

input_lines = raw_input().split()
n = map(int,input_lines)

if n[0] <= n[2] and n[2]<=n[1]:
    print "Yes"
else:
    print "No"
n=int(input())
l=list(map(int,input().split()))

if n=<2:
  print(1)
  exit()
  
cnt=0

if l[0]>l[1]:
  ans="low"
elif l[0]<l[1]:
  ans="high"
else:
  ans="even"
  
for i in range(2,n):
  if l[i-1]>l[i] and (ans=="low" or ans=="even"):
    ans="low"
  elif l[i-1]<l[i] and (ans=="high" or ans=="even"):
    ans="high"
  elif l[i-1]==l[i]:
    continue
  else:
    cnt+=1
    ans="even"
    
print(cnt+1)


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))

if n<=2:
  print(1)
  exit()
  
cnt=0

if l[0]>l[1]:
  ans="low"
elif l[0]<l[1]:
  ans="high"
else:
  ans="even"
  
for i in range(2,n):
  if l[i-1]>l[i] and (ans=="low" or ans=="even"):
    ans="low"
  elif l[i-1]<l[i] and (ans=="high" or ans=="even"):
    ans="high"
  elif l[i-1]==l[i]:
    continue
  else:
    cnt+=1
    ans="even"
    
print(cnt+1)
tmp = [row[i] for i, row in enumerate(input())]
print(''.join(tmp))

### FIXED CODE ###

tmp = [input()[i] for i in range(3)]
print(''.join(tmp))
from functools import reduce
import fractions

n=int(input())
A=list(map(int,input().split()))

def gcd(data):
    if len(data) == 1:
        return data[0]
    return reduce(lambda x, y: fractions.gcd(x, y), data)

gcds = []

for i in range(1, n-2):
    gcds.append(gcd(A[0:i] + A[i+1:n]))

print(max(gcds))


### FIXED CODE ###

# coding: utf-8

n=int(input())
A=list(map(int,input().split()))

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

L = [0]
R = [0]

for i in range(n):
    L.append(gcd(L[i], A[i]))
    R.append(gcd(R[i], A[n-1-i]))
R.reverse()

result = []

for i in range(n):
    result.append(gcd(L[i], R[i+1])) 

print(max(result))
import itertools
import sys
import numpy as np
from collections import defaultdict
import bisect

sys.setrecursionlimit(10 ** 9)
M = 1000000007
N = int(input())
left = list(map(int, input().split()))

indices = defaultdict(list)
for i, x in enumerate(left):
    indices[x].append(i)


def dp(t, n1, n2, n3):
    cached = t[n1, n2, n3]
    if cached >= 0:
        return cached
    remaining = n1 + n2 + n3
    assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    res = 0
    if last_cnt == n1:
        res += dp(t, n1 - 1, n2, n3)
        res %= M
    if last_cnt == n2:
        res += dp(t, n1, n2 - 1, n3)
        res %= M
    if last_cnt == n3:
        res += dp(t, n1, n2, n3 - 1)
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[n1, n2, n3] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = len(indices[i])
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    t = -np.ones(shape=(h[0] + 1, h[1] + 1, h[2] + 1), dtype=np.int32)
    t[0, 0, 0] = 1
    res = dp(t, h[0], h[1], h[2])
    return res * len(set(itertools.permutations(h))) % M


print(solve())


### FIXED CODE ###

import itertools
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 9)
M = 1000000007
N = int(sys.stdin.readline())
left = list(map(int, sys.stdin.read().split()))
counter = Counter(left)


def dp(t, ns):
    cached = t.get(ns)
    if cached is not None:
        return cached
    remaining = sum(ns)
    assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    n1, n2, n3 = ns
    res = 0
    if last_cnt == n1:
        res += dp(t, tuple(sorted([n1 - 1, n2, n3])))
        res %= M
    if last_cnt == n2:
        res += dp(t, tuple(sorted([n1, n2 - 1, n3])))
        res %= M
    if last_cnt == n3:
        res += dp(t, tuple(sorted([n1, n2, n3 - 1])))
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[ns] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = counter[i]
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    if sum(h) != N:
        return 0
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, tuple(sorted(h)))
    return (res * len(set(itertools.permutations(h)))) % M


print(solve())
import collections
import numpy as np
import sys
sys.setrecursionlimit(10**8)
#N,K=map(int,input().split())
#N=int(input())
S=list(input())
T=list(input())
T.pop()

if "".join(S)=="".join(T):
    print("Yes")
else:
    print("No")

# h=np.array(list(map(int,input().split())))
# ans=0
# def sol(l,m,k):
#     global ans
#     if m==0:
#         return ans
#     elif m>0:
#         for i in range(N-m+1):
#             if not 0 in l[i:i+m]:
#                 ans+=np.amin(l[i:i+m])
#                 l[i:i+m]=l[i:i+m]-min(l[i:i+m])
#                 print(l)
#         sol(l,m-1,ans)
#     # else:
#     #     ans+=np.count_nonzero(h)
#     #     sol(l, m - 1, ans)
# n=0
# sol(h,N,ans)
# print(ans)

### FIXED CODE ###


#N,K=map(int,input().split())
#N=int(input())
S=list(input())
T=list(input())
T.pop()

if "".join(S)=="".join(T):
    print("Yes")
else:
    print("No")
L,R=map(int,input().split())
M=2019;l,r=L%M,R%M
print([min(i*j%M for i in range(l,r) for j in range(i+1,r+1)),0][R//M-L//M>0])

### FIXED CODE ###

mod = 2019
l, r = map(int, input().split())

if r//mod - l//mod > 0:
  print(0)
else:
  l %= mod
  r %= mod
  ans = mod - 1
  for i in range(l+1, r+1):
    for j in range(l, i):
      ans = min(i*j%mod, ans)
  print(ans)
b = input()

if b=='A':
    print('T')

elif b=='T':
    print('A')

elif b=='C':
    print('G')

else:
    print('C')


### FIXED CODE ###

b = input()

if b=='A':
    print('T')

elif b=='T':
    print('A')

elif b=='C':
    print('G')

else:
    print('C')