Problem:


Score : 300 points

Problem Statement

You are given an undirected connected graph with N vertices and M edges that does not contain self-loops and double edges.

The i-th edge (1 \leq i \leq M) connects Vertex a_i and Vertex b_i.  

An edge whose removal disconnects the graph is called a bridge.

Find the number of the edges that are bridges among the M edges.  

Notes

A self-loop is an edge i such that a_i=b_i (1 \leq i \leq M).

Double edges are a pair of edges i,j such that a_i=a_j and b_i=b_j (1 \leq i<j \leq M).

An undirected graph is said to be connected when there exists a path between every pair of vertices.

Constraints

2 \leq N \leq 50

N-1 \leq M \leq min(N(N−1)⁄2,50)

1 \leq a_i<b_i \leq N

The given graph does not contain self-loops and double edges.

The given graph is connected.

Input

Input is given from Standard Input in the following format:  

N M  
a_1 b_1  
a_2 b_2
:  
a_M b_M

Output

Print the number of the edges that are bridges among the M edges.

Sample Input 1

7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7

Sample Output 1

4

The figure below shows the given graph:

The edges shown in red are bridges. There are four of them.

Sample Input 2

3 3
1 2
1 3
2 3

Sample Output 2

0

It is possible that there is no bridge.

Sample Input 3

6 5
1 2
2 3
3 4
4 5
5 6

Sample Output 3

5

It is possible that every edge is a bridge.



Sample input:
7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7


Sample output:
4

Submission status: Wrong Answer

Solution code:
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.ranks = [0] * n
        self.count = n

    def union(self, x, y):
        self.link(x, y)

    def link(self, x, y):
        x_root = self.parents[x]
        y_root = self.parents[y]
        if x_root == y_root:
            return

        if self.ranks[x] > self.ranks[y]:
            self.parents[y] = x_root
        else:
            self.parents[x] = y_root
            if self.ranks[x] == self.ranks[y]:
                self.ranks[y] += 1
        self.count -= 1

    def find(self, x):
        if self.parents[x] != x:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

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

bridges = []
for i in range(M):
    a, b = list(map(int, input().split()))
    # bridges.append(a, b)
    bridges.append([a-1, b-1])


count = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if j == i:
            continue
        else:
            x, y = bridges[j]
            uf.union(x, y)
    if uf.count > 1:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.ranks = [0] * n
        self.count = n

    def union(self, x, y):
        self.link(x,y)

    def link(self, x, y):
        x_root = self.parents[x]
        y_root = self.parents[y]
        if x_root == y_root:
            return
        # if self.parents[x] == self.parents[y]:
        #     return
        if self.ranks[x] < self.ranks[y]:
            self.parents[x] = y_root
        else:
            if self.ranks[y] == self.ranks[x]:
                self.ranks[y] += 1
            self.parents[y] = x_root
        # print('linked')
        self.count -= 1

    def find(self, x):
        if self.parents[x] != x:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

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

bridges = []
for i in range(M):
    a, b = list(map(int, input().split()))
    # bridges.append(a, b)
    bridges.append([a-1, b-1])


count = 0
for i in range(M):
    # print(i, 'th ------')
    uf = UnionFind(N)
    for j in range(M):
        if j == i:
            continue
        else:
            x, y = bridges[j]
            uf.union(x, y)
            # print('  union',x-1,y-1, 'count',uf.count, uf.parents)
            # print('  union',x,y, 'count',uf.count, uf.parents)
    if uf.count > 1:
        count += 1
print(count)

# for x, y in bridges:
#     uf.union(x-1, y-1)
#     result.append(uf.get_group_num())

# print(result[::-1])

Submission status: Wrong Answer

Solution code:
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.ranks = [0] * n
        self.count = n

    def union(self, x, y):
        self.link(x,y)

    def link(self, x, y):
        x_root = self.parents[x]
        y_root = self.parents[y]
        if x_root == y_root:
            return
        # if self.parents[x] == self.parents[y]:
        #     return
        if self.ranks[x] < self.ranks[y]:
            self.parents[x] = y_root
        else:
            if self.ranks[y] == self.ranks[x]:
                self.ranks[y] += 1
            self.parents[y] = x_root
        # print('linked')
        self.count -= 1

    def find(self, x):
        if self.parents[x] != x:
            return self.find(self.parents[x])
        else:
            return self.parents[x]

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

