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: Wrong Answer

Solution code:
def dfs(s):
    global t
    if s == t:
        return True
    DP[s]=1
    for i in F[s]:
        if not DP[i]:
            if dfs(i):
                return True
    return False
    
n,m = [int(i) for i in input().split()]
F = [{}]*n
for _ in range(m):
    i,j = [int(i) for i in input().split()]
    F[i][j] = 1
q = int(input())
for i in range(q):
    DP = [0]*n
    s,t = [int(i) for i in input().split()]
    if dfs(s):
        print("yes")
    else:
        print("no")

Submission status: Wrong Answer

Solution code:
def dfs(s):
    global t
    if s == t:
        return True
    DP[s]=1
    for i in F[s]:
        if not DP[i]:
            if dfs(i):
                return True
    return False
    
n,m = [int(i) for i in input().split()]
F = [{}]*n
for _ in range(m):
    i,j = [int(i) for i in input().split()]
    F[i][j] = 1
    F[j][i] = 1
q = int(input())
for i in range(q):
    DP = [0]*n
    s,t = [int(i) for i in input().split()]
    if dfs(s):
        print("yes")
    else:
        print("no")

Submission status: Wrong Answer

Solution code:
#coding: utf-8
n, m = map(int,input().split())
List = [[] for i in range(n)]
color = ["white" for i in range(n)]

for i in range(m):
    s,t = map(int,input().split())
    List[s].append(t)


def search(a,target):
    for member in List[a]:
        if member == target:
            print("yes")
            return True
        if color[member] == "white":
            color[member] = "black"
            return search(member, target)

p = int(input())
for i in range(p):
    a, target = map(int,input().split())
    b = search(a, target)
    if b != True:
        print("no")

Submission status: Wrong Answer

Solution code:
#coding: utf-8
n, m = map(int,input().split())
List = [[] for i in range(n)]

for i in range(m):
    s,t = map(int,input().split())
    List[s].append(t)
    List[t].append(s)


def search(a,target):
    if a == target:
        print("yes")
        return True
    for member in List[a]:
        if color[member] == "white":
            color[member] = "black"
            return search(member, target)

p = int(input())
for i in range(p):
    color = ["white" for i in range(n)]
    a, target = map(int,input().split())
    color[a] = "black"
    b = search(a, target)
    if b != True:
        print("no")

Submission status: Wrong Answer

Solution code:
n, m = [int(i) for i in input().split()]
G = [[] for _ in range(n)]
for mi in range(m):
    u, v = [int(i) for i in input().split()]
    G[u].append(v)
    G[u] += G[v]
    G[v].append(u)
    G[v] += G[u]

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
relations = [[] for _ in range(n)]

for i in range(m):
    s, t = map(int, input().split())
    if s > t:
        s, t = t, s
    relations[s] += [t]
friend_id = [None] * n
id = 0
for s, t in enumerate(relations):
    if t:
        queue = [s]
        while len(queue):
            k = queue.pop()
            friend_id[k] = id
            queue += relations[k]
            relations[k] = []
    id += 1

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
relations = [[] for _ in range(n)]

for i in range(m):
    s, t = map(int, input().split())
    if s > t:
        s, t = t, s
    relations[s] += [t]
friend_id = [None] * n
for s, t in enumerate(relations):
    if t:
        queue = [s]
        while len(queue):
            k = queue.pop()
            friend_id[k] = s
            queue += relations[k]
            relations[k] = []

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
relations = [[] for _ in range(n)]

for i in range(m):
    s, t = map(int, input().split())
    if s > t:
        s, t = t, s
    relations[s] += [t]
friend_id = [None] * n
for s, t in enumerate(relations):
    if t:
        queue = [s]
        while len(queue):
            k = queue.pop()
            friend_id[k] = s
            queue += relations[k]
            relations[k] = []

