Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Connected Components

  Write a program which reads relations in a SNS (Social Network Service), and judges that given pairs of users are reachable each other through the network.

Input

  In the first line, two integer $n$ and $m$ are given. $n$ is the number of users in the SNS and $m$ is the number of relations in the SNS. The users in the SNS are identified by IDs $0, 1, ..., n-1$.

  In the following $m$ lines, the relations are given. Each relation is given by two integers $s$ and $t$ that represents $s$ and $t$ are friends (and reachable each other).

  In the next line, the number of queries $q$ is given. In the following $q$ lines, $q$ queries are given respectively. Each query consists of two integers $s$ and $t$ separated by a space character.

Output

  For each query, print "yes" if $t$ is reachable from $s$ through the social network, "no" otherwise.

Constraints

$2 \leq n \leq 100,000$

$0 \leq m \leq 100,000$

$1 \leq q \leq 10,000$

Sample Input

10 9
0 1
0 2
3 4
5 7
5 6
6 7
6 8
7 8
8 9
3
0 1
5 9
1 3

Sample Output

yes
yes
no



Sample input:
10 9
0 1
0 2
3 4
5 7
5 6
6 7
6 8
7 8
8 9
3
0 1
5 9
1 3


Sample output:
yes
yes
no

Submission status: Runtime Error

Solution code:
def bfs(graph, start, goal, connection):
    visited = {start: None}
    unvisited = [start]
    while unvisited:
        now = unvisited[0]
        if now == goal or (1000000*now + goal) in connection:
            connection[1000000*start + goal] = 1
            return "yes"
        unvisited = unvisited[1:]
        for next in graph[now]:
            if not (next in visited):
                unvisited.append(next)
                visited[next] = now
    return "no"

n, m = map(int, input().split())
g = [None]*n
c = {}

for i in range(m):
    inp = list(map(int, input().split()))
    g[inp[0]].append(inp[1])
    g[inp[1]].append(inp[0])

q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    print(bfs(g, s, t, c))

Submission status: Runtime Error

Solution code:
def bfs(graph, start, goal, connection):
    visited = {start: None}
    unvisited = [start]
    while unvisited:
        now = unvisited[0]
        if now == goal or (1000000*now + goal) in connection:
            connection[1000000*start + goal] = 1
            connection[1000000*goal + start] = 1
            return "yes"
        unvisited = unvisited[1:]
        for next in graph[now]:
            if not (next in visited):
                unvisited.append(next)
                visited[next] = now
    return "no"

n, m = map(int, input().split())
g = [[] for i in range(n)]
c = {}

for i in range(m):
    inp = list(map(int, input().split()))
    g[inp[0]].append(inp[1])
    g[inp[1]].append(inp[0])
    connection[1000000*inp[0] + inp[1]] = 1
    connection[1000000*inp[1] + inp[0]] = 1

q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    print(bfs(g, s, t, c))

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(graph, start, goal, connection):
    visited = {start: None}
    unvisited = deque(start)
    while unvisited:
        now = unvisited.popleft()
        if now == goal or (1000000*now + goal) in connection:
            connection[1000000*start + goal] = 1
            connection[1000000*goal + start] = 1
            return "yes"
        for next in graph[now]:
            if not (next in visited):
                unvisited.append(next)
                visited[next] = now
    return "no"

n, m = map(int, input().split())
g = [[] for i in range(n)]
c = {}

for i in range(m):
    inp = list(map(int, input().split()))
    g[inp[0]].append(inp[1])
    g[inp[1]].append(inp[0])
    c[1000000*inp[0] + inp[1]] = 1
    c[1000000*inp[1] + inp[0]] = 1

q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    print(bfs(g, s, t, c))

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(graph, start, goal, connection):
    visited = {start: None}
    unvisited = deque()
    unvisited.append(start)
    while unvisited:
        now = unvisited.popleft()
        if now == goal or goal in connection[now]:
            connection[start].add(goal)
            connection[goal].add(start)
            return "yes"
        for next in graph[now]:
            if not (next in visited):
                unvisited.append(next)
                visited[next] = now
    return "no"

