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.

Solution (Python):
class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n+1)] 
        self.rank = [0] * (n+1)

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

        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)

        if self.rank[x] < self.rank[y]:
            self.par[x] = y

        else:
            self.par[y] = x

            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

n,m = map(int,input().split())
 
edges = [list(map(int,input().split())) for i in range(m)]
 
ans = 0
 
for i in range(m):
	uf = UnionFind(n)
	for j in range(m):
		if i != j:
			uf.union(edges[j][0]-1,edges[j][1]-1)
 
	c = 0
	for j in range(n):
		if j == uf.find(j):
			c += 1
 
	if c > 1 :
		ans += 1 
print(ans)

Solution (Python):
import sys

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def dfs(G, v):
	seen[v] += 1
	
	
	for nv in G[v]:
		if seen[nv]: continue
		
		dfs(G, nv)

N, M = MAP()
A = [MAP() for _ in range(M)]



ans = 0
for i in range(M):
	G = [[] for _ in range(N)]
	for j, m in enumerate(A):
		
		if i != j:
			a, b = m
			G[a-1].append(b-1)
			G[b-1].append(a-1)
		
	seen = [0] * N
	dfs(G, 1)
	
	
	if sum(seen) != N: ans += 1

print(ans)

Solution (Python):
n, m = map(int, input().split())
ab_array = [[int(x) for x in input().split()] for y in range(m)]
graph = [[] for x in range(n + 1)]


def dfs(graph, now, a, b):
    visited[now] = True
    for next in graph[now]:
        if (now == a and next == b) or (now == b and next == a):
            continue
        if not visited[next]:
            dfs(graph, next, a, b)
    return visited.count(False) == 1


for a, b in ab_array:
    graph[a].append(b)
    graph[b].append(a)
ans = 0
for a, b in ab_array:
    start = a
    end = b
    visited = [False for x in range(n + 1)]
    now = 1
    next_array = [now]
    while len(next_array) != 0:
        visited[now] = True
        for next in graph[now]:
            if (now == a and next == b) or (now == b and next == a):
                continue
            if not visited[next]:
                next_array.append(next)
        now = next_array.pop()
    if visited.count(False) == 1:
        ans += 1

    
    
print(m - ans)

Solution (Python):
n, m = map(int, input().split())
ab_array = [[int(x) for x in input().split()] for y in range(m)]
graph = [[] for x in range(n + 1)]


def dfs(graph, now, a, b):
    visited[now] = True
    for next in graph[now]:
        if (now == a and next == b) or (now == b and next == a):
            continue
        if not visited[next]:
            dfs(graph, next, a, b)
    return visited.count(False) == 1


for a, b in ab_array:
    graph[a].append(b)
    graph[b].append(a)
ans = 0
for a, b in ab_array:
    start = a
    end = b
    visited = [False for x in range(n + 1)]
    if dfs(graph, 1, a, b):
        ans += 1
print(m - ans)

Solution (Python):
def dfs(current):
    for maps in Graph[current]:
        if maps in already:
            continue
        else:
            already.append(maps)
            dfs(maps)

n,m = map(int,input().split())
ans = 0
Edges = []
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    Edges.append((a,b))

for i in range(m):
    egdes = Edges[0:i]+Edges[i+1:]
    Graph = [[] for _ in range(n)]
    for edge in egdes:
        Graph[edge[0]].append(edge[1])
        Graph[edge[1]].append(edge[0])
    already = []
    dfs(0)
    if len(already) != n:
        ans += 1
print(ans)