q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    print('yes' if friend_id[s] != None and friend_id[s] == friend_id[t] else'no')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
n, m = map(int, input().split())
ALL = [0] * n
Graph = []
for i in range(m):
    s, t = map(int, input().split())
    if ALL[s] == 0 and ALL[t] == 0:
        Graph.append(set([s, t]))
    elif ALL[s] == 0:
        for g in Graph:
            if t in g:
                g.add(s)
                break
    elif ALL[t] == 0:
        for g in Graph:
            if s in g:
                g.add(t)
                break
    ALL[s] = 1
    ALL[t] = 1

q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    for g in Graph:
        if s in g and t in g:
            print('yes')
            break
    else:
        print('no')

Submission status: Wrong Answer

Solution code:
n, m = map(int, raw_input().split())
G = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
    s, t = map(int, raw_input().split())
    G[s][t] = 1
    G[t][s] = 1

for i in range(n):
    for j in range(n):
        for k in range(n):
            if G[j][k] == 1:
                for l in range(k+1, n):
                    if G[k][l] == 1:
                        G[j][l] = 1

q = int(raw_input())
ans = ["no" for i in range(q)]
for i in range(q):
    s, t = map(int, raw_input().split())
    if G[s][t] == 1:
        ans[i] = "yes"
for i in range(q):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
n, m = map(int, raw_input().split())
G = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
    s, t = map(int, raw_input().split())
    G[s][t] = 1
    G[t][s] = 1

for i in range(n+1):
    for j in range(n):
        for k in range(n):
            if G[j][k] == 1:
                for l in range(k+1, n):
                    if G[k][l] == 1:
                        G[j][l] = 1

q = int(raw_input())
ans = ["no" for i in range(q)]
for i in range(q):
    s, t = map(int, raw_input().split())
    if G[s][t] == 1:
        ans[i] = "yes"
for i in range(q):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
n, m = map(int, raw_input().split())
G = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
    s, t = map(int, raw_input().split())
    G[s][t] = 1
    G[t][s] = 1

for i in range(n):
    for j in range(n):
        for k in range(n):
            if G[j][k] == 1:
                for l in range(k+1, n):
                    if G[k][l] == 1:
                        G[j][l] = 1
                        G[l][j] = 1

q = int(raw_input())
ans = ["no" for i in range(q)]
for i in range(q):
    s, t = map(int, raw_input().split())
    if G[s][t] == 1:
        ans[i] = "yes"
for i in range(q):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
n, m = map(int, raw_input().split())
G = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
    s, t = map(int, raw_input().split())
    G[s][t] = 1
    G[t][s] = 1

for i in range(n):
    for j in range(n):
        for k in range(j+1, n):
            if G[j][k] == 1:
                for l in range(n):
                    if G[k][l] == 1:
                        G[j][l] = 1
                        G[l][j] = 1

q = int(raw_input())
ans = ["no" for i in range(q)]
for i in range(q):
    s, t = map(int, raw_input().split())
    if G[s][t] == 1:
        ans[i] = "yes"
for i in range(q):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
n, m = map(int, raw_input().split())
G = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
    s, t = map(int, raw_input().split())
    G[s][t] = 1
    G[t][s] = 1

for i in range(2*n):
    for j in range(n):
        for k in range(j+1, n):
            if G[j][k] == 1:
                for l in range(k+1, n):
                    if G[k][l] == 1:
                        G[j][l] = 1
                        G[l][j] = 1

q = int(raw_input())
ans = ["no" for i in range(q)]
for i in range(q):
    s, t = map(int, raw_input().split())
    if G[s][t] == 1:
        ans[i] = "yes"
for i in range(q):
    print(ans[i])

Submission status: Wrong Answer

Solution code:

def BFS(s = 0, group_num = 0):
    Q.pop(0)
    color[s] = 2
    for j in range(len(A[s])):
        if color[A[s][j]] == 0:
            Q.append(A[s][j])
            color[A[s][j]] = 1
            affil[A[s][j]] = group_num
    if len(Q) != 0:
        BFS(Q[0], group_num)