n, m = map(int, input().split())
g = [set() for i in range(n)]
c = [set() for i in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    g[a].add(b)
    g[b].add(a)
    c[a].add(b)
    c[b].add(inp[a])

q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    print(bfs(g, s, t, c))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [[False]*n for i in range(n)]
rootList = [-1] * n

def hasSameRoot(x, y):
    if rootList[x] == rootList[y] != -1:
        return True
    elif rootList[x] == x and rootList[y] == y:
        return False
    elif x > 1:
        return hasSameRoot(y, x-1)
    else:
        return hasSameRoot(x, y-1)


for i in range(m):
    s, t = map(int, input().split())
    if rootList[s] < 0:
        rootList[s] = s
    if rootList[t] < 0:
        rootList[t] = t
    if rootList[s] != rootList[t]:
        rootList[s] = min(rootList[s], rootList[t])
        rootList[t] = min(rootList[s], rootList[t])
q = int(input())
for i in range(q):
    s, t = map(int, input().split()):
    if hasSameRoot(s, t):
        print("yes")
    else:
        print("no")

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
rootList = [-1] * n

def getRoot(x):
    if rootList[x] < 0:
        return x
    rootList[x] = getRoot(rootList[x])
    return rootList[x]

def setSameRoot(x, y):
    x = getRoot(x)
    y = getRoot(y)
    if x != y:
        G[x], G[y] = min(x, y), min(x, y)

for i in range(0, m):
    s, t = map(int, input().split())
    setSameRoot(s, t)
q = int(input())
for i in range(0, q):
    s, t = map(int, input().split())
    print("yes" if getRoot(s) == getRoot(t) else "no")

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
rootList = [-1] * n

def getRoot(x):
    if rootList[x] < 0:
        return x
    rootList[x] = getRoot(rootList[x])
    return rootList[x]

def setSameRoot(x, y):
    x = getRoot(x)
    y = getRoot(y)
    if x != y:
        G[x], G[y] = min(x, y), min(x, y)

for i in range(m):
    s, t = map(int, input().split())
    setSameRoot(s, t)
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    print("yes" if getRoot(s) == getRoot(t) != -1 else "no")

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
rootList = [-1] * n

def getRoot(x):
    if rootList[x] < 0:
        return x
    return getRoot(rootList[x])


def setSameRoot(x, y):
    x = getRoot(x)
    y = getRoot(y)
    if x != y:
        G[x], G[y] = min(x, y), min(x, y)

for i in range(m):
    s, t = map(int, input().split())
    setSameRoot(s, t)
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    print("yes" if getRoot(s) == getRoot(t) else "no")

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
rootList = [-1] * n
 
def getRoot(x):
    if rootList[x] < 0:
        rootList[x] = x
        return x
    return getRoot(rootList[x])
 
 
def setSameRoot(x, y):
    x = getRoot(x)
    y = getRoot(y)
    if x != y:
        rootList[x], rootList[y] = min(x, y), min(x, y)
 
for i in range(m):
    s, t = map(int, input().split())
    setSameRoot(s, t)
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    print("yes" if getRoot(s) == getRoot(t) else "no")

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
rootList = [-1] * n
 
def getRoot(x):
    if rootList[x] < 0:
        rootList[x] = x
        return x
    return getRoot(rootList[x])
 
 
def setSameRoot(x, y):
    x = getRoot(x)
    y = getRoot(y)
    if x != y:
        rootList[x], rootList[y] = min(x, y), min(x, y)
 
for i in range(m):
    s, t = map(int, input().split())
    setSameRoot(s, t)
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    print("yes" if getRoot(s) == getRoot(t) != -1 else "no")

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
rootList = [-1 for i in range(n)]
 
def getRoot(x):
    if rootList[x] < 0:
        rootList[x] = x
        return x
    return getRoot(rootList[x])
 
 
def setSameRoot(x, y):
    x = getRoot(x)
    y = getRoot(y)
    if x != y:
        rootList[x], rootList[y] = min(x, y), min(x, y)
 
for i in range(m):
    s, t = map(int, input().split())
    setSameRoot(s, t)
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    print("yes" if getRoot(s) == getRoot(t) != -1 else "no")

Submission status: Runtime Error

Solution code:
def dfs(r, c):
    global c, color
    S = [r]
    color[r] = c
    while (0 < len(S)):
        u = S.pop()
        for u in G[u]:
            v = color[ch]
            if (v == False):
                color[u] = c
                S.append(u)
 
def assignColor():
    global c, color
    c = 1
    for i in range(n):
        if (color[i] == False):
            dfs(i, c)
            c += 1
 
n, m = list(map(int, input().split()))
 
G = [False for i in range(n)]
for i in range(m):
    s, t = list(map(int, input().split()))
    G[s].append(t)
    G[t].append(s)
 
color = [False for i in range(n)]
 
assignColor()
 
q = int(input())

for i in range(q):
    s, t = list(map(int, input().split()))
    if (color[s] == color[t]):
        print("yes")
    else:
        print("no")

Submission status: Runtime Error

Solution code:
def dfs(r, c):
    global c, color, G
    S = [r]
    color[r] = c
    while (0 < len(S)):
        u = S.pop()
        for u in G[u]:
            v = color[ch]
            if (v == False):
                color[u] = c
                S.append(u)
 
def assignColor():
    global c, color, G, n
    c = 1
    for i in range(n):
        if (color[i] == False):
            dfs(i, c)
            c += 1
 
n, m = list(map(int, input().split()))
 
G = [False for i in range(n)]
for i in range(m):
    s, t = list(map(int, input().split()))
    G[s].append(t)
    G[t].append(s)
 
color = [False for i in range(n)]
 
assignColor()
 
q = int(input())

for i in range(q):
    s, t = list(map(int, input().split()))
    if (color[s] == color[t]):
        print("yes")
    else:
        print("no")

Submission status: Runtime Error

Solution code:
def dfs(r, c):
    global c, color, G
    S = [r]
    color[r] = c
    while (0 < len(S)):
        u = S.pop()
        for u in G[u]:
            v = color[u]
            if (v == None):
                color[u] = c
                S.append(u)
 
def assignColor():
    global c, color, G, n
    c = 1
    for i in range(n):
        if (color[i] == None):
            dfs(i, c)
            c += 1
 
n, m = list(map(int, input().split()))
 
G = [None for i in range(n)]
for i in range(m):
    s, t = list(map(int, input().split()))
    G[s].append(t)
    G[t].append(s)
 
color = [False for i in range(n)]
 
assignColor()
 
q = int(input())

for i in range(q):
    s, t = list(map(int, input().split()))
    if (color[s] == color[t]):
        print("yes")
    else:
        print("no")

Submission status: Runtime Error

Solution code:
def dfs(r, c):
    global c, color, G
    S = [r]
    color[r] = c
    while (0 < len(S)):
        u = S.pop()
        for u in G[u]:
            v = color[u]
            if (v == None):
                color[u] = c
                S.append(u)
 
def assignColor():
    global color, G, n
    c = 1
    for i in range(n):
        if (color[i] == None):
            dfs(i, c)
            c += 1
 
n, m = list(map(int, input().split()))
 
G = [None for i in range(n)]
for i in range(m):
    s, t = list(map(int, input().split()))
    G[s].append(t)
    G[t].append(s)
 
color = [False for i in range(n)]
 
assignColor()
 
q = int(input())

for i in range(q):
    s, t = list(map(int, input().split()))
    if (color[s] == color[t]):
        print("yes")
    else:
        print("no")

Submission status: Runtime Error

Solution code:
def dfs(r, c):
    global color, G
    S = [r]
    color[r] = c
    while (0 < len(S)):
        u = S.pop()
        for u in G[u]:
            v = color[u]
            if (v == None):
                color[u] = c
                S.append(u)
 
def assignColor():
    global color, G, n
    c = 1
    for i in range(n):
        if (color[i] == None):
            dfs(i, c)
            c += 1
 
n, m = list(map(int, input().split()))
 
G = [None for i in range(n)]
for i in range(m):
    s, t = list(map(int, input().split()))
    G[s].append(t)
    G[t].append(s)
 
color = [False for i in range(n)]
 
assignColor()
 
q = int(input())

for i in range(q):
    s, t = list(map(int, input().split()))
    if (color[s] == color[t]):
        print("yes")
    else:
        print("no")

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from collections import deque


if __name__ == '__main__':

    n, m = [int(s) for s in input().split(" ")]
    M = [set() for j in range(n)]
    for _ in range(m):
        u, v = [int(s) for s in input().split(" ")]
        M[u].add(v)
        M[v].add(u)
        
    color = [0] * n
    def dfs(u, c):  # depth-first search
        color[u] = c
        for v in M[u]:
            if color[v] == 0:
                dfs(v, c)
    
    c = 1
    for u in range(n):
        if color[u] == 0:
            dfs(u, c)
            c += 1
    
    l = int(input())
    for _ in range(l):
        p, q = [int(s) for s in input().split(" ")]
        if color[p] == color[q]:
            print("yes")
        else:
            print("no")

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
import sys
sys.setrecursionlimit(100000)


if __name__ == '__main__':

    n, m = [int(s) for s in input().split(" ")]
    M = [set() for j in range(n)]
    for _ in range(m):
        u, v = [int(s) for s in input().split(" ")]
        M[u].add(v)
        M[v].add(u)
        
    color = [0] * n
    def dfs(u, c):  # depth-first search
        color[u] = c
        for v in M[u]:
            if color[v] == 0:
                dfs(v, c)
    
    c = 1
    for u in range(n):
        if color[u] == 0:
            dfs(u, c)
            c += 1
    
    l = int(input())
    for _ in range(l):
        p, q = [int(s) for s in input().split(" ")]
        if color[p] == color[q]:
            print("yes")
        else:
            print("no")

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline
def MAIN():
    n, m = map(int, input().split())
    li = [i for i in range(n)]
    def f(a):
        if li[a] == a:
            return a
        li[a] = f(li[a])
        return li[a]
    def f2(a, b):
        if li[a] == a:
            li[a] = b
            return
        f2(li[a], b)
        li[a] = b
    for _ in range(m):
        x, y = map(int, readline().split())
        if f(x) > f(y):
            f2(x, li[y])
        elif f(x) < f(y):
            f2(y, li[x])
    for _ in range(int(input())):
        x, y = map(int, readline().split())
		print("yes" if f(a) == f(b) else "no")
MAIN()

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline
def MAIN():
    n, m = map(int, input().split())
    li = [i for i in range(n)]
    def f(a):
        if li[a] == a:
            return a
        li[a] = f(li[a])
        return li[a]
    def f2(a, b):
        if li[a] == a:
            li[a] = b
            return
        f2(li[a], b)
        li[a] = b
    for _ in range(m):
        x, y = map(int, readline().split())
        if f(x) > f(y):
            f2(x, li[y])
        elif f(x) < f(y):
            f2(y, li[x])
    for _ in range(int(input())):
        x, y = map(int, readline().split())
        print("yes" if f(a) == f(b) else "no")
MAIN()

Submission status: Runtime Error

Solution code:
def s():
 e=sys.stdin.readline
 n,m=map(int,e().split())
 P=[[]for _ in[0]*n]
 C=[0]*n
 k=0
 for _ in[0]*m:
  s,t=map(int,e().split());P[s]+=[t];P[t]+=[s]
 for i in range(n):
  k+=1
  if C[i]<1:
   s=[i];C[i]=k
   while s:
    u=s.pop()
    for v in P[u]:
     if C[v]<1:C[v]=k;s+=[v]
 for _ in[0]*int(e()):
  a,b=map(int,e().split())
  print(['no','yes'][C[a]==C[b]])
if'__main__'==__name__:s()

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())

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

