N = int(input())

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

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

visited = [ [0]*M for _ in range(N) ]

def transpose(A):
    return [list(x) for x in zip(*A)]

from itertools import combinations
for m1, m2 in combinations(range(M),2):

from itertools import product
for p in product((0,1),repeat=R): # bit全探索

V, E = map(int, input().split())
INF = 10**10
cost = [[INF]*V for _ in range(V)] # 重み
for e in range(E):
    s, t, d = map(int,input().split())
    cost[s][t] = d

dp = [[-1] * V for _ in range(1<<V)] # dp[S][v]

def dfs(S, v, dp):
    if dp[S][v] != -1: # 訪問済みならメモを返す
        return dp[S][v]
    if S==(1<<V)-1 and v==0: # 全ての頂点を訪れて頂点0に戻ってきた
        return 0 # もう動く必要はない

    res = INF
    for u in range(V):
        if S>>u & 1 == 0: # 未訪問かどうか
            res = min(res, dfs(S|1<<u, u, dp)+cost[v][u])
    dp[S][v] = res
    return res

ans = dfs(0, 0, dp) # 頂点0からスタートする。ただし頂点0は未訪問とする
if ans == INF:
    print(-1)
else:
    print (ans)

import bisect
INF = 10**10
N = int(input())
dp = [INF] * (N)
for n in range(N):
    a = int(input())
    i = bisect.bisect_left(dp, a)
    dp[i] = a # aがA[:n]中で最大なら、最も左のINFが更新される
print(bisect.bisect_left(dp, INF)) # 最後にINF以外の要素数を数える

Q = int(input())

def lcs(X, Y):
    dp = [[0] * (len(X)+1) for _ in range(len(Y)+1)]
    for i in range(1,len(Y)+1):
        for j in range(1,len(X)+1):
            if X[j-1]==Y[i-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i][j-1],dp[i-1][j])
    return dp[-1][-1]

ans = []
for q in range(Q):
    X = input()
    Y = input()
    ans.append(lcs(X,Y))
for a in ans:
    print(a)

class UnionFind:
    def __init__(self, n):
        self.nodes = n
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
        self.rank = [0] * n

    def find(self, i): # どの集合に属しているか（根ノードの番号）
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i]) # 経路圧縮
            return self.parents[i]

    def unite(self, i, j): # 二つの集合を併合
        pi = self.find(i)
        pj = self.find(j)
        if pi != pj:
            if self.rank[pi] < self.rank[pj]:
                self.sizes[pj] += self.sizes[pi]
                self.parents[pi] = pj
            else:
                self.sizes[pi] += self.sizes[pj]
                self.parents[pj] = pi
                if self.rank[pi] == self.rank[pj]:
                    self.rank[pi] += 1
    def same(self, i, j): # 同じ集合に属するかを判定
        return self.find(i)==self.find(j)

    def get_parents(self): # 根ノードの一覧を取得
        for n in range(self.nodes): # findで経路圧縮する
            self.find(n)
        return self.parents

    def size(self, i):
        p = self.find(i)
        return self.sizes[p]


N, M = map(int, input().split())
AB = []
B = []
for m in range(M):
    a, b = map(int, input().split())
    AB.append((a-1,b-1))

ans = []
score = N * (N-1) // 2
uf = UnionFind(N)
for a, b in AB[::-1]:
    ans.append(score)
    if not uf.same(a,b):
        score -= uf.size(a) * uf.size(b)
        uf.unite(a,b)    

for score in ans[::-1]:
    print(score)

from itertools import product
R, C = map(int,input().split())
lines = []
for r in range(R):
    line = list(map(int,input().split()))
    lines.append(line)
lines = list(zip(*lines))
ans = 0
for p in product((0,1),repeat=R):
    sm = 0
    for line in lines:
        cnt = 0
        for r in range(R):
            if p[r] == line[r]:
                cnt += 1
        sm += max(cnt, R-cnt)
    ans = max(ans, sm)
print (ans)

class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
        self.rank = [0] * n

    def find(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i]) # 経路圧縮
            return self.parents[i]

    def unite(self, i, j):
        pi = self.find(i)
        pj = self.find(j)
        if pi != pj:
            if self.rank[pi] < self.rank[pj]:
                self.sizes[pj] += self.sizes[pi]
                self.parents[pi] = pj
            else:
                self.sizes[pi] += self.sizes[pj]
                self.parents[pj] = pi
                if self.rank[pi] == self.rank[pj]:
                    self.rank[pi] += 1
    def same(self, i, j):
        return self.find(i)==self.find(j)