bridges = []
for i in range(M):
    a, b = list(map(int, input().split()))
    # bridges.append(a, b)
    bridges.append([a-1, b-1])


count = 0
for i in range(M):
    # print(i, 'th ------')
    uf = UnionFind(N)
    for j in range(M):
        if j == i:
            continue
        else:
            x, y = bridges[j]
            uf.union(x, y)
            # print('  union',x-1,y-1, 'count',uf.count, uf.parents)
            # print('  union',x,y, 'count',uf.count, uf.parents)
    if uf.count > 1:
        count += 1
print(count)

# for x, y in bridges:
#     uf.union(x-1, y-1)
#     result.append(uf.get_group_num())

# print(result[::-1])

Submission status: Wrong Answer

Solution code:
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.ranks = [0] * n
        self.count = n

    def union(self, x, y):
        self.link(x,y)

    def link(self, x, y):
        if self.parents[x] == self.parents[y]:
            return
        if self.ranks[x] < self.ranks[y]:
            self.parents[x] = y
        else:
            if self.ranks[y] == self.ranks[x]:
                self.ranks[y] += 1
            self.parents[y] = x
        # print('linked')
        self.count -= 1

    def find(self, x):
        if self.parents[x] != x:
            return self.find(self.parents[x])
        else:
            return self.parents[x]

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

bridges = []
for i in range(M):
    a, b = list(map(int, input().split()))
    # bridges.append(a, b)
    bridges.append([a-1, b-1])


count = 0
for i in range(M):
    # print(i, 'th ------')
    uf = UnionFind(N)
    for j in range(M):
        if j == i:
            continue
        else:
            x, y = bridges[j]
            uf.union(x, y)
            # print('  union',x-1,y-1, 'count',uf.count, uf.parents)
            # print('  union',x,y, 'count',uf.count, uf.parents)
    if uf.count > 1:
        count += 1
print(count)

# for x, y in bridges:
#     uf.union(x-1, y-1)
#     result.append(uf.get_group_num())

# print(result[::-1])

Submission status: Wrong Answer

Solution code:
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.ranks = [0] * n
        self.count = n

    def union(self, x, y):
        self.link(x,y)

    def link(self, x, y):
        if self.parents[x] == self.parents[y]:
            return
        if self.ranks[x] < self.ranks[y]:
            self.parents[x] = y
        else:
            if self.ranks[y] == self.ranks[x]:
                self.ranks[y] += 1
            self.parents[y] = x
        # print('linked')
        self.count -= 1

    def find(self, x):
        if self.parents[x] != x:
            return self.find(self.parents[x])
        else:
            return self.parents[x]

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

bridges = []
for i in range(M):
    bridges.append(list(map(int, input().split())))


# bridges = bridges[::-1]
# result = []
# print('-----')
count = 0
for i in range(M):
    # print(i, 'th ------')
    uf = UnionFind(N)
    for j in range(M):
        x, y = bridges[j]
        if j == i:
            # print('  skip',x-1,y-1, 'count',uf.count, uf.parents)
            # print('  skip',x,y, 'count',uf.count, uf.parents)
            continue
        else:
            uf.union(x-1, y-1)
            # print('  union',x-1,y-1, 'count',uf.count, uf.parents)
            # print('  union',x,y, 'count',uf.count, uf.parents)
    # print(i, uf.count)
    if uf.count > 1:
        count += 1


# for x, y in bridges:
#     uf.union(x-1, y-1)
#     result.append(uf.get_group_num())

# print(result[::-1])

print(count)

Submission status: Wrong Answer

Solution code:
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.ranks = [0] * n
        self.count = n

    def union(self, x, y):
        self.link(x,y)

    def link(self, x, y):
        if self.parents[x] == self.parents[y]:
            return
        if self.ranks[x] < self.ranks[y]:
            self.parents[x] = y
        else:
            if self.ranks[y] == self.ranks[x]:
                self.ranks[y] += 1
            self.parents[y] = x
        # print('linked')
        self.count -= 1

    def find(self, x):
        if self.parents[x] != x:
            return self.find(self.parents[x])
        else:
            return self.parents[x]

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