for i in range(m):
    com = list(map(int, input().split()))
    a[com[0]].append(com[1])
    a[com[1]].append(com[0])

q = int(input())

from collections import deque
for j in range(q):
    memo = [0 for i in range(n)]
    data = list(map(int, input().split()))
    memo[data[0]] = 1
    queue = deque(data[0])

    try:
        while len(queue):
            b = queue.popleft()
            for k in a[b]:
                if k == data[1]:
                    print("yes")
                    raise Exception
                if memo[k] == 0:
                    memo[k] = 1
                    queue.append(k)
        print("no")
    except Exception:
        pass

Submission status: Runtime Error

Solution code:
from collections import deque
from enum import Enum, auto

class Color(Enum):
    WHITE = auto()
    GRAY = auto()
    BLACK = auto()

n, m = list(map(int, input().split(' ')))
adj_list = [[] for i in range(n)]
for i in range(m):
    u, v = list(map(int, input().split(' ')))
    adj_list[u].append(v)
    adj_list[v].append(u)

# 幅優先
def adj_bfs(s, e):
    queue = deque([])
    colors = [Color.WHITE for i in range(n)]

    queue.append(s)
    colors[s] = Color.GRAY

    while len(queue) > 0:
        u = queue.popleft()
        for v in adj_list[u]:
            if colors[v] == Color.WHITE:
                colors[v] = Color.GRAY
                queue.append(v)
                if v == e: return True
        colors[u] = Color.BLACK
    return False

