Harryxun/stf_run huggingface dataset:
from collections import deque
def bfs(maze, sy, sx, gy, gx):
    d = [[-1] * w for _ in range(h)]
    que = deque([[sy, sx]])
    #print(que)
    d[sy][sx] = 0
    while que:
        y, x = que.popleft()
        if y == gy and x == gx:
            break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            ny, nx = y + j, x + k
            if 0 <= nx < w  and 0 <= ny < h  and d[ny][nx] == -1 and maze[ny][nx] != "#":
                d[ny][nx] = d[y][x] + 1
                que.append([ny, nx])
                
    return d
gx, gy = w - 1, h - 1
def counting(maze, h, w, aim):
    cnt = 0
    for i in range(h):
        for j in range(w):
            if maze[i][j] == aim:
                cnt += 1
    return cnt
a = bfs(maze, 0, 0, gy, gx)
if a[gy][gx] == -1:
    print(-1)
else:
    print(h * w - (counting(maze, h, w, '#') + (a[gy][gx] + 1)))

### FIXED CODE ###

from collections import deque

def bfs():
    flag = False
    d = [[float('inf')] * W for i in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque([])
    que.append((0, 0))
    d[0][0] = 0

    while que:
        p = que.popleft()
        if p[0]==H-1 and p[1]==W-1:
            flag = True
            break

        for i in range(4):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]

            if 0<=nx<W and 0<=ny<H and maze[ny][nx]!='#' and d[ny][nx]==float("inf"):
                que.append((ny, nx))
                d[ny][nx] = d[p[0]][p[1]] + 1

    if flag==False:
        return False

    return d[H-1][W-1]

def notcount(H, W, maze):
    cnt = 0

    for i in range(H):
        for j in range(W):
            if maze[i][j]=='#':
                cnt += 1

    return cnt

H, W = map(int, input().split())
maze = [list(input()) for i in range(H)]
if bfs()==False:
    print(-1)
else:
    s = (H * W - notcount(H, W, maze)) - (bfs() + 1)
    #bfs()
    print(s)
n = int(input())

if n>81:
    print("No")
    exit()
elif n<10:
    print("Yes")
    exit()
elif n%2==0:
    a = n/2
    if a<10:
        print("Yes")
        exit()
    else n%3==0:
        a = n/3
        if a<10:
            print("Yes")
            exit()
        else n%4==0:
            a = n/4
            if a<10:
                print("Yes")
                exit()
            else n%5==0:
                a = n/5
                if a<10:
                    print("Yes")
                    exit()
                else n%6==0:
                    a = n/6
                    if a<10:
                        print("Yes")
                        exit()
                    else n%7==0:
                        a = n/7
                        if a<10:
                            print("Yes")
                            exit()
                        else n%8==0:
                            a = n/8
                            if a<10:
                                print("Yes")
                                exit()
                            else n%9==0:
                                a = n/9
                                if a<10:
                                    print("Yes")
                                    exit()
                                else:
                                    print("No")

### FIXED CODE ###

n = int(input())

if n>81:
    print("No")
elif n<10:
    print("Yes")
else:
    for i in reversed(range(1,10)):
        if n%i==0:
            s = n/i
            if s<10:
                print("Yes")
                exit()
    print("No")
N = int(input())
A = list(map(int, input().split()))

ans = []

for i in range(N - 1):
    l, r = A[i], A[i + 1]

    if l > r:
        addR = None

        if 0 < r:
            addR = True

        if l < 0:
            addR = False

        if r <= 0 <= l:
            if abs(l) >= abs(r):
                addR = True
            else:
                addR = False

        if addR:
            A[i + 1] += l * 2
            ans.append((i, i + 1))
            ans.append((i, i + 1))
        else:
            A[i] += r * 2
            ans.append((i + 1, i))
            ans.append((i + 1, i))

print(len(ans))
for x, y in ans:
    print(x + 1, y + 1)

if list(sorted(A)) != A:
    1 / 0


### FIXED CODE ###

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

ans = []
mx = max(A)
mi = min(A)