n, q = map(int,input().split())
uf = UnionFind(n)
for q in range(q):
    cmd, i, j = map(int,input().split())
    if cmd == 0:
        uf.unite(i,j)
    else:
        print(int(uf.same(i,j)))

import queue
N = int(input())

adj = [[]for i in range(N+1)]
depth = [-1] * (N+1)
for n in range(1,N+1):
    V = list(map(int,input().split()))
    for v in V[2:]:
        adj[n].append(v)
    
q = queue.Queue()
q.put((1,0)) # 番号、深さ
while(not q.empty()):
    x, d = q.get()
    if depth[x] != -1:
        continue
    depth[x] = d
    for next in adj[x]:
        if depth[next] == -1:
            q.put((next,d+1))

for i in range(1,N+1):
    print(i,depth[i])

N = int(input())
N%=10
if N==3:
    print('bon')
elif N in (0,1,6,8):
    print('pon')
else:
    print('hon')

K = int(input())
S = input()
if len(S)<=K:
    print(S)
else:
    print(S[:K]+'...')

import math
A,B,H,M = map(int,input().split()) 
H = (H+M/60)*30 # 360度/12時間 = 30度、長針は短針より60倍遅い
M *= 6 # 360度/60分 = 6度
d = abs(H-M) # 長針と短針のなす角度
if d > 180: # 角度は180度以下
    d = 360 - d
C = pow(A**2+B**2-2*A*B*math.cos(math.radians(d)),0.5)
print(C)

import queue
N,M = map(int,input().split())
adj = [[]for i in range(N+1)]
parent = [-1] * (N+1) # -1なら未訪問
for m in range(M):
    a,b = map(int,input().split())
    adj[a].append(b)
    adj[b].append(a)
q = queue.Queue() # 自分の部屋番号、親の部屋番号
q.put((1,0)) # 部屋1の親は部屋0と考える
while(not q.empty()):
    x, p = q.get()
    if parent[x] != -1: # 訪問済み
        continue
    parent[x] = p
    for next in adj[x]:
        if parent[next] == -1: # 未訪問なら
            q.put((next,x)) # 探索候補に追加
print ('Yes') # 必ず目標は達成できる
for p in parent[2:]: # 部屋2以降の親（前の部屋）
    print(p)

import math
MOD = 1000000007
N = int(input())

even = dict() # (+,+), (-,-)
odd = dict() # (+,-), (-,+)
ans = 1
zz = 0 # (0,0)の場合は、その数だけ答えをインクリメントすれば良い

for n in range(N):
    a,b = map(int,input().split())

    if a==0 and b==0:
        zz += 1 # かぞえあげる
        continue # 考察対象から除外
    if a==0:
        n_sign = 0
        b = 0 # こうしておくと後ほど'0/0'として格納される
    elif b==0:
        n_sign = 1
        a = 0 # こうしておくと後ほど'0/0'として格納される

    else:    
        n_sign = ((a<0) + (b<0)) % 2 # -の出現回数が偶数か奇数か
        a = abs(a) # 符号は用済み
        b = abs(b) # 符号は用済み
        gcd = math.gcd(a,b) # 約分のためにGCDを計算
        a//=gcd # 約分
        b//=gcd # 約分

    if n_sign==1:
        s =str(b)+'/'+str(a) # '41/3'のように文字列として扱う
        odd[s] = odd.get(s,0) + 1 # かぞえあげる
    elif n_sign==0:
        s =str(a)+'/'+str(b) # 逆数を考えることで単純な文字列比較に持ち込む
        even[s] = even.get(s,0) + 1      

for k,v in odd.items():
    if k in even: # 共存NGあり
        ans *= (2**v + 2**even[k] - 1)
        even.pop(k) # 辞書から削除
    else: # 共存NGなし
        ans *= 2**v
    ans %= MOD

for k,v in even.items():
    ans *= 2**v # 削除していない分を数える
    ans %= MOD

ans -= 1 # 1匹も選択しないのはNG
ans += zz
ans %= MOD
print (ans)