bridges = []
for i in range(M):
    bridges.append(list(map(int, input().split())))


# bridges = bridges[::-1]
# result = []
# print('-----')
count = 0
for i in range(M):
    # print(i, 'th ------')
    uf = UnionFind(N)
    for j in range(M):
        x, y = bridges[j]
        if j == i:
            # print('  skip',x-1,y-1, 'count',uf.count, uf.parents)
            continue
        else:
            uf.union(x-1, y-1)
            # print('  union',x-1,y-1, 'count',uf.count, uf.parents)
    # print(i, uf.count)
    if uf.count > 1:
        count += 1


# for x, y in bridges:
#     uf.union(x-1, y-1)
#     result.append(uf.get_group_num())

# print(result[::-1])

print(count)

Submission status: Wrong Answer

Solution code:
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.ranks = [0] * n
        self.count = n

    def union(self, x, y):
        self.link(x,y)

    def link(self, x, y):
        if self.parents[x] == self.parents[y]:
            return
        if self.ranks[x] < self.ranks[y]:
            self.parents[x] = y
        else:
            if self.ranks[y] == self.ranks[x]:
                self.ranks[y] += 1
            self.parents[y] = x
        self.count -= 1

    def find(self, x):
        if self.parents[x] != x:
            return self.find(self.parents[x])
        else:
            return self.parents[x]

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

bridges = []
for i in range(M):
    bridges.append(list(map(int, input().split())))


# bridges = bridges[::-1]
# result = []
count = 0
for i in range(M):
    # print(i, 'th ------')
    uf = UnionFind(N)
    for j in range(M):
        x, y = bridges[j]
        if j == i:
            continue
        else:
            uf.union(x-1, y-1)
    # print(' ', uf.count)
    if uf.count > 1:
        count += 1


# for x, y in bridges:
#     uf.union(x-1, y-1)
#     result.append(uf.get_group_num())

# print(result[::-1])

print(count)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

ans = 0

n,m = map(int, input().split())
tpl = tuple([tuple(map(int, input().split())) for _ in range(m)])
ls = []
for i in range(1,n+1):
    tmpls = []
    for j in range(1,n+1):
        if i < j:
            if (i,j) in tpl:
                tmpls.append(j)
        elif i > j:
            if (j,i) in tpl:
                tmpls.append(j)
    ls.append(tuple(tmpls))
ls = tuple(ls)

def dfs(a, visitedls, ini, ininext, flag):
    if not flag:
        visitedls.append(a)
        if a == ini:
            if ininext != visitedls[-2]:
                flag = True
        else:
            for b in ls[a-1]:
                if b not in visitedls:
                    dfs(b, visitedls, ini, ininext, flag)
        visitedls.remove(a)

def main():
    for i in range(n):
        for p in ls[i]:
            global flag, ans
            flag = False
            visitedls = []
            dfs(p, visitedls, i+1, p, flag)
            if not flag:
                ans += 1
    print(int(ans/2))



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
lab=[]
dn={}
for i in range(M):
    #lab.append(list(map(int,input().split())))
    a,b=map(int,input().split())
    lab.append([a,b])
    if not a in dn:
        dn[a]=[b]
    else:
        dn[a].append(b)
    if not b in dn:
        dn[b]=[a]
    else:
        dn[b].append(a)
ans=0
for i in range(M):
    #dtmp=copy.copy(dn)
    #for dd in dtmp:
    #    if dd[]
    st=[lab[i][0]]
    df={}
    ng=lab[i][1]
    #while st:
    f=0
    for j in range(N):
        if not st:
            break
        ntmp=st.pop()
        if ntmp==ng:
            f=1
            break
        for nc in dn[ntmp]:
            if not nc in df and not (ntmp==lab[i][0] and nc==lab[i][1]):
                st.append(nc)
                df[nc]=1
    if f==0:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
def ABC075C_dfs(root, graph, frm, now):
    
    for dst in graph[now]:
        if dst != frm:
           if dst in root:
               base = root.index(dst)
               return len(root) - base + 1
           else:
              root.append(now)
              ret = ABC075C_dfs(root, graph, now, dst)
              if ret == 0:
                  root.remove(now)
              else:
                  return ret
 
    return 0