if mx * mi < 0:
    if abs(mi) > abs(mx):
        x = A.index(mi)
        for y in range(N):
            if y == x:
                continue
            A[y] += mi
            ans.append((x, y))
    else:
        x = A.index(mx)
        for y in range(N):
            if x == y:
                continue
            A[y] += mx
            ans.append((x, y))

for i in range(N - 1)[::(-1)**(min(A) < 0)]:
    l, r = A[i], A[i + 1]

    if l > r:
        if r >= 0:
            A[i + 1] += l
            ans.append((i, i + 1))
        elif l <= 0:
            A[i] += r
            ans.append((i + 1, i))

print(len(ans))
for x, y in ans:
    print(x + 1, y + 1)

if list(sorted(A)) != A:
    print(A)
    1 / 0
n, q = map(int,input().split())
s = list(input())
x = []
ans = 0
for i in range(n-1):
	if s[i] == "A" and s[i+1] == "C":
		ans += 1
		x.append(ans)
	else:
		x.append(ans)

for j in range(q):
	l, r = map(int,input().split())
	print(x[r-1]-x[l-1])

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
c=[0]
t=0

for i in range(0,n-1):
    if s[i]=="A" and s[i+1]=="C":
        t+=1
        c.append(t)
    else:
        c.append(t)

for i in range(q):
    l,r=map(int,input().split())
    print(c[r-1]-c[l-1])
N = int(input())
num_list = list(map(int, input().split()))
 
a=0
for i in num_list:
  if i%2==0 and (i%3!=0 and i%5!=0):
  	print('DENIED')
    exit()
print('APPROVED')

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
app_fl = True
for Ai in [a for a in A if a % 2 == 0]:
    if Ai % 3 != 0 and Ai % 5 != 0:
        app_fl = False
        break
 

if app_fl is True:
    print("APPROVED")
else:
    print("DENIED")
# unionfind

class UnionFind(object):

    def __init__(self, n):
        self.n = n
        self.parent = list(range(self.n))
        self.rank = [0]*self.n

    def find_parent(self, xx):
        if self.parent[xx] == xx:
            return xx
        else:
            self.parent[xx] = self.find_parent(self.parent[xx])
            return self.parent[xx]

    def unite(self, xx, yy):
        xp = self.find_parent(xx)
        yp = self.find_parent(yy)
        if xp == yp:
            return None
        else:
            self.parent[xp] = yp
            return None


N, M = map(int, input().split())
uf = UnionFind(N+1)

for _ in range(M):
    x, y, z = map(int, input().split())
    uf.unite(x, y)

res = [0] * (N + 1)
res_c = 0
for i in range(1, N + 1):
    j = uf.find_parent(i)
    if res[j] == 0:
        res_c += 1
    res[j] += 1

print(N - (sum(res) - res_c))


### FIXED CODE ###

# unionfind