# 深さ優先
colors = [Color.WHITE for i in range(n)]

def adj_dfs(u, e):
    colors[u] = Color.GRAY

    for v in adj_list[u]:
        if colors[v] == Color.WHITE:
            if v == e: return True
            if adj_dfs(v, e):
                return True

    colors[u] = Color.BLACK
    return False

q = int(input())
for i in range(q):
    s, e = list(map(int, input().split(' ')))
    colors = [Color.WHITE for i in range(n)]
    if adj_dfs(s, e):
        print('yes')
    else:
        print('no')

Submission status: Runtime Error

Solution code:
import sys
input_lines = [[int(i) for i in line.split()] for line in sys.stdin.read().splitlines()]
[user_num, rel_num] = input_lines[0]
rel_list = input_lines[1:rel_num+1]
ques_num = input_lines[rel_num+1][0]
ques_list = input_lines[rel_num+2:]
color_list = [-1] * user_num
adja_list = [set() for i in range(user_num)]

def dfs(id, color):
    if color_list[id] == -1:
        color_list[id] = color
        for a_id in adja_list[id]:
            dfs(a_id, color)



for rel in rel_list:
    adja_list[rel[0]].add(rel[1])
    adja_list[rel[1]].add(rel[0])

color = 0
for id in range(user_num):
    dfs(id, color)
    color += 1