def ABC075C_Bridge():
    N, M = map(int, input().strip().split())
    graph = [[] for i in range(N)]

    for i in range(M):
        a1, b1 = list(map(int, input().strip().split()))
        a1 -= 1
        b1 -= 1
        graph[a1].append(b1)
        graph[b1].append(a1)

    root = []
    print(M - ABC075C_dfs(root, graph, -1, 0))
        


def main():
    ABC075C_Bridge()

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def ABC075C_dfs(root, graph, frm, now):
    
    for dst in graph[now]:
        if dst != frm:
           if dst in root:
               base = root.index(dst)
               return len(root) - base + 1
           else:
              root.append(now)
              ret = ABC075C_dfs(root, graph, now, dst)
              if ret == 0:
                  root.remove(now)
              else:
                  return ret
 
    return 0

def ABC075C_Bridge():
    N, M = map(int, input().strip().split())
    graph = [[] for i in range(N)]

    if(N > M):
        print(M)
        return 0

    for i in range(M):
        a1, b1 = list(map(int, input().strip().split()))
        a1 -= 1
        b1 -= 1
        graph[a1].append(b1)
        graph[b1].append(a1)

    root = []
    print(M - ABC075C_dfs(root, graph, -1, 0))
        


def main():
    ABC075C_Bridge()

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def ABC075C_dfs(root, graph, frm, now):
    
    for dst in graph[now]:
        if dst != frm:
           if dst in root:
               base = root.index(dst)
               return len(root) - base + 1
           else:
              root.append(now)
              ret = ABC075C_dfs(root, graph, now, dst)
              if ret == 0:
                  root.remove(now)
                  return 0
              else:
                  return ret
 
    return 0

def ABC075C_Bridge():
    N, M = map(int, input().strip().split())
    graph = [[] for i in range(N)]

    for i in range(M):
        a1, b1 = list(map(int, input().strip().split()))
        a1 -= 1
        b1 -= 1
        graph[a1].append(b1)
        graph[b1].append(a1)

    root = []
    print(M - ABC075C_dfs(root, graph, -1, 0))
        


def main():
    ABC075C_Bridge()

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import copy
def dfs(tmp):
  seen[tmp] = 1
  for i in range(n):
    if ll[tmp][i] == 1 and seen[i] == 0:
      tmp = i
      dfs(tmp)
  

n,m = map(int,input().split())
ll =[[0]*n for _ in [0]*n]
edges = [list(map(int,input().split())) for _ in [0]*m]
for edge in edges:
  ll[edge[0]-1][edge[1]-1] = 1
  ll[edge[1]-1][edge[0]-1] = 1
originalll = ll.copy()
seen = [0]*n
ans = 0

for edge in edges:
  ll = copy.deepcopy(originalll)
  ll[edge[0]-1][edge[1]-1] = 0
  ll[edge[1]-1][edge[0]-1] = 0
  seen = [0]*n
  tmp = 0
  dfs(tmp)
  if sum(seen) < n:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
def dfs(seen,tmp):
  seen[tmp] = 1
  for i in range(n):
    if ll[tmp][i] == 1 and seen[i] == 0:
      tmp = i
      dfs(seen,tmp)
  return seen,tmp

n,m = map(int,input().split())
ll =[[0]*n for _ in [0]*n]
edges = [list(map(int,input().split())) for _ in [0]*m]
for edge in edges:
  ll[edge[0]-1][edge[1]-1] = 1
  ll[edge[1]-1][edge[0]-1] = 1
originalll = ll.copy()
seen = [0]*n
ans = 0

for edge in edges:
  ll = copy.deepcopy(originalll)
  ll[edge[0]-1][edge[1]-1] = 0
  ll[edge[1]-1][edge[0]-1] = 0
  seen = [0]*n
  tmp = 0
  seen,tmp = dfs(seen,tmp)
  if sum(seen) < n-1:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
def dfs(seen,tmp):
  for i in range(n):
    if ll[tmp][i] == 1 and seen[i] == 0:
      seen[i] = 1
      tmp = i
      seen,tmp = dfs(seen,tmp)
  return seen,tmp

