Harryxun/stf_run huggingface dataset:
from collections import deque

n, m = list(map(int, input().split()))
AB = [[int(x) for x in input().split()] for _ in range(m)]

# representation matrix
repn = [[] for j in range(n + 1)]
for a, b in AB:
    repn[a].append(b)
    repn[b].append(a)


# Minimum Spanning Tree
tree = [[] for i in range(n + 1)]
visited = [False] * (n + 1)
visited[1] = True
q = deque([1])

while q:
    u = q.popleft()
    for v in repn[u]:
        if visited[v]:
            continue
        visited[v] = True
        tree[u].append(v)
        tree[v].append(u)
        q.append(v)


# define directions of the edges other than that of MST
degree = [0] * (n + 1)
ans = []

for a, b in AB:
    if b in tree[a]:
        continue
    ans.append('{} {}'.format(a, b))
    degree[a] += 1


# defining orientations
def dfs(u = 1, parent = None):
    for v in tree[u]:
        if v == parent:
            continue
        dfs(v, u)
        if degree[v] % 2 == 0:
            ans.append('{} {}'.format(u, v))
            degree[u] += 1
        else:
            ans.append('{} {}'.format(v, u))
            degree[v] += 1

dfs()


# output answer
if degree[1] % 2 == 1:
    print(-1)
else:
    print('\n'.join(ans))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from collections import deque

n, m = map(int, input().split())

if m % 2 == 1:
    print(-1)
    exit()



AB = [[int(x) for x in input().split()] for _ in range(m)]

# representation matrix
repn = [[] for j in range(n + 1)]
for a, b in AB:
    repn[a].append(b)
    repn[b].append(a)


# Minimum Spanning Tree
tree = [set() for i in range(n + 1)]
visited = [False] * (n + 1)
visited[1] = True
q = deque([1])

while q:
    u = q.popleft()
    for v in repn[u]:
        if visited[v]:
            continue
        visited[v] = True
        tree[u].add(v)
        tree[v].add(u)
        q.append(v)


# define directions of the edges other than that of MST
degree = [0] * (n + 1)
ans = []

for a, b in AB:
    if b in tree[a]:
        continue
    ans.append('{} {}'.format(a, b))
    degree[a] += 1


# defining orientations
def dfs(u = 1, parent = None):
    for v in tree[u]:
        if v == parent:
            continue
        dfs(v, u)
        if degree[v] % 2 == 0:
            ans.append('{} {}'.format(u, v))
            degree[u] += 1
        else:
            ans.append('{} {}'.format(v, u))
            degree[v] += 1

dfs()

print('\n'.join(ans))
import sys

ary=[]
ans=[]
def solve(a,b,c,d,e,f):
    x=(c-b*f/e)/(a-b*d/e)
    y=(c-a*f/d)/(b-a*e/d)
    return [x,y]

for i in sys.stdin:
    ary.append(list(map(int,i.split())))
    ans.append(solve(*ary[-1]))
    
for i in range(len(ans)):
    print('{0:.3f} {1:.3f}' .format(*ans[i]))

### FIXED CODE ###

import sys

ary=[]
ans=[]
def solve(a,b,c,d,e,f):
    if c*e-b*f==0:
        x=0
    else:
        x=(c*e-b*f)/(a*e-b*d)
    if c*d-a*f==0:
        y=0
    else:
        y=(c*d-a*f)/(b*d-a*e)
    return [x,y]

for i in sys.stdin:
    ary.append(list(map(int,i.split())))
    ans.append(solve(*ary[-1]))

for i in range(len(ans)):
    print('{0:.3f} {1:.3f}'.format(round(ans[i][0],3),round(ans[i][1],3)))
n = int(input())
a = map(int,input().split())
for i in range (n):
  if a[i] %2 == 0:
    if a[i] %3 != 0 or a[i] %5 != 0:
      print("DENIED")
      exit()