for ques in ques_list:
    if color_list[ques[0]] == color_list[ques[1]]:
        print('yes')
    else:
        print('no')

Submission status: Runtime Error

Solution code:
def dfs(v):
    global node_chk
    global edge_chk
    global B
    global connect
    global value

    node_chk[v] = 1
    connect[v] = value
    for x in B[v]:
        if(node_chk[x] == 0):
                dfs(x)



n,m = map(int,input().split())
B = [[]for i in range(n)] # 隣接リスト
edge_chk = [[]for i in range(n)]
node_chk = [0 for i in range(n)]
connect = [0 for i in range(n)]
value = 0

for i in range(m):
    A = list(map(int,input().split()))
    B[A[0]].append(A[1])
    B[A[1]].append(A[0])
    edge_chk[A[0]].append(0)
    edge_chk[A[1]].append(0)

for i in range(n):
    if(node_chk[i] == 1):
        continue
    dfs(i)
    value += 1


q = int(input())
for i in range(q):
    start,target = map(int,input().split())
    if(connect[start] == connect[target]):
        print("yes")
    else:
        print("no")

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

def dfs(v):
    global node_chk
    global edge_chk
    global B
    global connect
    global value

    node_chk[v] = 1
    connect[v] = value
    for x in B[v]:
        if(node_chk[x] == 0):
                dfs(x)