n,m = map(int,input().split())
ll =[[0]*n for _ in [0]*n]
edges = [list(map(int,input().split())) for _ in [0]*m]
for edge in edges:
  ll[edge[0]-1][edge[1]-1] = 1
  ll[edge[1]-1][edge[0]-1] = 1
originalll = ll.copy()
seen = [0]*n
ans = 0

for edge in edges:
  ll = copy.deepcopy(originalll)
  ll[edge[0]-1][edge[1]-1] = 0
  ll[edge[1]-1][edge[0]-1] = 0
  seen = [0]*n
  tmp = 0
  seen,tmp = dfs(seen,tmp)
  if sum(seen) < n-1:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  N,M=LI()
  l=[0]*N

  l2=[]
  for _ in range(M):
    a,b=LI()

    l[a-1]+=1
    l[b-1]+=1

    l2.append([a,b])

  x=l.count(1)
  if x==0:
    return 0

  l3=[]
  for i,x in enumerate(l):
    if x==1:
      l3.append(i+1)

  ans=len(l3)
  cnt=0
  for i,_x in enumerate(l2):
    a,b=_x
    if l3.count(a)>0:
      while True:
        cnt+=1
        if cnt==100010:
          return M
        if l[b-1]==2:
          ans+=1
          for x in l2:
            if [a,b]!=x:
              if x[0]==b:
                b=x[1]
                break
              elif x[1]==b:
                b=x[0]
                break
        else:
          break

    elif l3.count(b)>0:
      while True:
        cnt+=1
        if cnt==100010:
          return M
        if l[a-1]==2:
          ans+=1
          for x in l2:
            if [a,b]!=x:
              if x[0]==a:
                a=x[1]
                break
              elif x[1]==a:
                a=x[0]
                break
        else:
          break

  return ans

# main()
print(main())

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
l = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    l[a-1].append(b-1)
    l[b-1].append(a-1)
stack = []
seen = [False]*N
ans = 0
for i, ary in enumerate(l):
    if len(ary) == 1 and not seen[i]:
        stack.append(i)
        seen[i] = True
        while len(stack) != 0:
            for n in l[stack.pop()]:
                if not seen[n]:
                    if len(l[n]) < 3:
                        stack.append(n)
                        seen[n] = True
                    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
l = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    l[a-1].append(b-1)
    l[b-1].append(a-1)
stack = []
seen = [False]*N
min_length = 99999
max_length = 0
for i, ary in enumerate(l):
    min_length = min(min_length, len(ary))
    max_length = max(max_length, len(ary))
    if len(ary) == 1:
        stack.append(i)
        seen[i] = True
ans = 0
if max_length <= 2 and min_length == 1:
    ans = 1

while len(stack) != 0:
    n = stack.pop()
    for i in l[n]:
        if not seen[i]:
            if len(l[i]) < 3:
                stack.append(i)
                seen[i] = True
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a1=[0]*m
b1=[0]*m
for i in range(m):
  a1[i],b1[i]=map(int,input().split())
ans=0
a,b=a1,b1
for i in range(m):
  a=[int(a1[i]) for i in range(m)]
  b=[int(b1[i]) for i in range(m)]
  a.pop(i)
  b.pop(i)
  for j in range(n):
    for k in range(n):
      for l1,l2 in zip(a,b):
        if l1==j:
          j=l2
        if j==k:
          break
      if l1!=j and j!=k:
        ans+=1
        break
      elif j==k:
        break
    if l1!=j and j!=k:
        break
    elif j==k:
      break
  a,b=a1,b1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]

def find_root(root,x):
    y = root[x]
    if x == y:
        return x
    z = find_root(root,y)
    root[x] = z
    return z
 
def merge(root,size,x,y):
    x = find_root(root,x)
    y = find_root(root,y)
    if x == y:
        return
    sx,sy = size[x],size[y]
    if sx < sy:
        sx,sy = sy,sx
        x,y = y,x
    root[y] = x
    size[x] += sy