print("APPROVED")

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    if a[i] % 2 == 0:
        if a[i] % 3 != 0:
            if a[i] % 5 != 0:
                print("DENIED")
                exit()
        if a[i] % 5 != 0:
            if a[i] % 3 != 0:
                print("DENIED")
                exit()
print("APPROVED")
A,B = map(int,input().split())

if A >= 13:
    print(B)

elif A >= 6 and A <= 12:
    print(B/2)

elif A <= 5
    print(0)


### FIXED CODE ###

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


if A >= 13:
    print(B)

elif A >= 6 and A <= 12:
    print(int(B/2))

else:
    print(0)
s=str(input())
t=str(input())
n=len(t)
m=len(s)
ans=0
a=[]
if t in s:
  print(0)
else:
  for i in range(m-n-1):
    for j in range(n):
      if s[i+j]==t[j]:
        ans+=1
    a.append(ans)
  print(n-max(a))

### FIXED CODE ###

s=str(input())
t=str(input())
n=len(t)
m=len(s)
a=[]
if t in s:
  print(0)
else:
  for i in range(m-n+1): #ずらす文字数
    ans=0
    for j in range(n):
      if s[i+j]!=t[j]:
        ans+=1
    a.append(ans)
  print(min(a))
n = int(input())
nums = list(map(int, input().split()))
if 0 in nums:
    print(0)
    quit()
mul = 1
for i in nums:
    mul *= i
    if mul > 1000000000000000000:
        print(-1)
        quit()
print(mul)

### FIXED CODE ###

a,b = [int(num) for num in input().split()]
print(a*b)
n=int(input())

# 最上公倍数を考える
import math
from functools import reduce
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

num_list=[]
for _ in range(n):
    num_list.append(int(input()))
print(lcm(*num_list))

### FIXED CODE ###

n=int(input())

# 最上公倍数を考える
from fractions import gcd
from functools import reduce

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

num_list=[]
for _ in range(n):
    num_list.append(int(input()))
print(lcm(*num_list))
N, P = map(int, input().split())
S = input()
ans = 0
rui = [0] * (N + 1)
if 10 % P == 0:
    for i in range(len(S)):
        if int(S[i]) % P == 0:
            ans += i + 1
    print(ans)
    exit()

t = 1
for i in reversed(range(N)):
    tmp = int(S[i]) * t % P
    rui[i] = (rui[i + 1] + tmp) % P
    t *= 10
    t %= P

cnt = [0] * (N + 1)
for i in reversed(range(N + 1)):
    ans += cnt[rui[i]]
    cnt[rui[i]] += 1
print(ans)

### FIXED CODE ###

N, P = map(int, input().split())
S = input()
ans = 0
rui = [0] * (N + 1)
if 10 % P == 0:
    for i in range(len(S)):
        if int(S[i]) % P == 0:
            ans += i + 1
    print(ans)
    exit()

t = 1
for i in reversed(range(N)):
    tmp = int(S[i]) * t % P
    rui[i] = (rui[i + 1] + tmp) % P
    t *= 10
    t %= P

cnt = [0] * P
for i in reversed(range(N + 1)):
    ans += cnt[rui[i]]
    cnt[rui[i]] += 1
print(ans)
S_raw = input()
T_raw = input()

S = list(S_raw)
T = list(T_raw)

i = 0
j = 0

j_list = []
S_list = []

lt = len(T)
ls = len(S)

while True:
	if j == ls or i == lt:
		if not i == lt:
			print("UNRESTORABLE")
			exit(0)
		elif j != ls:
			j_list.append(j)
			i = 0
			j = j - lt + 2
		else:
			j_list.append(j)
			break

	if T[i] == S[j]:
		i += 1
		j += 1
	elif S[j] == '?':
		i += 1
		j += 1
	else:
		i = 0
		j += 1