n,m = map(int,input().split())
B = [[]for i in range(n)] # 隣接リスト
edge_chk = [[]for i in range(n)]
node_chk = [0 for i in range(n)]
connect = [0 for i in range(n)]
value = 0

for i in range(m):
    A = list(map(int,input().split()))
    B[A[0]].append(A[1])
    B[A[1]].append(A[0])
    edge_chk[A[0]].append(0)
    edge_chk[A[1]].append(0)

for i in range(n):
    if(node_chk[i] == 1):
        continue
    dfs(i)
    value += 1


q = int(input())
for i in range(q):
    start,target = map(int,input().split())
    if(connect[start] == connect[target]):
        print("yes")
    else:
        print("no")

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

def dfs(v):
    global node_chk
    global edge_chk
    global B
    global connect
    global value

    node_chk[v] = 1
    connect[v] = value
    for x in B[v]:
        if(node_chk[x] == 0):
                dfs(x)



n,m = map(int,input().split())
B = [[]for i in range(n)] # 隣接リスト
edge_chk = [[]for i in range(n)]
node_chk = [0 for i in range(n)]
connect = [0 for i in range(n)]
value = 0

for i in range(m):
    A = list(map(int,input().split()))
    B[A[0]].append(A[1])
    B[A[1]].append(A[0])
    edge_chk[A[0]].append(0)
    edge_chk[A[1]].append(0)

for i in range(n):
    if(node_chk[i] == 1):
        continue
    dfs(i)
    value += 1


q = int(input())
for i in range(q):
    start,target = map(int,input().split())
    if(connect[start] == connect[target]):
        print("yes")
    else:
        print("no")

Submission status: Runtime Error

Solution code:
def tan(G,st,fi):
    global flag
    for i in range(len(G)):
        if G[st][i] == 1:
            if i == fi:
                flag = 1
            tan(G,i,fi)
    
n,m = list(map(int, input().split()))
G = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
    S = list(map(int, input().split()))
    G[S[0]][S[1]] = 1
    G[S[1]][S[0]] = 1

q = int(input())
ans = []
for i in range(q):
    Q = list(map(int, input().split()))
    if Q[0]<Q[1]:
        st = Q[0]
        fi = Q[1]
    else:
        st = Q[1]
        fi = Q[0]

    flag = 0
    tan(G,st,fi)
    if flag==1:
        ans.append("yes")
    else:
        ans.append("no")
        
for i in range(q):
    print(ans[i])

Submission status: Runtime Error

Solution code:
#coding:utf-8
n, r = map(int,input().split())
Q = []
M = [[] for j in range(n)]
for i in range(r):
    i,j = map(int,input().split())
    M[i].append(j)
    M[j].append(i)


def search(person, target):
    data = M[person]
    for per in data:
        if per ==  target:
            global yes
            yes = 1
            return
        if color[per] == "white":
            color[per] = "gray"
            search(per, target)
    color[person] = "black"

num = int(input())
for i in range(num):
    yes = 0
    color = ["white" for j in range(n)]
    person, target = map(int,input().split())
    search(person, target)
    if yes == 0:
        print("no")
    else:
        print("yes")

Submission status: Runtime Error

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10000)
n, r = map(int,input().split())
Q = []
M = [[] for j in range(n)]
for i in range(r):
    i,j = map(int,input().split())
    M[i].append(j)
    M[j].append(i)


def search(person, target):
    data = M[person]
    for per in data:
        if per ==  target:
            global yes
            yes = 1
            return
        if color[per] == "white":
            color[per] = "gray"
            search(per, target)
    color[person] = "black"

num = int(input())
for i in range(num):
    yes = 0
    color = ["white" for j in range(n)]
    person, target = map(int,input().split())
    search(person, target)
    if yes == 0:
        print("no")
    else:
        print("yes")