class UnionFind(object):

    def __init__(self, n):
        self.n = n
        self.parent = list(range(self.n))
        self.rank = [0]*n

    def find_parent(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find_parent(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find_parent(x)
        y = self.find_parent(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


N, M = map(int, input().split())
uf = UnionFind(N+1)

for _ in range(M):
    xx, yy, zz = map(int, input().split())
    uf.unite(xx, yy)

res = [0] * (N + 1)
res_c = 0
for i in range(1, N + 1):
    j = uf.find_parent(i)
    if res[j] == 0:
        res_c += 1
    res[j] += 1

print(N - (sum(res) - res_c))
import math 

N=int(input())
l=10**9+7
nums=list(map(int,input().split()))
k=int(math.log2(max(nums)))+1
mat=[0]*k
for each in nums:
    num=str(bin(each))[2:].zfill(k)
    for i in range(k):
        if num[i]=="1":
            mat[i]+=1

ans=sum([ (N-mat[i])*mat[i]*pow(2,(k-i-1),l) for i in range(k)])
print(ans%l)

### FIXED CODE ###

mod=10**9+7
N=int(input())
str_a = ''.join(['{:060b}'.format(a) for a in map(int, input().split())])

ans=0
for i in range(60):
    ones=str_a[59-i::60].count("1")
    ans+= pow( 2, i ,mod)* ones *(N-ones)
print(ans%mod)
N,W = map(int,input().split())
w,v = [0 for _ in range(N)],[0 for _ in range(N)]

for i in range(N):
    w[i],v[i] = map(int,input().split())

dp = [[0 for _ in range(110)] for _ in range(100100)]

for i in range(N):
    for sum_w in range(0,W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i])

        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

#dp[i]][sum_w]
print(dp[N][W])

### FIXED CODE ###

N,W = map(int,input().split())
w,v = [0 for _ in range(N)], [0 for _ in range(N)]
for i in range(N):
    w[i],v[i] = map(int,input().split())
# dp[i][w] = [合計重さ,重さw で得られる最大の価値v]
dp = [[0 for _ in range(W+1)] for i in range(N+1)]

for i in range(N):
    for sum_w in range(W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i][sum_w], dp[i][sum_w - w[i]] + v[i])
        dp[i+1][sum_w] = max(dp[i+1][sum_w],dp[i][sum_w])

# for i in dp:
#     print(i)
print(dp[N][W])
x, y = map(int, input().split())
 
num = 0
while x < y:
    num += 1
    x *= 2
    
print(num)

### FIXED CODE ###

a,b,c,d = map(int, input().split())

l = a+b
r = c+d
msg = "Balanced"
if l > r:
   msg = "Left"
elif l < r:
   msg = "Right"
print(msg)
import copy
h, w = map(int, input().split())

a = [list(map(lambda x: int(x) % 2, input().split())) for _ in range(h)]
# for v in a:
#     print(*v)

directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
visited = copy.deepcopy(a)
number = [[i * w + j for j in range(w)] for i in range(h)]
def bfs(x, y):
    graph = [[] for _ in range(h * w)]
    que = [(x, y)]
    visited[y][x] = 0
    while que:
        x, y = que.pop(0)
        n = number[y][x]

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < w and 0 <= ny < h and visited[ny][nx] == 1:
                que.append((nx, ny))
                nn = number[ny][nx]
                graph[n].append(nn)
                visited[ny][nx] = 0
                # graph[nn].append(n)
    return graph


def dfs(i, slide):
    if not graph[i]:
        dp[slide][i] = slide, None
        return slide

    r = dp[slide].get(i)
    if r is not None:
        return r[0]

    none = [dfs(c, 0) for c in graph[i]]
    if slide:
        r = sum(none)
        dp[slide][i] = r, None
        return r + 1
    else:
        to = [dfs(c, 1) for c in graph[i]]
        r = 0
        merge = None
        for i_ in range(len(graph[i])):
            s = 0
            for j_ in range(len(graph[i])):
                if j_ == i_: # slide!!
                    s += to[j_]
                else:
                    s += none[j_]
            if s > r:
                r = s
                merge = graph[i][i_]
        s = sum(none)
        if s > r:
            r = s
            merge = None
        dp[slide][i] = r, merge
        return r


def xy(i):
    return i % w, i // w


answers = []
def dfs_answer(i, slide):
    _, to = dp[slide][i]
    for c in graph[i]:
        if c == to:
            answers.append((*xy(i), *xy(to)))
            dfs_answer(c, 1)
        else:
            dfs_answer(c, 0)


for i in range(h):
    for j in range(w):
        if visited[i][j]:
            graph = bfs(j, i)
            dp = [{}, {}]
            dfs(number[i][j], 0)
            # print(dfs(number[i][j], 0), ":", j, i, number[i][j])
            #
            # print("--------")
            dfs_answer(number[i][j], 0)
            # __import__("sys").exit()

print(len(answers))
for ans in answers:
    print(*ans)


### FIXED CODE ###

h, w = map(int, input().split())

a = [list(map(lambda x: int(x) % 2, input().split())) for _ in range(h)]

road = []
for i in range(h):
    for j in list(range(w))[::(i % 2) * -2 + 1]:
        road.append((i + 1, j + 1))

answer = []
for f, t in zip(road[:-1], road[1:]):
    if a[f[0] - 1][f[1] - 1] % 2:
        answer.append(f + t)
        a[t[0] - 1][t[1] - 1] += 1

print(len(answer))
for ans in answer:
    print(*ans)
N,A=int(input()),int(input())
print('Yes' if N%500<=A else 'No')

### FIXED CODE ###

r,g,b=map(int,input().split())
result = (r*100+g*10+b)%4
if result==0:
  print('YES')
else:
  print('NO')
def choose(n,a,mod):
    x, y = 1, 1
    for i in range(a):
        x = x * (n - i) % mod
        y = y * (i + 1) % mod
    return x * pow(y, mod - 2, mod) % mod

n,m = map(int,input().split())
ans = 0
mod = pow(10**9+7)
for i in range(n+1):
    if i == 0:
        stand = choose(m,n,mod)
        ans += stand
        k = 1
    else:
        k*=i
        k %= mod
        stand *= (-1)*n*pow(m,mod-2,mod)
        stand %= mod
        ans += pow(k,mod-2,mod)*stand
        ans %= mod
ans *= k
ans %= mod
print(ans)

### FIXED CODE ###

mod = pow(10,9)+7
n,m = map(int,input().split())
ans = 0
inv = [0,1]
fact = [1,1]
ifact = [1,1]
for i in range(2,m+1):
    inv.append(inv[mod%i]*(mod-int(mod/i))%mod)
    fact.append(i*fact[-1]%mod)
    ifact.append(ifact[-1]*inv[i]%mod)

def combi(a,b):
    return fact[a]*ifact[b]*ifact[a-b]%mod
def permi(a,b):
    return fact[a]*ifact[a-b]%mod

for i in range(n+1):
    now = combi(n,i)
    now *= permi(m-i,n-i)
    now %= mod
    ans += now*(-1)**(i&1)
    ans %= mod
ans *= permi(m,n)
ans %= mod
print(ans)
x=int(input())
p=x**0.5
ans=[]
for i in range(1,p+1):
  j=2
  while True:
    if i**j<=p:
      ans.append(i**j)
    else:
      break
    j+=1
print(max(ans))

### FIXED CODE ###

x=int(input())
import math
p=math.ceil(x**0.5)
ans=[1]
for i in range(2,p+1):
  j=2
  while True:
    if i**j<=x:
      ans.append(i**j)
    else:
      break
    j+=1
print(max(ans))
N, K = map(int, input().split())

def combination(a, b):
    minb = min(a-b, b)
    r = 1
    for i in range(1, minb+1):
        r = r * (a-minb+i)/i
    return int(r)

for i in range(1, K+1):
    must = combination(K-1, i-1)
    left_ball = N-K-i+1
    if left_ball < 0:
        print(0)
        continue
    can = combination(left_ball+i, i)
    print((must*can)%1000000007)

### FIXED CODE ###

N, K = map(int, input().split())
mod = 10**9+7

import math

def combination(a, b):
    minb = min(a-b, b)
    r = 1
    for j in range(1, minb+1):
        r = r * (a-minb+j)//j
    return int(r)

for i in range(1, K+1):
    if N==K and i!=1:
        print(0)
        continue
    must = combination(K-1, i-1)
    if must is None:
        print("K:"+str(K)+", i:"+str(i))
    left_ball = N-K-i+1
    if left_ball < 0:
        print(0)
        continue
    can = combination(left_ball+i, i)
    print((must*can)%mod)
#define int long long
 
 
const int mod = 1e9+7;
int fact[2020];
 
int power(int a, int b){
    int ans = 1;
    while(b){
        if (b&1){
            ans = (ans*a)%mod;
        }
        a = (a*a)%mod;
        b>>=1;
    }
    return ans;
}
 
int inv(int a){
    return power(a, mod-2);
}
 
int ncr(int n, int r){
    int denom = fact[r] * fact[n-r] %mod;
    denom = inv(denom);
    return (fact[n]*denom)%mod;
}
 
 
signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
 
    int n;
    cin>>n;
 
    if(n==3){
        cout<<1<<endl;
        return 0;
    }
 
    fact[0] = 1;
    for (int i=1; i<=n; i++){
        fact[i] = (i*fact[i-1])%mod;
    }
 
    //n-1cr-1
    //n-1-2*icri-1
 
    int ans = 0;
    for (int i=1; (n-1-2*i)>0; i++){
        if (n-1-2*i<i-1) break;
        ans = (ans + ncr(n-1-2*i, i-1))%mod;
    }
    cout<<ans<<endl;
 
 
 
    return 0;
}