for j in j_list:
	for i,c in zip(range(j-lt,j),T):
		S[i] = c

	S_tmp = ''

	for i in range(ls):
		if S[i] == '?':
			S_tmp += 'a'
		else:
			S_tmp += str(S[i])

	S_list.append(S_tmp)

S_list.sort()
print(S_list[0])

### FIXED CODE ###

S_raw = input()
T_raw = input()

S = list(S_raw)
T = list(T_raw)

i = 0
j = 0

j_list = []
S_list = []

lt = len(T)
ls = len(S)

while True:
	if (j >= ls) or (i >= lt):
		if i < lt  :
			if j_list == []:
				print("UNRESTORABLE")
				exit(0)
			else:
				break
		elif j < ls:
			j_list.append(j)
			i = 0
			j = j - lt + 1

		else:
			j_list.append(j)
			break

	if T[i] == S[j]:
		i += 1
		j += 1
	elif S[j] == '?':
		i += 1
		j += 1
	else:
		j -= (i - 1)
		i = 0

for k in j_list:
	M = S[:]
	for i,c in zip(range(k-lt,k),T):
		M[i] = c

	S_tmp = ''

	for i in range(ls):
		if M[i] == '?':
			S_tmp += 'a'
		else:
			S_tmp += M[i]

	S_list.append(S_tmp)