n = 10
m = 9
friends = [[0, 1], [0, 2], [3, 4], [5, 7], [5, 6], [6, 7], [6, 8], [7, 8], [8, 9]]

A = [0] * n
for i in range(n):
    A[i] = list((-1, -1))
for i in range(m):
    entry = friends[i]
    s = entry[0]
    t = entry[1]
    A[s].append(t)
    A[t].append(s)

color = [0] * n
affil = [0] * n
group_num = -1
for i in range(n):
    if color[i] == 0:
        Q = [i]
        group_num = group_num + 1
        affil[i] = group_num
        BFS(i, group_num)

q = 3
quest = [[0, 1], [5, 9], [1, 3]]
for i in range(q):
    entry = quest[i]
    if affil[entry[0]] == affil[entry[1]]:
        print("yes")
    else:
        print("no")

Submission status: Wrong Answer

Solution code:

def BFS(s = 0, group_num = 0):
    Q.pop(0)
    color[s] = 2
    for j in range(len(A[s])):
        if color[A[s][j]] == 0:
            Q.append(A[s][j])
            color[A[s][j]] = 1
            affil[A[s][j]] = group_num
    if len(Q) != 0:
        BFS(Q[0], group_num)

n = 10
m = 9
friends = [[0, 1], [0, 2], [3, 4], [5, 7], [5, 6], [6, 7], [6, 8], [7, 8], [8, 9]]

A = [0] * n
for i in range(n):
    A[i] = list()
for i in range(m):
    entry = friends[i]
    s = entry[0]
    t = entry[1]
    A[s].append(t)
    A[t].append(s)

color = [0] * n
affil = [0] * n
group_num = -1
for i in range(n):
    if color[i] == 0:
        Q = [i]
        group_num = group_num + 1
        affil[i] = group_num
        BFS(i, group_num)

q = 3
quest = [[0, 1], [5, 9], [1, 3]]
for i in range(q):
    entry = quest[i]
    if affil[entry[0]] == affil[entry[1]]:
        print("yes")
    else:
        print("no")

Submission status: Wrong Answer

Solution code:

def BFS(s = 0, group_num = 0):
    Q.pop(0)
    color[s] = 2
    for j in range(len(A[s])):
        if color[A[s][j]] == 0:
            Q.append(A[s][j])
            color[A[s][j]] = 1
            affil[A[s][j]] = group_num
    if len(Q) != 0:
        BFS(Q[0], group_num)

n = 10
m = 9
friends = [[0, 1], [0, 2], [3, 4], [5, 7], [5, 6], [6, 7], [6, 8], [7, 8], [8, 9]]

A = range(n)
for i in A:
    A[i] = list()
for i in range(m):
    entry = friends[i]
    s = entry[0]
    t = entry[1]
    A[s].append(t)
    A[t].append(s)

color = [0] * n
affil = [0] * n
group_num = -1
for i in range(n):
    if color[i] == 0:
        Q = [i]
        group_num = group_num + 1
        affil[i] = group_num
        BFS(i, group_num)

q = 3
quest = [[0, 1], [5, 9], [1, 3]]
for i in range(q):
    entry = quest[i]
    if affil[entry[0]] == affil[entry[1]]:
        print("yes")
    else:
        print("no")

Submission status: Wrong Answer

Solution code:
from collections import deque

n, m = map(int, input().split())
g = [set() for _ in range(n)]
gids = [0] * n

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def search(s, gid):
    global g, gids
    queue = deque()
    queue.append(s)
    visited = [0] * n
    visited[s] = 1
    gids[s] = gid

    while queue:
        i = queue.popleft()
        for f in g[i]:
            if not visited[f]:
                visited[f] = 1
                gids[f] = gid
                queue.append(f)