Solution (Python):
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 size(self, x):
        return -self.parents[self.find(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())
edge = [list(map(int,input().split())) for _ in range(M)]
ans = 0
for i in range(M):
    tmp = edge.pop(i)
    uf = UnionFind(N)
    for j in range(M-1):
        u,t = edge[j][0]-1,edge[j][1]-1
        uf.union(u,t)
        uf.union(t,u)
    if uf.group_count() != 1:
        ans += 1
    edge.insert(i,tmp)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
n,m=map(int,input().split())
es=[[[] for j in range(n)] for i in range(m)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    for j in range(m):
        if i!=j:
            es[j][a].append(b)
            es[j][b].append(a)
sw = [[True for i in range(n)] for i in range(m)]
def dfs(v,k):
    sw[k][v] = False
    for i in es[k][v]:
        if sw[k][i]:
            dfs(i,k)
for i in range(m):
    dfs(0,i)
ans=0
for j in range(m):
    for i in range(n):
        if sw[j][i]:
            ans+=1
            break
print(ans)

Solution (Python):
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 size(self, x):
        return -self.parents[self.find(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())
abl = []
for _ in range(m):
    a,b = map(int,input().split())
    abl.append((a,b))

all_uf = UnionFind(n)
for a,b in abl:
    all_uf.union(a-1,b-1)
k = all_uf.group_count()

ans = 0
for i in range(m):
    uf = UnionFind(n)
    for a,b in abl[:i] + abl[i+1:]:
        uf.union(a-1,b-1)
    if k != uf.group_count():
        ans += 1

print(ans)

Solution (Python):
n, m = map(int, input().split())
A = [list(map(int, input().split())) for i in range(m)]

B = [[] for i in range(n + 1)]

for i in range(m):
    B[A[i][0]].append(A[i][1])
    B[A[i][1]].append(A[i][0])

co = 0
ok = 0
while ok == 0:
    ok = 1
    for i in range(1, n + 1):
        if len(B[i]) == 1:
            ok = 0
            k = B[i][0]
            B[i].remove(k)
            B[k].remove(i)
            co += 1

print(co)

Solution (Python):
import copy
def dfs(graph,s):
    S=[s]
    visited=[s]
    while len(S)>0:
        v=S.pop()

        for n in graph[v]:

            if n not in visited:
                S.append(n)
                visited.append(n)
    return len(visited)


if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    graph={i+1:[] for i in range(N)}
    E=[]
    for i in range(M):
        a,b=list(map(int,input().split()))
        graph[a].append(b)
        graph[b].append(a)
        E.append((a,b))

    ans=0
    for e in E:
        a,b=e[0],e[1]
        copied=copy.deepcopy(graph)
        copied[a].remove(b)
        copied[b].remove(a)
        if dfs(copied,1)!=N:
            ans+=1
    print(ans)

Solution (Python):
N,M=map(int,input().split())
lab=[]
dn={}
for i in range(M):
    
    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):
    
    
    
    st=[lab[i][0]]
    df={lab[i][0]:1}
    ng=lab[i][1]
    
    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)

Solution (Python):

import copy
N , M = map(int,input().split())

tmp_list = []
for _ in range(M):
    a , b = map(int,input().split())
    tmp_list.append([a - 1,b - 1])

def dfs(now):
    stack = [work_graph[now]]
    while stack:
        next_nodes = stack.pop()
        for next_node in next_nodes:
            if not visited[next_node]:
                visited[next_node] = True
                stack.append(work_graph[next_node])


cnt = 0
for i in range(M):
    work_graph = [[] for _ in range(N)]
    for j in range(M):
        if j == i:
            continue
        work_graph[tmp_list[j][0]].append(tmp_list[j][1])
        work_graph[tmp_list[j][1]].append(tmp_list[j][0])
    visited = [False] * N
    dfs(0)
    if not all(visited):
        cnt += 1
print(cnt)

Solution (Python):
N, M = map(int, input().split())

a_list = []
b_list = []
edge = [[0 for _ in range(N)] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    a_list.append(a - 1)
    b_list.append(b - 1)
    edge[a - 1][b - 1] = 1
    edge[b - 1][a - 1] = 1

ans = 0
flags = [False] * N

def dfs(v):
    flags[v] = True
    for v2 in [i for i, x in enumerate(edge[v]) if x == 1]:
        if flags[v2]:
            continue
        dfs(v2)

for i in range(M):
    edge[a_list[i]][b_list[i]] = 0
    edge[b_list[i]][a_list[i]] = 0

    flags = [False] * N

    dfs(0)
    ans += 1 if not all(flags) else 0

    edge[a_list[i]][b_list[i]] = 1
    edge[b_list[i]][a_list[i]] = 1

print(ans)

Solution (Python):
from copy import deepcopy
N, M = map(int, input().split())
graph = dict()
for i in range(N):
    graph[i] = []
ab = [tuple(map(int, input().split())) for _ in range(M)]

import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
inf = float("inf")

graph = np.zeros((N, N))

for a, b in ab:
    graph[a - 1][b - 1] = 1
counter = 0
for a, b in ab:
    g = deepcopy(graph)
    g[a - 1][b - 1] = 0
    g = csr_matrix(g)
    shortest_paths = shortest_path(g, directed=False, method="D")
    if inf in shortest_paths[0]:
        counter += 1
print(counter)

Solution (Python):
from copy import deepcopy
N, M = map(int, input().split())
graph = dict()
for i in range(N):
    graph[i] = []
ab = [tuple(map(int, input().split())) for _ in range(M)]

import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
inf = float("inf")

graph = np.zeros((N, N))

for a, b in ab:
    graph[a - 1][b - 1] = 1
counter = 0
for a, b in ab:
    g = deepcopy(graph)
    g[a - 1][b - 1] = 0
    g = csr_matrix(g)
    shortest_paths = shortest_path(g, directed=False, method="D")
    if inf in shortest_paths[0]:
        counter += 1
print(counter)

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

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] = 1
  dfs(tmp)
  if sum(seen) < n:
    ans += 1
print(ans)

Solution (Python):
def ABC075C_dfs(targ, root, graph, now):

    for dst in graph[now]:
        if targ == sorted([dst, now]):
            continue
        if dst not in root:
            root.append(dst)
            ABC075C_dfs(targ, root, graph, dst)


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

    if N > M:
        print(M)
        return 0
    
    edge = [[] for i in range(M)]
    for i in range(M):
        a1, b1 = map(int, input().strip().split())
        a1 -= 1
        b1 -= 1
        graph[a1].append(b1)
        graph[b1].append(a1)
        edge[i] = sorted([a1, b1])

    ans = 0
    for ed in edge:
        root = [0]
        ABC075C_dfs(ed, root, graph, 0)
        if len(root) != N:
            ans += 1

    print(ans)

def main():
    ABC075C_Bridge()

if __name__ == "__main__":
    main()

Solution (Python):
class UF:
    def __init__(self, N):
        self.uf = [-1]*N
        self.n = N

    def find(self, x):
        if self.uf[x]<0: return x
        self.uf[x] = self.find(self.uf[x])
        return self.uf[x]

    def size(self, x):
        return -self.uf[self.find(x)]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x==y: return
        if self.size(x) > self.size(y): x, y = y, x
        self.uf[y] += self.uf[x]
        self.uf[x] = y
        self.n -= 1

N, M = list(map(int, input().split()))
E = [tuple(map(int, input().split())) for _ in range(M)]

ans = 0
for i in range(M):
    uf = UF(N)
    for j in range(M):
        if i==j: continue
        a, b = E[j]
        uf.union(a-1, b-1)
    if uf.n==2: ans+=1

print(ans)

Solution (Python):
N, M = map(int, input().split())
l = [[] for _ in range(N)]
ab = []
ans = 0
for _ in range(M):
    ab.append([int(i)-1 for i in input().split()])
    l[ab[-1][0]].append(ab[-1][1])
    l[ab[-1][1]].append(ab[-1][0])
for a, b in ab:
    stack = []
    seen = [False]*N
    stack.append(0)
    seen[0] = True
    while len(stack) != 0:
        v = stack.pop()
        for v2 in l[v]:
            if v == a and v2 == b or v == b and v2 == a:
                continue
            if not seen[v2]:
                stack.append(v2)
                seen[v2] = True
    if False in seen:
        ans += 1

print(ans)

Solution (Python):
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 size(self, x):
        return -self.parents[self.find(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_counts(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())  

edges = []
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    edges.append((a, b))
ans = M 
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if j == i:
            continue
        uf.union(edges[j][0], edges[j][1])
    if min(uf.parents) == -N:  
        ans -= 1
print(ans)

Solution (Python):
N,M=map(int,input().split())
e=[[] for i in range(N)]
tester=[None]*M
for i in range(M):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  e[a].append(b)
  e[b].append(a)
  tester[i]=set([a,b])
  
ans=0
for test in tester:
  stack=[]
  stack.append([0,-1])
  seen=[0 for i in range(N)]
  while stack:
    node=stack.pop()
    v=node[0]
    parent=node[1]
    if seen[v]==1:
      continue
    seen[v]=1
    childs=e[v]
    for child in childs:
      if child==parent:
        continue
      if test==set([v,child]):
        continue
      stack.append([child,v])
      
  if sum(seen)!=N:
    ans+=1
print(ans)

Solution (Python):
n,m = map(int, input().split())
data = []
for i in range(m):
    data.append(list(map(int, input().split())))

not_bridge = 0
def dfs(node, finished):
    finished.add(node)
    global not_bridge
    if len(finished) == n:
        not_bridge += 1
    else:
        for i in adjacent_list[node]:
            if i not in finished:
                dfs(i, finished)
    

for i in range(m):
    adjacent_list = [[]for i in range(n+1)]
    finished = set()
    for j in range(m):
        if i != j:
            a, b = data[j]
            adjacent_list[a].append(b)
            adjacent_list[b].append(a)
    dfs(1, finished)
print(m - not_bridge)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
l = [[] for _ in range(n)]
ab = []
for _ in range(m):
  a, b = map(int, input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)
  ab.append((a, b))
seen = [False]*n
def dfs(v):
  for i in l[v]:
    if not seen[i]:
      seen[i] = True
      dfs(i)
ans = 0
for a, b in ab:
  l[a-1].remove(b-1)
  l[b-1].remove(a-1)
  c = 0
  for i in range(n):
    if not seen[i]:
      dfs(i)
      c += 1
  if c > 1:
    ans += 1
  seen = [False]*n
  l[a-1].append(b-1)
  l[b-1].append(a-1)
print(ans)

Solution (Python):
N, M = map(int, input().split())
l=[[] for i in range(N)]
e = [[int(i) for i in input().split()] for i in range(M)]
e0=e
c=0

def DFS(v):
  seen.append(v)
  for v2 in l[v]:
    if not v2 in seen:
      DFS(v2)
  return seen

for i in range(M):
  seen=[]
  l=[[] for i in range(N)]
  for j in range(M):
    if j!=i:
      l[(e[j][0])-1].append(e[j][1]-1)
      l[(e[j][1])-1].append(e[j][0]-1)
  S=DFS(0)
  if len(S)!=N:c+=1
print (c)

Solution (Python):
def main():
    N, M = (int(i) for i in input().split())
    G = [[] for _ in range(N)]
    edges = []
    s = -1
    for i in range(M):
        a, b = (int(i)-1 for i in input().split())
        if i == 0:
            s = a
        G[a].append(b)
        G[b].append(a)
        edges.append((a, b))

    def dfs(v, seen, remove_edge):
        todo = []
        seen[v] = True
        todo.append(v)
        while todo:
            u = todo[-1]
            for next_v in G[u]:
                if seen[next_v]:
                    continue
                if (u, next_v) == remove_edge or (next_v, u) == remove_edge:
                    continue
                seen[next_v] = True
                todo.append(next_v)
                break
            else:
                todo.pop()

    ans = 0
    for e in edges:
        seen = [False] * N
        dfs(s, seen, e)
        if all(seen):
            continue
        ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

N,M=map(int,input().split())
G = [[] for i in range(N)]
A = []
B = []

for i in range(M):
    a,b = map(lambda x:int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)
    A.append(a)
    B.append(b)


def dfs(x):
    global old
    old[x] = True
    for i in G[x]:
        if not(old[i]):
            dfs(i)

ans = 0
for i in range(M):
    a,b = A[i], B[i]
    G[a].remove(b)
    G[b].remove(a)

    old = [False]*N
    dfs(0)
    if old != [True]*N:
        ans += 1

    G[a].append(b)
    G[b].append(a)

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(100)

N, M = map(int,input().split())
admat = [[0] * N for _ in range(N)]
edges = []
for _ in range(M):
    a, b = map(int,input().split())
    a -= 1; b -= 1
    admat[a][b] = 1
    admat[b][a] = 1
    edges.append((a, b))

def dfs(v):
    visited[v] = 1
    for nv, bit in enumerate(admat[v]):
        if bit == 0:
            continue
        if not visited[nv]:
            dfs(nv)

ans = 0

for a, b in edges:
    visited = [0] * N
    admat[a][b] = 0
    admat[b][a] = 0
    dfs(0)
    if all(visited):
        pass
    else:
        ans += 1
    admat[a][b] = 1
    admat[b][a] = 1

print(ans)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

def main():
    N,M=MI()
    AB=LLIN_(M)
    matrix = [[0]*N for _ in range(N)]

    def dfs(matrix):
        stack = [0]
        visited = set([0])
        while stack:
            u = stack.pop()
            for i,v in enumerate(matrix[u]):
                if v and i not in visited:
                    stack.append(i)
                    visited.add(i)
        return len(visited)!=len(matrix) 
    
    for i,(a,b) in enumerate(AB):
        matrix[a][b] = 1
        matrix[b][a] = 1
    ans = 0
    for i,(a,b) in enumerate(AB):
        matrix[a][b] = 0
        matrix[b][a] = 0
        ans += dfs(matrix)
        matrix[a][b] = 1
        matrix[b][a] = 1
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
def search(t, i, reached):
    if reached[i]:
        return

    reached[i] = True
    for nt in t[i]:
        search(t, nt, reached)


def main():
    N, M = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(M)]

    t = [[] for _ in range(N)]
    for a, b in AB:
        a -= 1
        b -= 1
        t[a].append(b)
        t[b].append(a)

    cnt = 0
    for a, b in AB:
        a -= 1
        b -= 1

        t[a].remove(b)
        t[b].remove(a)
        reached = [False for _ in range(N)]
        search(t, 0, reached)
        if not all(reached):
            cnt += 1

        t[a].append(b)
        t[b].append(a)

    print(cnt)


main()

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

from collections import defaultdict
ans = 0
for i in range(m):
    visited = [0] * n

    graph = defaultdict(list)
    for j in range(m):
        if j != i:
            graph[ab[j][0] - 1].append(ab[j][1] - 1)
            graph[ab[j][1] - 1].append(ab[j][0] - 1)

    stack = [0]
    while stack:
        start = stack.pop()
        for target in graph[start]:
            if visited[target] == 0:
                visited[target] = 1
                stack.append(target)

    if sum(visited) != n:
        ans += 1

print(ans)

Solution (Python):
N, M = [int(i) for i in input().split()]
graph = [[0]*N for i in range(N)]
vstd = [0] * N

for i in range(M):
    a, b = [int(i) for i in input().split()]
    graph[a-1][b-1] = graph[b-1][a-1] = 1


def dfs(v):
    vstd[v] = 1
    for v2 in range(N):
        if graph[v][v2] == 0:
            continue
        if vstd[v2] == 1:
            continue
        dfs(v2)
 
ans = 0
for i in range(N):
    for j in range(N):
        if graph[i][j] == 0:
            continue
        graph[i][j] = graph[j][i] = 0
        for k in range(N):
            vstd[k] = 0
        dfs(0)
        bridge = False
        for k in range(N):
            if vstd[k] == 0:
                bridge = True
        if bridge == True:
            ans += 1
        graph[i][j] = graph[j][i] = 1

print(ans//2)

Solution (Python):
n, m = map(int, input().split())
li = []
count = 0

def check_dfs(node_list):
    traveled = []
    return dfs(node_list, traveled, 0)


def dfs(node_list, t_list, position):
    t_list.append(position)
    if len(t_list) == n:
        return 0
    for i in node_list[position]:
        if i not in t_list:
            dfs(node_list, t_list, i)
    if len(t_list) == n:
        return 0
    else:
        return 1

for i in range(m):
    array = list(map(int, input().split()))
    li.append(array)

for i in range(m):
    nodes = [[] for k in range(n)]
    for j in range(m):
        if j == i:
            continue
        else:
            nodes[li[j][0]-1].append(li[j][1]-1)
            nodes[li[j][1]-1].append(li[j][0]-1)
    count += check_dfs(nodes)

print(count)

Solution (Python):
from collections import deque

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

graph=[[False]*N for i in range(N)]
visited=[False]*N
a=[0]*M
b=[0]*M

for i in range(M):
    a[i],b[i]=map(int,input().split())
    a[i]-=1
    b[i]-=1
    graph[a[i]][b[i]]=True
    graph[b[i]][a[i]]=True

ans=0
for i in range(M):
    graph[a[i]][b[i]]=False
    graph[b[i]][a[i]]=False
    for j in range(N):
        visited[j]=False
    d=deque([0])
    while d:
        temp=d.popleft()
        visited[temp]=True
        for j in range(N):
            if graph[temp][j]==True and visited[j]==False:
                d.append(j)

    bridge = False
    for j in range(N):
        if visited[j] == False:
            bridge = True
            break
    if bridge == True:
        ans += 1
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True

print(ans)

Solution (Python):
N,M=map(int,input().split())

graph=[[False]*N for i in range(N)]
visited=[False]*N
a=[0]*M
b=[0]*M

for i in range(M):
    a[i],b[i]=map(int,input().split())
    a[i]-=1
    b[i]-=1
    graph[a[i]][b[i]]=True
    graph[b[i]][a[i]]=True


def dfs(v):
    visited[v]=True
    for v2 in range(N):
        if graph[v][v2]==False:continue
        if visited[v2]==True:continue
        dfs(v2)

ans=0
for i in range(M):
    graph[a[i]][b[i]]=False
    graph[b[i]][a[i]]=False
    for j in range(N):
        visited[j]=False
    dfs(0)
    bridge=False
    for j in range(N):
        if visited[j]==False:
            bridge=True
    if bridge==True:
        ans+=1
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True

print(ans)

Solution (Python):
N,M=map(int,input().split())

C=[[] for i in range(N)]

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

cnt=0
f=True
while f:
    f=False
    for i in range(N):
        if len(C[i])==1:
            cnt+=1
            idx=C[C[i][0]].index(i)
            C[C[i][0]].pop(idx)
            C[i].pop()
            f=True
print(cnt)

Solution (Python):
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfs(bu, bv, u=0):
        for cu in to[u]:
            if (u, cu) == (bu, bv) or (u, cu) == (bv, bu): continue
            if fin[cu]: continue
            fin[cu] = True
            dfs(bu, bv, cu)

    to = defaultdict(list)
    ee = []
    n, m = MI()
    for _ in range(m):
        a, b = map(int1, input().split())
        to[a].append(b)
        to[b].append(a)
        ee.append([a, b])
    ans = 0
    for u, v in ee:
        fin = [False] * n
        fin[0] = True
        dfs(u, v)
        if sum(fin) < n: ans += 1
    print(ans)

main()

Solution (Python):

from collections import deque

N,M=map(int,input().split())
out=[set() for v in range(N+1)];out[0]=None
es=[None]
for e in range(1,M+1):
    a,b=map(int,input().split())
    es.append((a,b))
    out[a].add(b);out[b].add(a)




ans=0
q=deque()
for e in es[1:]: 
    r=[False for v in range(N+1)];out[0]=None 
    a,b=e 
    r[a]=True 
    for u in out[a]-{b}:
        q.append(u);r[u]=True 
    while q:
        u=q.pop() 
        for v in out[u]:
            if not r[v]:
                q.append(v);r[v]=True
    if not r[b]: 
        ans+=1

print(ans)

Solution (Python):
N, M = map(int,input().split())
edges = [list(map(int,input().split())) for i in range(M)]
ans = 0
for x in edges:
  l = list(range(N))
  for y in edges:
    if y!=x:
      l=[l[y[0]-1] if l[i]==l[y[1]-1] else l[i] for i in range(N)]
  if len(set(l))!=1:
    ans+=1
print(ans)