S_list.sort()
print(S_list[0])
A, B = map(int, input(). split())
answer = None
flag = False
for i in range(1009):
  
  if (A == i*0.08//1) and (B == i*0.1//1):
    Answer = i
    print(Answer)
    flag = True
   
    if flag:
        break
if (answer = None):
  print(-1)
    


### FIXED CODE ###

A, B = map(int, input(). split())
answer = None
flag = False
for i in range(1, 1009):
  
  if (A == (i*0.08)//1) and (B == (i*0.1)//1):
    answer = i
    print(answer)
    flag = True
   
    if flag:
        break
if answer is None:
  answer = -1
  print(answer)
import itertools
import math


def lcm(left,right):
    return (int(left) * int(right)) / int(math.gcd(left,right))


N = int(input().strip())
Ts = []
for i in range(N):
    Ts.append(int(input()))

res = int(lcm(Ts[0], Ts[1]))
for T in Ts[2:]:
    res = int(lcm(res, T))

print(int(res))




### FIXED CODE ###

import itertools
import math


def gcd(a,b):
    while b:
        a, b = b, a % b
    return a


def lcm(left, right):
    return (left * right) // gcd(left, right)


N = int(input().strip())
Ts = []
for i in range(N):
    Ts.append(int(input().strip()))

res = 0
if len(Ts) == 0:
    res = 0
elif len(Ts) == 1:
    res = Ts[0]
else:
    res = int(lcm(Ts[0], Ts[1]))
    for T in Ts[2:]:
        res = int(lcm(res, T))

print(str(int(res)))
line = [int(i) for i in input().split(' ')]
set_line = set(line)
A = [int(i) for i in input().split(' ')]
B = [int(i) for i in input().split(' ')]
C = []
for i in range(line[2]):
  C.append([int(i) for i in input().split(' ')])
  
if line.count(1) == 3:
  print(A[0] + B[0] - C[2])
else:
  min_price = min(A) + min(B)
  for i in range(len(C)):
    price = A[C[i][0]] + B[C[i][1]] - C[i][2]
    if min_price > price:
      min_price = price
  print(min_price)
      
      

### FIXED CODE ###

line = [int(i) for i in input().split(' ')]
set_line = set(line)
A = [int(i) for i in input().split(' ')]
B = [int(i) for i in input().split(' ')]
C = []
for i in range(line[2]):
  C.append([int(i) for i in input().split(' ')])
  
if line.count(1) == 3:
  print(A[0] + B[0] - C[2])
else:
  min_price = min(A) + min(B)
  for i in range(len(C)):
    price = A[(C[i][0] - 1)] + B[(C[i][1] - 1)] - C[i][2]
    if min_price > price:
      min_price = price
  print(min_price)
def lcs(x, y, pre_lcs, pre_lcs_len):
    rec = []
    idx = []
    for c in y:
        s = 0
        for i, k in enumerate(idx):
            t = x.find(c, s) + 1
            if t < 1:
                break
            if t < k:
                idx[i] = t
            s = k
        else:
            t = x.find(c, s) + 1
            if t:
                idx.append(t)
        rec.append(idx.copy())
    
    lcs_len = len(idx)
    if lcs_len > pre_lcs_len:
        lcs = ''
        pos = len(idx) - 1
        for line, yc in zip(rec[::-1], y[::-1]):
            i = line[pos] - 1
            xc = x[i]
            if xc == yc:
                lcs += xc
                if pos == 0:
                    return (lcs[::-1], lcs_len)
                pos -= 1
    else:
        return (pre_lcs, pre_lcs_len)

def solve():
    import sys
    file_input = sys.stdin
    ans_out = []
    for s in file_input:
        s = s.rstrip()
        if s[0] == '#':
            break
        s_len = len(s)
        sep = s_len // 2
        ans, ans_len = lcs(s[:sep], s[sep:], '', 0)
        while sep > ans_len:
            ans, ans_len = lcs(s[:-sep], s[-sep:], ans, ans_len)
            sep -= 1
            ans, ans_len = lcs(s[:sep], s[sep:], ans, ans_len)
        ans_out.append(ans)
    print(*ans_out, sep='\n')

solve()


### FIXED CODE ###

def lcs(x, y, pre_lcs, pre_lcs_len):
    pm = dict((zip('ABCDEFGHIJKLMNOPQRSTUVWXYZ', [0] * 26)))
    for c in pm:
        for i, xc in enumerate(x):
            if c == xc:
                pm[c] |= (1 << i)
    
    V = (1 << len(x)) - 1
    rec = []
    
    for yc in y:
        V = ((V + (V & pm[yc])) | (V & ~pm[yc]))
        rec.append(bin(V)[-len(x):])
    
    lcs_len = bin(V)[-len(x):].count('0')
    
    if lcs_len > pre_lcs_len:
        rx = x[::-1]
        lcs = ''
        idx = 0
        for v, yc in zip(rec[::-1], reversed(y)):
            idx = v.find('0', idx)
            if yc == rx[idx]:
                lcs += yc
                if len(lcs) == lcs_len:
                    return (lcs[::-1], lcs_len)
                idx += 1
    else:
        return (pre_lcs, pre_lcs_len)

from sys import stdin

def solve():
    file_input = stdin
    ans_out = []
    for s in file_input:
        s = s.rstrip()
        if s[0] == '#':
            break
        s_len = len(s)
        sep = s_len // 2
        ans, ans_len = lcs(s[:sep], s[sep:], '', 0)
        while sep > ans_len:
            ans, ans_len = lcs(s[:-sep], s[-sep:], ans, ans_len)
            sep -= 1
            ans, ans_len = lcs(s[:sep], s[sep:], ans, ans_len)
        ans_out.append(ans)
    print(*ans_out, sep='\n')

solve()
X,N = map(int, input().split())
P = map(list,int(input.split()))
direction = -1
i = 0
while True:
    dist = i * direction

    if not (dist + X in P):
        print(dist + X)
        break
    i += 1
    if direction < 0: direction = 1
    else : direction = -1

### FIXED CODE ###

X,N = map(int, input().split())
if N > 0: 
    P = list(map(int,input().split()))
    direction = -1
    i = 1
    if not X in P:
        print(X)
    else:
        while True:
            dist = i * direction
            val = dist+X
            if not (val in P):
                print(val)
                break
            if direction < 0: direction = 1
            else : 
                direction = -1
                i+=1
else: 
    print(X)
# coding: utf-8
# Your code here!

N, M = map(int,input().split())
hen = [list(map(int,input().split())) for i in range(M)]
S, T = map(int,input().split())
hen2 = []
for i in range(N):
    a = []
    for j in hen:
        if j[0]==i+1:
            a.append(j[1])
    hen2.append(a)

queue = [[S,0]]
check = []
dist = [0]

while True:
    if queue == []:
        print(-1)
        break
    Now = queue.pop(0)
    ndist = dist.pop(0)
    if Now == [T,0]:
        print(int(ndist/3))
        break
    
    check.append(Now)
    for i in hen2[Now[0]-1]:
        if [i,(Now[1]+1)%3] not in check:
            queue.append([i,(Now[1]+1)%3])
            dist.append(ndist+1)
            

### FIXED CODE ###

S = input()

S = list(S)
S.sort()
if S[0] == S[1] and S[2] == S[3]:
    if S[1]!=S[2]:
        print("Yes")
    else:
        print("No")
else:
    print("No")
import sys
sys.setrecursionlimit(400*400)

H, W = map(int, input().split())
S = [input() for i in range(H)]

mask = ["".join(["#" if (i + j) % 2 else "." for j in range(W)]) for i in range(H)]

masked_S = [[1 if S[i][j] == mask[i][j] else 0 for j in range(W)] for i in range(H)]

S_colored = [[-1 for j in range(W)] for i in range(H)]

color_count = dict()


def fill(i, j, color):
    S_colored[i][j] = color

    if S[i][j] == "#":
        color_count[color][0] += 1
    else:
        color_count[color][1] += 1

    for yx in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
        dy, dx = yx
        i2, j2 = i + dy, j + dx

        if i2 < 0 or i2 >= H or j2 < 0 or j2 >= W:
            continue

        if S_colored[i2][j2] != -1:
            continue

        if masked_S[i2][j2] != masked_S[i][j]:
            continue

        fill(i2, j2, color)


def main():
    color = -1
    for i in range(H):
        for j in range(W):
            if S_colored[i][j] != -1:
                continue
            color += 1
            color_count[color] = [0, 0]
            fill(i, j, color)

    result = 0
    for k in color_count.keys():
        result += color_count[k][0] * color_count[k][1]

    print(result)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(400*400*400)

H, W = map(int, input().split())
S = [input() for i in range(H)]

mask = ["".join(["#" if (i + j) % 2 else "." for j in range(W)]) for i in range(H)]

masked_S = [[1 if S[i][j] == mask[i][j] else 0 for j in range(W)] for i in range(H)]

S_colored = [[-1 for j in range(W)] for i in range(H)]

color_count = dict()


def fill(i, j, color):
    S_colored[i][j] = color

    if S[i][j] == "#":
        color_count[color][0] += 1
    else:
        color_count[color][1] += 1

    for yx in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
        dy, dx = yx
        i2, j2 = i + dy, j + dx

        if i2 < 0 or i2 >= H or j2 < 0 or j2 >= W:
            continue

        if S_colored[i2][j2] != -1:
            continue

        if masked_S[i2][j2] != masked_S[i][j]:
            continue

        fill(i2, j2, color)


def main():
    color = -1
    for i in range(H):
        for j in range(W):
            if S_colored[i][j] != -1:
                continue
            color += 1
            color_count[color] = [0, 0]
            fill(i, j, color)

    result = 0
    for k in color_count.keys():
        result += color_count[k][0] * color_count[k][1]

    print(result)

if __name__ == '__main__':
    main()
from sys import stdin

input = stdin.readline


def main():
    s = list(input())
    s.reverse()
    MOD = 2019
    tot = 0
    ans = 0
    d = [0 for _ in range(MOD)]
    for i in range(len(s)):
        d[tot] += 1
        x = (10 ** i) % MOD
        p = int(s[i]) * x
        p %= MOD
        tot = (tot + p) % MOD
        ans += d[tot]
    return ans


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

def main():
    s = list(input())
    s.reverse()
    MOD = 2019
    tot = 0
    ans = 0
    d = [0 for _ in range(MOD)]
    for i in range(len(s)):
        d[tot] += 1
        x = pow(10, i, MOD)
        p = int(s[i]) * x
        p %= MOD
        tot = (tot + p) % MOD
        ans += d[tot]
    return ans


if __name__ == '__main__':
    print(main())
s = input()
s1 = []
le = []
cnt= 0
for i in list(s):
  if i!="x":
    le.append(cnt)
    s1.append(i)
  cnt+=1
if s1!=s1[::-1]:
  print(-1)
  exit()
print(le[len(le)//2])

### FIXED CODE ###

s = list(input())
s1=s[::-1]
ans = 0
cnt = 0
cnt1 = 0
while cnt<len(s) and cnt1<len(s) and cnt<=len(s)-1-cnt1:
  if s[cnt]!=s1[cnt1]:
    if s[cnt]=="x" and s1[cnt1]!="x":
      cnt+=1
      ans+=1
    elif s1[cnt1]=="x" and s[cnt]!="x":
      cnt1+=1
      ans+=1
    elif s[cnt]!="x" and s1[cnt1]!="x":
      print(-1)
      exit()
  elif s[cnt]==s1[cnt1]:
    cnt+=1
    cnt1+=1
print(ans)
n = int(input())
ele = []
ans = []
i = 1
while i * i < n:
    if n % i == 0:
        ele.append([len(str(i)),len(str(n // i))])
        ans.append([i,n//i])
    i += 1

k = max(ele[0][1],ele[0][0])
for i in range(len(ele)):
    k = min(max(ele[i][0],ele[i][1]),k)
print(k)

### FIXED CODE ###

n = int(input())
ele = []
i = 1
while i * i <= n:
    if n % i == 0:
        ele.append([len(str(i)),len(str(n // i))])
    i += 1

k = max(ele[0][1],ele[0][0])
for i in range(len(ele)):
    k = min(max(ele[i][0],ele[i][1]),k)
print(k)
N,X=map(int, input().split())
L=list(map(int, input().split()))

d = 0
count = 0

跳ねる直前からスタート

for i in range(1, N+2):
  if d <= X:
    count = count + 1
    d = d + L[i-1]

print(count)

### FIXED CODE ###

N,X=map(int, input().split())
L=list(map(int, input().split()))
L.append(0)


d = 0
count = 0

#跳ねる直前からスタート

for i in range(1, N+2):
  if d <= X:
    count = count + 1
    d = d + L[i-1]

print(count)
N=int(input())
X=int(int(N*100/108)*1.08)
print([':(',d][X==N])

### FIXED CODE ###

N=int(input())
X=int(N*100/108)
print(X if int(X*1.08)==N else X+1 if int((X+1)*1.08)==N else ':(')
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
C = []
for _ in range(M):
    b, c = map(int, input().split())
    C.extend([c]*b)
C.sort(reverse=True)

ans = 0
for i in range(M):
    if i == N:
        print(ans)
        exit()
    if C[i] <= A[0]:
        num = i
        break
    ans += C[i]
ans += sum(A[num:])
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
table = []
for i in range(N):
    table.append((A[i], 1))
for i in range(M):
    b, c = map(int, input().split())
    table.append((c, b))

table = sorted(table)
cnt = N
ans = 0
while cnt > 0:
    #print(ans,s)
    c, b = table.pop()
    if b >= cnt:
        ans += c*cnt
        break
    ans += c*b
    cnt -= b
print(ans)
n = int(input())
a = list(map(int , input().split()))
pos = sorted([i for i in a if i >= 0], reverse=True)
neg = sorted([i for i in a if i < 0])

ans = 0
if len(neg) == 0 and len(pos) == 2:
    print(pos[0], pos[1])
    exit()
elif len(neg) == 0:
    neg.append(pos.pop())

tmp = neg.pop()
ans = []
while len(pos) > 1:
    a = pos.pop()
    ans.append([tmp, a])
    tmp -= a

for i in neg:
    ans.append(tmp, i)
    tmp -= i

ans.append([pos[0], tmp])
print(pos[0] - tmp)
[print(*i) for i in ans]


### FIXED CODE ###

n = int(input())
a = list(map(int , input().split()))
pos = sorted([i for i in a if i >= 0], reverse=True)
neg = sorted([i for i in a if i < 0], reverse=True)

ans = []
if len(neg) == 0 and len(pos) == 2:
    print(pos[0] - pos[1])
    print(pos[0], pos[1])
    exit()
elif len(pos) == 0:
    tmp = neg[0]
    for i in range(1,len(neg)):
        ans.append([tmp, neg[i]])
        tmp -= neg[i]
    print(tmp)
    [print(*i) for i in ans]
    exit()
elif len(neg) == 0:
    neg.append(pos.pop())

tmp = neg.pop()
while len(pos) > 1:
    a = pos.pop()
    ans.append([tmp, a])
    tmp -= a
neg.append(tmp)

tmp = pos[0]
for i in neg:
    ans.append([tmp, i])
    tmp -= i

print(tmp)
[print(*i) for i in ans]
# -*- coding: utf-8 -*-

import math

r = input()
print "%f %f" %(r*r*math.pi, 2*r*mat.pi)

### FIXED CODE ###

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

import math

r = float(raw_input())
print "%f %f" %(r*r*math.pi, 2*r*math.pi)
def find(tab, a):
    if tab[0][a]==-1:
        return a
    tab[0][a] = find(tab, tab[0][a])
    return tab[0][a]

def union(tab, a, b):
    p1, p2 = (find(tab, a), find(tab, b))
    if p1 != p2:
        tab[0][p1] = p2
        tab[1][p2] += tab[1][p1]

def size(tab, a):
    return tab[1][a]

N, M = [int(a) for a in input().split(" ")]
ABs = [[int(a) for a in input().split(" ")] for i in range(M)]
tab = [[-1]*N, [1]*N]
arr = []

for a, b in reversed(ABs):
    a, b = (a-1, b-1)
    pa, pb = (find(tab, a), find(tab, b))
    na, nb = (size(tab, pa), size(tab, pb))
    if pa!=pb:
        dn = ((na+nb)*(na+nb-1)//2)-(na*(na-1)//2)-(nb*(nb-1)//2)
        arr.append(dn)
        union(tab, a, b)
    else:
        arr.append(0)

acc = 0
for cp in reversed(arr):
    acc += cp
    print(acc)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

def find(tab, a):
    if tab[0][a]==a:
        return a
    tab[0][a] = find(tab, tab[0][a])
    return tab[0][a]

def union(tab, a, b):
    p1, p2 = (find(tab, a), find(tab, b))
    if p1 != p2:
        tab[0][p1] = p2
        tab[1][p2] += tab[1][p1]

def size(tab, a):
    return tab[1][a]

N, M = [int(a) for a in input().split(" ")]
ABs = [[int(a) for a in input().split(" ")] for i in range(M)]
tab = [[i for i in range(N)], [1 for i in range(N)]]
arr = []

for a, b in reversed(ABs):
        a, b = (a-1, b-1)
        pa, pb = (find(tab, a), find(tab, b))
        na, nb = (size(tab, pa), size(tab, pb))
        if pa!=pb:
            dn = ((na+nb)*(na+nb-1)//2)-(na*(na-1)//2)-(nb*(nb-1)//2)
            arr.append(dn)
            union(tab, a, b)
        else:
            arr.append(0)

acc = 0
for cp in reversed(arr):
    acc += cp
    print(acc)