gid = 1
for i in range(n):
    if gids[i]:
        continue
    search(i, gid)
    gid += 1

print(gids)

q = int(input())
while q:
    s, t = map(int, input().split())
    print('yes' if gids[s] == gids[t] else 'no')
    q -= 1

Submission status: Wrong Answer

Solution code:
from collections import deque

n, m = map(int, input().split())
g = [set() for _ in range(n)]
gids = [0] * n

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def search(s, gid):
    global g, gids
    queue = deque()
    queue.append(s)
    visited = [0] * n
    visited[s] = 1
    gids[s] = gid

    while queue:
        i = queue.popleft()
        for f in g[i]:
            if not visited[f]:
                visited[f] = 1
                gids[f] = gid
                queue.append(f)


gid = 1
for i in range(n):
    if gids[i]:
        continue
    search(i, gid)
    gid += 1

print(gids)

q = int(input())
while q:
    s, t = map(int, input().split())
    gs, gt = gids[s], gids[t]
    print('yes' if gs and gt and gs == gt else 'no')
    q -= 1

Submission status: Wrong Answer

Solution code:
def DFS(s):
    flag[s] = 1
    group[s] = j
    for i in range(n):
        if G[s][i] == 1 and flag[i] == 0:
            DFS(i)

n, m = map(int, raw_input().split())
G = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
    s, t = map(int, raw_input().split())
    G[s][t] = 1
    G[t][s] = 1

group = [[] for i in range(n)]
flag = [0 for i in range(n)]
j = 0
for i in range(n):
    if flag[i] == 0:
        DFS(i)
        j += 1

q = int(raw_input())
ans = ["no" for i in range(q)]
for i in range(q):
    s, t = map(int, raw_input().split())
    if group[s] == group[t]:
        ans[i] = "yes"
for i in range(q):
    print(ans[i])

print(group)

Submission status: Wrong Answer

Solution code:
x,y = map(int,raw_input().strip().split(' '))
follow = [[] for i in range(x)]
for i in range(y):
    h,c = map(int,raw_input().strip().split(' '))
    follow[h].append(c)
    follow[c].append(h)
 
color = {}
u = 0

for i in range(x):
    if not i in color:
        que = [i]
        color[i] = u
        while len(que) > 0:
            u = que[0]
            for v in follow[u]:
                if not v in color:
                    color[v] = u
                    que.append(v)
            del que[0]
        u += 1
 
 
q = int(raw_input())
for i in range(q):
    h,c = map(int,raw_input().strip().split(' '))
    if color[h] == color[c]:
        print 'yes'
    else:
        print 'no'

Submission status: Wrong Answer

Solution code:
n,m = map(int,raw_input().strip().split(' '))
graph = [[] for i in range(n)]
for i in range(m):
    s,t = map(int,raw_input().strip().split(' '))
    graph[s].append(t)
    graph[t].append(s)
 
color = {}
c = 0
for i in range(n):
    if not i in color:
        que = [i]
        color[i] = c
        if len(que) > 0:
         for j in range (len(que)):
            u = que[0]
            for v in graph[u]:
                if not v in color:
                    color[v] = c
                    que.append(v)
            del que[0]
        c += 1

Submission status: Wrong Answer

Solution code:
n,m = map(int,raw_input().strip().split(' '))
graph = [[] for i in range(n)]
for i in range(m):
    s,t = map(int,raw_input().strip().split(' '))
    graph[s].append(t)
    graph[t].append(s)
 
color = {}
c = 0
for i in range(n):
    if not i in color:
        que = [i]
        color[i] = c
        if len(que) > 0:
         for j in range(len(que)):
            u = que[0]
            for v in graph[u]:
                if not v in color:
                    color[v] = c
                    que.append(v)
            del que[0]
        c += 1

Submission status: Wrong Answer