def UF_make(graph,n):
    Root=list(range(n+1))
    Size=[1] * (n+1)
    for i in range(len(graph)):
        merge(Root,Size,graph[i][0],graph[i][1])
    Root[-1] = find_root(Root,n)  #
    Root.pop(0)  #
    return Root

ans=0
for i in range(M):
    if len(set((UF_make(AB[:i]+AB[i+1:],N))))!=1:
        ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]

def find_root(root,x):
    y = root[x]
    if x == y:
        return x
    z = find_root(root,y)
    root[x] = z
    return z
 
def merge(root,size,x,y):
    x = find_root(root,x)
    y = find_root(root,y)
    if x == y:
        return
    sx,sy = size[x],size[y]
    if sx < sy:
        sx,sy = sy,sx
        x,y = y,x
    root[y] = x
    size[x] += sy

def UF_make(graph,n):
    Root=list(range(n+1))
    Size=[1] * (n+1)
    for i in range(len(graph)):
        merge(Root,Size,graph[i][0],graph[i][1])
    Root[-1] = find_root(Root,n)  #
    Root.pop(0)  #
    return Root

ans=0
for i in range(M):
    if max(UF_make(AB[:i]+AB[i+1:],N))!=1:
        ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    d = collections.defaultdict(list)
    ab = []
    for i in range(m):
        a, b = list(map(int, readline().split()))
        d[a-1] += [b-1]
        d[b-1] += [a-1]
        ab.append(sorted([a-1, b-1]))
    cnt = 0
    for abl in ab:
        ql = collections.deque()
        ql.append(0)
        fq = collections.defaultdict(list)
        fq[0]
        a, b = abl
        while ql:
            q = ql.popleft()
            for v in d[q]:
                if v not in fq and [a, b] != sorted([q, v]):
                    ql.append(v)
                    fq[v]
    print(cnt)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
#print(graph)#受け取り終了

#ぐるっと一周を除く
c=0
for i in range(n):
  if len(graph[i])!=2:
    c+=1
if c==0:
  print(0)

else:
  cnt=0;p=0;q=0
  for i in range(n):
    if len(graph[i])==2:
        p+=1
        x=graph[i][0]
        y=graph[i][1]
        if (x in graph[y]) and (y in graph[x]):
            cnt+=0
        elif len(graph[x])==2 or len(graph[y])==2:
            cnt+=1
        else:
            cnt+=2
    elif len(graph[i])==1:
        q+=1
  if p+q==n and q>0:
      cnt+=1
  print(cnt)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
#print(graph)#受け取り終了

#ぐるっと一周を除く
c=0
for i in range(n):
  if len(graph[i])!=2:
    c+=1
if c==0:
  print(0)

else:
  cnt=0;p=0;q=0
  for i in range(n):
    if len(graph[i])==2:
        p+=1
        x=graph[i][0]
        y=graph[i][1]
        if (x in graph[y]) and (y in graph[x]):
            cnt+=0
        elif (len(graph[x]) or len(graph[y]))==2:
            cnt+=1
        else:
            cnt+=2
    elif len(graph[i])==1:
        q+=1
  if p+q==n and q>0:
      cnt+=1
  print(cnt)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
#print(graph)#受け取り終了

#ぐるっと一周を除く
c=0
for i in range(n):
  if len(graph[i])!=2:
    c+=1
if c==0:
  print(0)

else:
  cnt=0
  p=0;q=0
  for i in range(n):
    if len(graph[i])==2:
        p+=1
        x=graph[i][0]
        y=graph[i][1]
        if len(graph[x])>=3 and len(graph[y])==1:
            cnt+=2
        elif len(graph[x])>=3 and len(graph[y])>=3:
            cnt+=0
        elif len(graph[x])>=3 and len(graph[y])==2:
            cnt+=1
        elif len(graph[x])==2 and len(graph[y])>=3:
            cnt+=1
        elif len(graph[x])==2 and len(graph[y])==2:
            cnt+=1
        elif len(graph[x])==1 and len(graph[y])>=3:
            cnt+=2
        elif len(graph[x])==1 and len(graph[y])==2:
            cnt+=1
        elif len(graph[x])==2 and len(graph[y])==1:
            cnt+=1
    elif len(graph[i])==1:
        q+=1
    if p+q==n and q>0:
        cnt+=1
  print(cnt)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