### FIXED CODE ###

#import sys
#input = sys.stdin.readline
Q = 10**9+7
def cmb(n,r):
    if n-r < r: r = n-r
    if r == 0: return 1
    denominator = 1                       #分母
    numerator = 1                         #分子
    for i in range(r):
        numerator *= n-i
        numerator %= Q
        denominator *= i+1
        denominator %= Q
    return numerator*pow(denominator, Q-2, Q)%Q
 
def main():
    S = int( input())
    ans = 0
    for i in range(1, S//3+1):
        t = S - i*3
        ans += cmb(t+i-1,i-1)
        ans %= Q
    print(ans)
        
if __name__ == '__main__':
    main()
def calc(X):
    A = 1
    B = 1
    if X == 0:
        return A,B
    else:
        l_bound = int(X**0.2)
        h_bound = l_bound * 2
        for i in range(l_bound,h_bound):
            for j in range(0,i+1):
                if i ** 5 - j ** 5 == X:
                    A = i
                    B = j
                    return A,B
                if i ** 5 + j ** 5 == X:
                    A = i
                    B = -j
                    return A,B
def resolve():
    X = int(input())
    A,B = calc(X)  
    print(str(A) + " " + str(B))
resolve()

### FIXED CODE ###

def calc(X):
    A = 1
    B = 1
    if X == 0:
        return A,B
    else:
        l_bound = 1
        h_bound = 200
        for i in range(l_bound,h_bound):
            for j in range(0,i+1):
                if i ** 5 - j ** 5 == X:
                    A = i
                    B = j
                    return A,B
                if i ** 5 + j ** 5 == X:
                    A = i
                    B = -j
                    return A,B
def resolve():
    X = int(input())
    A,B = calc(X)  
    print(str(A) + " " + str(B))
resolve()
import math
n,k = map(int,input().split())

ret=0

for i in range(1,n+1):
    p=math.ceil(math.log2(k/i))
    p=p if p>0 else 0
    ret+=math.pow(0.5,p)/n

print(ret)


### FIXED CODE ###

import math
n,k = map(int,input().split())

ret=0

for i in range(1,n+1):
    p=math.ceil(math.log2(k/i))
    p=p if p>0 else 0
    ret+=math.pow(0.5,p)/n

ret=math.floor(ret*1e12)*1e-12
print(ret)
S = list(input())
print(sum(S))

### FIXED CODE ###

S = list(input())
S = list(map(int, S))
print(sum(S))
N = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())