Solution code:
n,m = map(int,raw_input().strip().split(' '))
graph = [[] for i in range(n)]
for i in range(m):
    s,t = map(int,raw_input().strip().split(' '))
    graph[s].append(t)
    graph[t].append(s)
 
color = {}
c = 0
for i in range(n):
    if not i in color:
        que = [i]
        color[i] = c
        if len(que) > 0:
       #  for j in range(len(que)):
            u = que[0]
            for v in graph[u]:
                if not v in color:
                    color[v] = c
                    que.append(v)
            del que[0]
        c += 1

Submission status: Wrong Answer

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

M = [[0 for j in xrange(n)] for i in xrange(n)]

color = ["WHITE" for i in xrange(n)]

for i in xrange(m):
    tmp1, tmp2 = map(int, raw_input().split())
    M[tmp1][tmp2] = 1

def dfs(u):
    color[u] = 'GRAY'
    for v in xrange(n):
        if M[u][v] == 1 and color[v] == 'WHITE':
            dfs(v)
    color[u] = 'BLACK'

q = input()
for i in xrange(q):
    s, t = map(int, raw_input().split())
    for j in xrange(n):
        color[j] = "WHITE"
    dfs(s)
    if color[t] == "BLACK" or color[t] == "GRAY":
        print "yes"
    else:
        print "no"

Submission status: Wrong Answer

Solution code:
n,m = map(int,raw_input().strip().split(' '))
graph = [[] for i in range(n)]
for i in range(m):
    s,t = map(int,raw_input().strip().split(' '))
    graph[s].append(t)
    graph[t].append(s)
 
color = {}
c = 0
for i in range(n):
    if not i in color:
        que = [i]
        color[i] = c
        if len(que) > 0:
        #while len(que) > 0:
            u = que[0]
            for v in graph[u]:
                if not v in color:
                    color[v] = c
                    que.append(v)
            del que[0]
        c += 1
 
 
q = int(raw_input())
for i in range(q):
    s,t = map(int,raw_input().strip().split(' '))
    if color[s] == color[t]:
        print 'yes'
    else:
        print 'no'

Submission status: Wrong Answer

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

M = [[0 for j in xrange(n)] for i in xrange(n)]

color = ["WHITE" for i in xrange(n)]

for i in xrange(m):
    tmp1, tmp2 = map(int, raw_input().split())
    M[tmp1][tmp2] = 1

def dfs(u):
    color[u] = 'GRAY'
    for v in xrange(n):
        if M[u][v] == 1 and color[v] == 'WHITE':
            dfs(v)
    color[u] = 'BLACK'

q = input()
for i in xrange(q):
    s, t = map(int, raw_input().split())
    for j in xrange(n):
        color[j] = "WHITE"
    dfs(s)
    if color[t] == "WHITE":
        print "no"
    else:
        print "yes"

Submission status: Wrong Answer

Solution code:
n,m = map(int,raw_input().strip().split(' '))
graph = [[] for i in range(n)]
for i in range(m):
    s,t = map(int,raw_input().strip().split(' '))
    graph[s].append(t)
    graph[t].append(s)
color = {}
c = 0
for i in range(n):
    if not i in color:
        que = [i]
        color[i] = c
        if len(que) > 0:
         for j in range(len(que)):
          if len(que) > 0:
        #while len(que) > 0:
            u = que[0]
            for v in graph[u]:
                if not v in color:
                    color[v] = c
                    que.append(v)
            del que[0]
        c += 1
q = int(raw_input())
for i in range(q):
    s,t = map(int,raw_input().strip().split(' '))
    if color[s] == color[t]:
        print 'yes'
    else:
        print 'no'

Submission status: Wrong Answer

Solution code:
n,m = map(int,raw_input().strip().split(' '))
graph = [[] for i in range(n)]
for i in range(m):
    s,t = map(int,raw_input().strip().split(' '))
    graph[s].append(t)
    graph[t].append(s)