graph=[[] for i in range(n)]
visited=[False]*n
visited[0]=True
from collections import deque
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
#print(graph)#受け取り終了

#ぐるっと一周を除く
a=0
for i in range(n):
  if len(graph[i])!=2:
    a+=1
if a==0:
  print(0)

else:
  cnt=0
  p=0;q=0
  for i in range(n):
    if len(graph[i])==2:
        p+=1
        x=graph[i][0]
        y=graph[i][1]
        if len(graph[x])>=3 and len(graph[y])==1:
            cnt+=2
        elif len(graph[x])>=3 and len(graph[y])>=3:
            cnt+=0
        elif len(graph[x])>=3 and len(graph[y])==2:
            cnt+=1
        elif len(graph[x])==2 and len(graph[y])>=3:
            cnt+=1
        elif len(graph[x])==2 and len(graph[y])==2:
            cnt+=1
        elif len(graph[x])==1 and len(graph[y])>=3:
            cnt+=2
        elif len(graph[x])==1 and len(graph[y])==2:
            cnt+=1
        elif len(graph[x])==2 and len(graph[y])==1:
            cnt+=1
    elif len(graph[i])==1:
        q+=1
    if p+q==n and q>0:
        cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.parents=[-1]*n
  def find(self,x):
    if self.parents[x]<0:
      return x
    else:
      self.parents[x]=self.find(self.parents[x])
      return self.parents[x]
  def union(self,x,y):
    x=self.find(x)
    y=self.find(y)
    if x==y:
      return
    if self.parents[x]>self.parents[y]:
      x,y=y,x
    self.parents[x]+=self.parents[y]
    self.parents[y]=x
  def same(self,x,y):
    return self.find(x)==self.find(y)
  def members(self,x):
    root=self.find(x)
    return [i for i in range(self.n) if self.find(i)==root]
  def roots(self):
    return [i for i,x in enumerate(self.parents) if x<0]
  def group_count(self):
    return len(self.roots())
  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}
  def __str__(self):
    return '\n'.join('{}: {}'.format(r,self.members(r)) for r in self.roots())
  
n,m=map(int,input().split())
a,b=[0]*m,[0]*m
res=0
for i in range(m):
  UF=UnionFind(n)
  for j in range(m):
    if j!=i:
      UF.union(a[j],b[j])
  if UF.group_count()==2:
    ret+=1
print(res)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

WHITE = 0
GRAY = 1
BLACK = 2


def dfs(s, n, m):
    color = [WHITE] * n

    stack = [s]
    color[s] = GRAY
    while stack:
        u = stack[-1]
        for v, flg in enumerate(m[u]):
            if flg:
                if color[v] == WHITE:
                    color[v] = GRAY
                    stack.append(v)
                    break
        else:
            stack.pop()
            color[u] = BLACK

    cnt = color.count(BLACK)

    return cnt


def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(m)]

    g = [[0] * n for _ in range(n)]
    for a, b in ab:
        a -= 1
        b -= 1
        g[a][b] = 1
        g[b][a] = 1

    ans = 0
    for a, b in ab:
        a -= 1
        b -= 1
        cp = deepcopy(g)
        cp[a][b] = 0
        cp[b][a] = 0

        cnt = dfs(0, n, cp)

        if cnt != m:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
WHITE = 0
GRAY = 1
BLACK = 2


def dfs(s, n, m):
    color = [WHITE] * n

    stack = [s]
    color[s] = GRAY
    while stack:
        u = stack[-1]
        for v, flg in enumerate(m[u]):
            if flg:
                if color[v] == WHITE:
                    color[v] = GRAY
                    stack.append(v)
                    break
        else:
            stack.pop()
            color[u] = BLACK

    cnt = color.count(BLACK)

    return cnt


def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(m)]

    g = [[0] * n for _ in range(n)]
    for a, b in ab:
        a -= 1
        b -= 1
        g[a][b] = 1
        g[b][a] = 1

    ans = 0
    for a, b in ab:
        a -= 1
        b -= 1
        cp = g.copy()
        cp[a][b] = 0
        cp[b][a] = 0

        cnt = dfs(0, n, cp)

        if cnt != n:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()