min = min(A, B, C, D, E)

ans = 4 + int(N/min)
    if N % min != 0:
        ans = ans + 1
print(ans)

### FIXED CODE ###

N = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())
 
min = min(A, B, C, D, E)
 
ans = 4 + int(N/min)
if N % min != 0:
    ans = ans + 1
print(ans)
N, A, B = map(int, input().split())
print(min([A * T, B]))

### FIXED CODE ###

N, A, B = map(int, input().split())
print(min([A * N, B]))
A, B, C = map(int, input().split())
if A == B and B == C:
    print(Yes)
else:
    print(No)

### FIXED CODE ###

A, B, C = map(int, input().split())
if A == B and B == C and C == A:
    print("Yes")
elif A!=B or B!=C or C!=A:
    print("No")
N, K = map(int,input().split())
A = list(map(int, input().split())) 
check = [0]*N
tele_lis = []
global start
start = []
def tele(x):
    check[x-1] = 1
    tele_lis.append(x)
    if check[A[x-1]-1] == 0:
        tele(A[x-1])
    else:
        start.append(A[x-1])
        return
tele(1)
for i in range(N):
    if start[0] == tele_lis[i]:
        break
    
print(tele_lis[i::][(K-i) % (sum(check)-i)])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

N, K = map(int,input().split())
A = list(map(int, input().split())) 
check = [0]*N
tele_lis = []
start = []
def tele(x):
    check[x-1] = 1
    tele_lis.append(x)
    if check[A[x-1]-1] == 0:
        tele(A[x-1])
    else:
        start.append(A[x-1])
        return
tele(1)
for i in range(N):
    if start[0] == tele_lis[i]:
        break
if i >= K:
    print(tele_lis[K])
else:
    print(tele_lis[i::][(K-i) % (sum(check)-i)])