color = {}
c = 0
for i in range(n):
    if not i in color:
        que = [i]
        color[i] = c
        #if len(que) > 0:
        for j in range(len(que)):
          if len(que) > 0:
        #while len(que) > 0:
            u = que[0]
            for v in graph[u]:
                if not v in color:
                    color[v] = c
                    que.append(v)
            del que[0]
        c += 1
q = int(raw_input())
for i in range(q):
    s,t = map(int,raw_input().strip().split(' '))
    if color[s] == color[t]:
        print 'yes'
    else:
        print 'no'

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
G = [[] for j in range(n)]
for i in range(m):
    s, t = map(int, input().split())
    G[s].append(t)
    G[t].append(s)

group = {}
c = 0
for i in range(n):
    if not i in group:
        que = [i]
        group[i] = c
        while len(que) > 0:
            u = que[0]
            for j in G[u]:
                if not j in group:
                    group[j] = que.append(j)
            del que[0]
        c += 1

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

Submission status: Wrong Answer

Solution code:
n,m = map(int,raw_input().strip().split(' '))
graph = [[] for i in range(n)]
for i in range(m):
    s,t = map(int,raw_input().strip().split(' '))
    graph[s].append(t)
    graph[t].append(s)
color = {}
c = 0
for i in range(n):
    if not i in color:
        que = [i]
        color[i] = c
        if len(que) > 0:
            u = que[0]
            for v in graph[u]:
                if not v in color:
                    color[v] = c
                    que.append(v)
            del que[0]
        c += 1
q = int(raw_input())
for i in range(q):
    s,t = map(int,raw_input().strip().split(' '))
    if color[s] == color[t]:
        print 'yes'
    else:
        print 'no'

Submission status: Wrong Answer

Solution code:
def connect(o,s,t):
    global ct
    if color[s]!="white" or ct==1:
        return
    if fr[o][t]==t:
        ct+=1
    color[s]="grey"
    for i in fr[s]:
        if i==-1:
            continue
        elif i==t or ct==1:
             ct+=1
             break
        else:
            fr[o][i]=i
            fr[i][o]=s
            connect(o,i,t)
            
n,m=map(int,raw_input().split())
fr=[[-1]*n for i in xrange(n)]
for i in xrange(m):
    s,t=map(int,raw_input().split())
    fr[s][t]=t
    fr[t][s]=s
q=input()
for i in xrange(q):
    ct=0
    color=["white"]*n
    s,t=map(int,raw_input().split())
    connect(s,s,t)
    if ct==0:
        print('no')
    else:
        print('yes')
        fr[s][t]=t
        fr[t][s]=s

Submission status: Wrong Answer

Solution code:
def connect(o,s,t):
    global ct
    if color[s]!="white" or ct!=1:
        return
    if fr[o][t]==t:
        ct+=1
    color[s]="grey"
    for i in fr[s]:
        if i==-1:
            continue
        elif i==t or ct!=0:
             ct+=1
             break
        else:
            fr[o][i]=i
            fr[i][o]=s
            connect(o,i,t)
            
n,m=map(int,raw_input().split())
fr=[[-1]*n for i in xrange(n)]
for i in xrange(m):
    s,t=map(int,raw_input().split())
    fr[s][t]=t
    fr[t][s]=s
q=input()
for i in xrange(q):
    ct=0
    color=["white"]*n
    s,t=map(int,raw_input().split())
    connect(s,s,t)
    if ct==0:
        print('no')
    else:
        print('yes')
        fr[s][t]=t
        fr[t][s]=s

Submission status: Wrong Answer

Solution code:
def connect(o,s,t):
    global ct
    if color[s]!="white" or ct!=0:
        return
    if fr[o][t]==t:
        ct+=1
    color[s]="grey"
    for i in fr[s]:
        if i==-1:
            continue
        elif i==t or ct!=0:
             ct+=1
             break
        else:
            fr[o][i]=i
            fr[i][o]=s
            connect(o,i,t)
            
n,m=map(int,raw_input().split())
fr=[[-1]*n for i in xrange(n)]
for i in xrange(m):
    s,t=map(int,raw_input().split())
    fr[s][t]=t
    fr[t][s]=s
q=input()
for i in xrange(q):
    ct=0
    color=["white"]*n
    s,t=map(int,raw_input().split())
    connect(s,s,t)
    if ct==0:
        print('no')
    else:
        print('yes')
        fr[s][t]=t
        fr[t][s]=s

Submission status: Wrong Answer

Solution code:
def dfs(u):
    global ct
    if color[u]!=-1:
        return
    color[u]=ct
    for v in fr[u]:
        if v!=-1 and color[v]==-1:
            dfs(v)
    color[u]=ct
    
n,m=map(int,raw_input().split())
fr=[[] for i in xrange(n)]
if m==0:
    q=input()
    for i in xrange(q):
        s,t=map(int,raw_input().split())
    print('no')
else:
    for i in xrange(m):
        s,t=map(int,raw_input().split())
        fr[s].append(t)
        fr[t].append(s)

    q=input()
    ct=0
    color=[-1]*n
    for i in xrange(n):
        dfs(i)
        ct+=1
    for i in xrange(q):
        s,t=map(int,raw_input().split())
        if color[s]==color[t]:
            print('yes')
        else:
            print('no')

Submission status: Wrong Answer

Solution code:
from queue import deque

n, m = map(int, input().split())
color = [-1 for i in range(n)]
G = deque([[0] * n for i in range(n)])
for i in range(m):
    s, t = map(int, input().split())
    G[s][t] = 1
    G[t][s] = 1

def dfs(r, c):
    S = deque([r])
    color[r] = c
    while (len(S)):
        u = S.popleft()
        for i in [j for j in range(0, m) if G[u][j] == 1]:
            if color[i] == -1:
                color[i] = c
                S.append(i) # ???????????£?????????????????????????????¢???

def assginColor():
    i_d = 1
    for u in range(n):
        if color[u] == -1:
            dfs(u, i_d)
            i_d += 1

assginColor()
q = int(input())

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

Submission status: Wrong Answer

Solution code:
def cover(V, i):
	for j in range(i + 1, len(V)):
		if V[i] & V[j]:
			V.append(V[i] | V[j])
			del V[j], V[i]
			return True

n, m = map(int, raw_input().split())
V = []
for _ in range(m):
	v = set(map(int, raw_input().split()))
	V.append(v)

flag = True
while flag:
	flag = False
	for i in range(len(V)):
		if cover(V, i):
			print V
			flag = True
			break
		
q = int(raw_input())
for _ in range(q):
	s, t = map(int, raw_input().split())
	for v in V:
		if s in v:
			if t in v:
				print "yes"
			else:
				print "no"
		elif t in v:
			if s in v:
				print "yes"
			else:
				print "no"

Submission status: Wrong Answer

Solution code:
def cover(V, i):
	for j in range(i + 1, len(V)):
		if V[i] & V[j]:
			V.append(V[i] | V[j])
			del V[j], V[i]
			return True

n, m = map(int, raw_input().split())
V = []
for _ in range(m):
	v = set(map(int, raw_input().split()))
	V.append(v)

flag = True
while flag:
	flag = False
	for i in range(len(V)):
		if cover(V, i):
			flag = True
			break
		
q = int(raw_input())
for _ in range(q):
	s, t = map(int, raw_input().split())
	for v in V:
		if s in v:
			if t in v:
				print "yes"
			else:
				print "no"
		elif t in v:
			if s in v:
				print "yes"
			else:
				print "no"

Submission status: Wrong Answer

Solution code:
def cover(V, i):
	for j in range(i + 1, len(V)):
		if V[i] & V[j]:
			V.append(V[i] | V[j])
			del V[j], V[i]
			return True