a,b,c,d = list(map(int, input().split()))
if a+b>=d:
    print(a)
else:
    print(a-(d-a-b)

### FIXED CODE ###

n=input()
s=input()
l=len(n)
if n+s[l]==s:
    print("Yes")
else:
    print("No")
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()


def main():
    x, y =input().split()
    if ord(x) < ord(y):
        print("<")
    elif ord(X) > ord(y):
        print(">")
    else:
        print("=")
    


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()


def main():
    x, y =input().split()
    if ord(x) < ord(y):
        print("<")
    elif ord(x) > ord(y):
        print(">")
    else:
        print("=")
    


if __name__ == "__main__":
    main()
from itertools import produce

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


print(produce([A]*K, [B]*K, [C]*K))


### FIXED CODE ###

S = input()
T = input()

if S == T[:-1] and len(S) + 1 == len(T):
  print("Yes")
else:
  print("No")
import math
A, B = map(int, input().split())

GCD = math.gcd(A, B)



import collections


def primes_ordered_dict(n):
    #
    prime_list = []
    non_prime_list = []
    number_dict = collections.OrderedDict(
        ((i, None) for i in range(n + 1)))
    #
    del number_dict[0]
    del number_dict[1]
    while True:
        # get prime
        prime, _ = number_dict.popitem(False)
        if A % prime == 0 and B % prime == 0:
            prime_list.append(prime)
        # break
        if not (prime * prime <= n):
            break
        # get non primes
        non_prime_list.append(prime * prime)
        for k in number_dict:
            if prime * k <= n:
                non_prime_list.append(prime * k)
            else:
                break
        # delete non primes
        for non_prime in non_prime_list:
            del number_dict[non_prime]
        non_prime_list.clear()

    # add rest of numbers as prime
    prime_list.extend(
        [prime for prime, _ in number_dict.items() if A % prime == 0 and B % prime == 0])

    return prime_list

if GCD == 1:
    print(1)
else:
    print(len(primes_ordered_dict(GCD))+1)

### FIXED CODE ###

import collections
import math

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


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
     # divisors.sort()
    return divisors



def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

A_div = set(make_divisors(A))
B_div = set(make_divisors(B))
common_div = (A_div & B_div)

cnt = 1
for c in common_div:
    if is_prime(c):
        cnt += 1

print(cnt)
a, b = map(int, input().split())
if a * b % 2 == 0:
    print("Even")
elif:
    print("Odd")
    

### FIXED CODE ###

a, b = map(int, input().split())
if a * b % 2 == 0:
    print("Even")
else:
    print("Odd")
n, m = map(int, input().split())
p = list(map(lambda x: x-1, map(int, input().split())))
t = [tuple(map(lambda x: x-1, map(int, input().split()))) for _ in range(m)]

a = [set() for _ in range(n)]
for i, j in t:
    a[p[i]].add(p[j])
    a[p[j]].add(p[i])

def dfs(x, v):
    if v[x] == 0:
        v[x] = 1
        for i in a[x]:
            dfs(i, v)

mx = []
for i in range(n):
    v = [0]*n
    dfs(i, v)
    mx.append(v)

ans = 0
for i in range(n):
    tmp = p[i]
    idx = p.index(i)
    if mx[tmp][i]:
        ans += 1
        p[i] = i
        p[idx] = tmp
print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
p = list(map(lambda x: x-1, map(int, input().split())))

follow = [i for i in range(n)]
num = [1]*n
def root_index_of(x):
    r = x
    while follow[r] != r:
        r = follow[r]
    return r

def connected(x, y):
    return root_index_of(x) == root_index_of(y)

def connect(x, y):
    rx = root_index_of(x)
    ry = root_index_of(y)

    if rx == ry:
        return

    if num[rx] < num[ry]:
        follow[rx] = ry
        follow[x] = ry
        num[ry] += num[rx]
    else:
        follow[ry] = rx
        follow[y] = rx
        num[rx] += num[ry]

for i in range(m):
    x, y = map(lambda x: x-1, map(int, input().split()))
    connect(p[x], p[y])

ans = 0
for i in range(n):
    if connected(i, p[i]):
        ans += 1
print(ans)