n, m = map(int, raw_input().split())
V = []
for _ in range(m):
	v = set(map(int, raw_input().split()))
	V.append(v)

flag = True
while flag:
	flag = False
	for i in range(len(V)):
		if cover(V, i):
			flag = True
			break
		
q = int(raw_input())
for _ in range(q):
	s, t = map(int, raw_input().split())
	for v in V:
		if s in v:
			if t in v:
				print "yes"
			else:
				print "no"
			break
		elif t in v:
			if s in v:
				print "yes"
			else:
				print "no"
			break

Submission status: Wrong Answer

Solution code:
def cover(V, i):
    for j in range(i + 1, len(V)):
        if V[i] & V[j]:
            V.append(V[i] | V[j])
            del V[j], V[i]
            return True

n, m = map(int, raw_input().split())
V = []
for _ in range(m):
    v = set(map(int, raw_input().split()))
    V.append(v)

flag = True
while flag:
    flag = False
    for i in range(len(V)):
        if cover(V, i):
            flag = True
            break

q = int(raw_input())
for _ in range(q):
    s, t = map(int, raw_input().split())
    for v in V:
        if s in v:
            if t in v:
                print "yes"
            else:
                print "no"
            break

Submission status: Wrong Answer

Solution code:
def connected(G,s,t):
    checked = [False]*len(G)
    def main(G,s,t):
        if t in G[s]: return True
        checked[s] = True
        for f in G[s]:
            if checked[f]: continue
            if main(G,f,t): return True
        return False
    return main(G,s,t)


if __name__=='__main__':
    n,m = list(map(int,input().split()))
    G = [[] for _ in range(n)]
    for _ in range(m):
        s,t = list(map(int,input().split()))
        G[s].append(t)
        G[t].append(s)
    q = int(input())
    for _ in range(q):
        s,t = list(map(int,input().split()))
        print('Yes' if connected(G,s,t) else 'No')

Submission status: Wrong Answer

Solution code:
un,ln=map(int,raw_input().split())

dic = {}
memo = {}
for x in xrange(un):
    dic[x] = set([])
    memo[x] = {}


for _ in xrange(ln):
    s,t=map(int,raw_input().split())
    dic[s].add(t)
    dic[t].add(s)

n = input()

def func(src, tgt, ignore=[]):
    
    if tgt in dic[src]:
        return True

    if tgt in memo[src].keys():
        return memo[src][tgt]

    for new_src in dic[src]:
        if new_src in ignore:
            continue
        if func(new_src, tgt, ignore+[src]):

            if new_src in memo[new_src].keys():
                memo[new_src].append({tgt:True})
            else:
                memo[new_src]={tgt:True}

            return True
        else:
            if new_src in memo[new_src].keys():
                memo[new_src].append({tgt:False})
            else:
                memo[new_src]={tgt:False}
    return False

for _ in xrange(n):
    s,t=map(int,raw_input().split())
    print "yes" if func(s,t,[]) else "no"

Submission status: Wrong Answer

Solution code:
#coding:utf-8

def CC(root,dist):
    Flag=False
    if len(dist)!=0:
        for i in range(len(dist)):
            if dist[i][-1]==root[0]:
                d=dist[i]
                d=d+[root[1]]
                dist.append(d)
                Flag=True
    if Flag==False:
        dist.append(root)

def Check(dist,qList):
    for i in range(len(dist)):
        if qList[0] in dist[i] and qList[1] in dist[i]:
            return "yes"
    return "no"
    
if __name__=="__main__":
    I=input()
    n=int(I.split(" ")[0])
    m=int(I.split(" ")[1])
    A=[]
    for i in range(m):
        A.append(list(map(int,input().split(" "))))
    dist=[]
    for i in range(m):
        CC(A[i],dist)
    q=int(input())
    for i in range(q):
        print(Check(dist,list(map(int,input().split(" ")))))