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):

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

ab = []
ans = 0

for i in range(M):

    a,b = map(int,input().split())
    ab.append([a,b])

for i in range(M):

    abc = ab.copy()
    del abc[i]

    lis = [1] + [0] * (N-1)

    flag = True

    while flag:

        flag = False

        for j in abc:

            if lis[ j[0]-1 ] == 1:
                lis[ j[1]-1 ] = 1
                abc.remove(j)
                flag = True
                break

            elif lis[ j[1]-1 ] == 1:
                lis[ j[0]-1 ] = 1
                abc.remove(j)
                flag = True
                break

    
    if 0 in lis:
        ans += 1

print (ans)

Solution (Python):
N, M = map(int, input().split())
side = [list(map(int, input().split())) for i in range(M)]
maze = [[0] * N for i in range(N)]


for i, j in side:
    maze[i-1][j-1] = 1
    maze[j-1][i-1] = 1


visited = [0] * N

def search_side(maze, v):
    ans = []
    for i in range(len(maze[v])):
        if maze[v][i] == 1:
            ans.append(i)
    return ans

def dfs(v, visited, maze):
    visited[v] = 1
    for i in search_side(maze, v):
        if visited[i] == 1:
            continue
        else:
            visited = dfs(i, visited, maze)
    return visited

ans = 0
for i, j in side:
    maze[i-1][j-1] = 0
    maze[j-1][i-1] = 0
    if sum(dfs(0, visited, maze)) != N:
        ans += 1
    maze[i-1][j-1] = 1
    maze[j-1][i-1] = 1
    visited = [0] * N
print(ans)

Solution (Python):
n,m=map(int,input().split())
p=[]
for i in range(m):
    p.append(list(map(int,input().split())))
g=[[] for i in range(n+1)]
for pi in p:
    g[pi[0]].append(pi[1])
    g[pi[1]].append(pi[0])
def dfs(v,visited,g):
     for v2 in g[v]:
         if visited[v2]==0:
             visited[v2]=1
             dfs(v2,visited,g)

c=0
for pi in p:
    g[pi[0]].remove(pi[1])
    g[pi[1]].remove(pi[0])
    visited=[0]*(n+1)
    visited[0]=1
    visited[1]=1
    dfs(1,visited,g)
    if 0 in visited:
        c+=1
    g[pi[0]].append(pi[1])
    g[pi[1]].append(pi[0])
print(c)

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

def test(k):
    d = {i + 1 : [] for i in range(n)}
    for i, (a, b) in enumerate(es):
        if i == k:
            continue
        d[a].append(b)
        d[b].append(a)
    q = [1]
    visited = set([])
    while True:
        if len(q) == 0:
            if len(visited) == n:
                return 0
            else:
                return 1
        q2 = q[:]
        q = []
        for v in q2:
            if v not in visited:
                visited.add(v)
                q.extend(d[v])
ans = 0
for k in range(m):
    ans += test(k)
print(ans)

Solution (Python):
N,M = map(int,input().split())
T = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    T[a][b] = 1
    T[b][a] = 1
ans = 0
def f(v,x,y):
    global N,M,T,a
    a[v] = 1
    for i in range(N+1):
        if (v==x and i==y) or (v==y and i==x):
            continue
        elif T[v][i]==0 or a[i]==1:
            continue
        f(i,x,y)
for i in range(1,N+1):
    for j in range(i,N+1):
        a = [0 for _ in range(N+1)]
        f(1,i,j)
        if sum(a)!=N:
            ans += 1
print(ans)

Solution (Python):

def dfs(g, v):
    visited[v] = True
    for v2 in range(N):
        if visited[v2] == False and g[v][v2] == 1:
            dfs(g,v2)


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

graph = [[0 for i in range(N)] for j in range(N)]
edgelist = [] 
for e in range(M):
    ai, bi = map(int,input().split())
    graph[ai-1][bi-1] = 1
    graph[bi-1][ai-1] = 1
    edgelist.append([ai-1,bi-1])

bridges = 0 

for edge in edgelist:
    
    graph[edge[0]][edge[1]] = 0
    graph[edge[1]][edge[0]] = 0
    
    isbridge = False
    visited = [False for i in range(N)]
    dfs(graph, 0)
    
    for i in range(N):
        if visited[i] == False:
            isbridge = True
            break
    if isbridge == True:
        bridges += 1
    
    
    graph[edge[0]][edge[1]] = 1
    graph[edge[1]][edge[0]] = 1

print(bridges)

Solution (Python):
class UnionFind() :
	
	def __init__(self,n) :  
		
		self.par = [i for i in range(n+1)];
		self.rank = [0]*(n+1);
	
	def root(self,x) :  
		if self.par[x] == x :  
			return x;
		else :
			self.par[x] = self.root(self.par[x]);  
			return self.par[x];
	
	def unite(self,x,y) :  
		x = self.root(x);
		y = self.root(y);
		if x == y :
			return;
		
		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;
	
	def same_check(self,x,y) :  
		return self.root(x) == self.root(y);

nm = input().split(" ");
n = int(nm[0]);
m = int(nm[1]);
ab = [[0]*2 for i in range(m)];
for i in range(m) :
	s = input().split(" ");
	ab[i][0] = int(s[0]);
	ab[i][1] = int(s[1]);

basefin = UnionFind(n);
check_base = [0]*(n+1);
for i in range(m) :
	basefin.unite(ab[i][0],ab[i][1]);
for i in range(1,n+1) :
	check_base[basefin.root(i)] = 1;
base = sum(check_base);

ans = 0;
for i in range(m) :
	unifin = UnionFind(n);
	check = [0]*(n+1);
	for j in range(m) :
		if j != i :
			unifin.unite(ab[j][0],ab[j][1]);
	for k in range(1,n+1) :
		check[unifin.root(k)] = 1;
	if sum(check) - base == 1 :
		ans += 1;
	
print(ans);

Solution (Python):
n, m = [int(i) for i in input().split()]
g = [[] for i in range(n)]
for i in range(m):
    a, b = [int(_) for _ in input().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)

u = 0
s = []
non_bridge = []
while True:
    if u in s:
        tmp = s[s.index(u):]
        tmp.append(u)

        if len(tmp)>=4:
            for i in range(len(tmp)-1):
                if sorted(tmp[i:i+2]) not in non_bridge:
                    non_bridge.append(sorted(tmp[i:i+2]))
        u = s.pop()
    elif len(g[u]) > 0:
        s.append(u)
        j = -1
        for i in range(len(g[u])):
            if g[u][i] not in s:
                j = i
        u = g[u].pop(j)
    else:
        if len(s) == 0:
            break
        u = s.pop()

print(m-len(non_bridge))

Solution (Python):
class UnionFind():
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.rank = [0 for _ in range(N)]
        self.size = [1 for _ in range(N)]

    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            elif self.rank[x] < self.rank[y]:
                x, y = y, x
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]

ans = 0
for i in range(M):
    uf = UnionFind(N)
    temp = ab[:i] + ab[i+1:]
    for a, b in temp:
        uf.union(a-1, b-1)
    
    for i in range(N-1):
        if uf.is_same(i, i+1) == False:
            ans += 1
            break

print(ans)

Solution (Python):
class UnionFind:
   def __init__(self,n):
       self.parent = [-1 for i in range(n)]

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

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

   def union(self, x, y):
       x, y = self.find(x), self.find(y)
       if (x == y):
           pass
       else:
           self.parent[x] = self.parent[y]
           self.parent[y] = x

   def isgroup(self, x, y):
       return True if self.find(x) == self.find(y) else False

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]

ans = 0
for i in range(M):
    uf = UnionFind(N)
    temp = ab[:i] + ab[i+1:]
    for a, b in temp:
        uf.union(a-1, b-1)

    for i in range(1, N):
        if uf.isgroup(i, i-1) == False:
            ans += 1
            break

print(ans)

Solution (Python):



n, m = map(int, input().split())
grpah = [[False for _ in range(n)] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    grpah[a - 1][b - 1] = True
    grpah[b - 1][a - 1] = True


def dfs(cur, visited):
    if all(visited) is False and all(grpah[cur]) is False:
        for i, v in enumerate(grpah[cur]):
            if v == True and visited[i] == False:
                visited[i] = True
                dfs(i, visited)


ans = 0

for i in range(n):
    for j in range(n):
        if grpah[i][j] or grpah[j][i]:
            
            grpah[i][j] = grpah[j][i] = False
            temp_visited = [False for _ in range(n)]
            temp_visited[0] = True
            dfs(0, temp_visited)
            if all(temp_visited) is False:
                ans += 1

            
            grpah[i][j] = grpah[j][i] = True

print(ans//2)

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

nodes = {}

for a, b in ab:
    if a in nodes:
        nodes[a].append(b)
    else:
        nodes[a] = [b]
    if b in nodes:
        nodes[b].append(a)
    else:
        nodes[b] = [a]

def dfs(s, nodes, visited):
    visited[s-1] = True
    q = []
    q.extend(nodes[s])
    
    while q:
        v = q.pop()
        if visited[v-1]:
            continue
        else:
            dfs(v, nodes, visited)
    
    return all(visited)

ans = 0

for a,b in ab:
    nodes[a].remove(b)
    nodes[b].remove(a)

    visited = [False for _ in range(N)]
    if not dfs(1,nodes,visited):
        ans += 1

    if a in nodes:
        nodes[a].append(b)
    else:
        nodes[a] = [b]
    if b in nodes:
        nodes[b].append(a)
    else:
        nodes[b] = [a]
    
print(ans)

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

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

ans = 0

for ab in abs:
    a = ab[0] - 1
    b = ab[1] - 1
    _abs = abs[::]
    _abs.remove(ab)

    dist_map = [[i == j for j in range(N)] for i in range(N)]

    for _ab in _abs:
        _a = _ab[0] - 1
        _b = _ab[1] - 1
        if not dist_map[_a][_b]:
            dist_map[_a][_b] = True
            dist_map[_b][_a] = True

    for i in range(N):
        for j in range(N):
            for k in range(N):
                dist_map[j][k] = dist_map[j][k] or (dist_map[j][i] and dist_map[i][k])
                dist_map[k][j] = dist_map[j][k]

    if not dist_map[a][b]:
        ans += 1

print(ans)

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())

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


count=0
for i in range(m):
    uf=UnionFind(n)
    for j in range(m):
        if i == j:
            continue
        if not uf.same_check(g[j][0], g[j][1]):
            uf.union(g[j][0], g[j][1])
    
    root=uf.find(1)
    for j in range(2,n+1):
        if not root==uf.find(j):
            count+=1
            break

print(count)

Solution (Python):
import copy

N,M=map(int,input().split())
l_2d = [[0] * N for i in range(N)]
edges=[]

def dfs(i):
    l_visit[i-1]=1
    for j in range(1,N+1):
        if l_2d_temp[i-1][j-1]==1 and l_visit[j-1]==0:
            dfs(j)
    return

for _ in range(M):
    i,j=map(int,input().split())
    edges.append([i,j])
    l_2d[i-1][j-1]=1
    l_2d[j-1][i-1]=1
    
ans=0
for edge in edges:
    i,j=edge
    l_2d_temp=copy.deepcopy(l_2d)
    l_2d_temp[i-1][j-1]=0
    l_2d_temp[j-1][i-1]=0

    l_visit=[0]*N

    dfs(1)
    if 0 in l_visit:
        ans+=1

print(ans)

Solution (Python):
def check(graph,seen,now):
    seen[now] = True 
    for i in range(len(graph[now])):
        if seen[i] :
            continue
        if graph[now][i] == 0 :
            continue
        check(graph,seen,i)
    return seen



N,M = map(int,input().split())
para = [[i for i in map(int,input().split())] for j in range(M)]
graph =[[0 for i in range(N)] for  j in range(N)]
for i in range(M):
    graph[para[i][0]-1][para[i][1]-1] = 1
    graph[para[i][1]-1][para[i][0]-1] = 1 


ans = 0
for i in range(M):
    seen = [False]*(N)
    graph[para[i][0]-1][para[i][1]-1] = 0
    graph[para[i][1]-1][para[i][0]-1] = 0
    if False in check(graph,seen,0):
        ans += 1
    graph[para[i][0]-1][para[i][1]-1] = 1
    graph[para[i][1]-1][para[i][0]-1] = 1 

print(ans)

Solution (Python):
from collections import defaultdict
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, M = nl()
edges = defaultdict(dict)
pairs = []
for i in range(M):
    a, b = nl()
    pairs.append([a-1, b-1])
    edges[a-1][b-1] = True
    edges[b-1][a-1] = True

done = [False] * N

def check(v):
    done[v] = True
    for dst, on in edges[v].items():
        if not on or done[dst]:
            continue
        check(dst)

bridges = 0
for pair in pairs:
    edges[pair[0]][pair[1]] = False
    edges[pair[1]][pair[0]] = False

    done = [False] * N
    check(0)
    if not all(done):
        bridges += 1

    edges[pair[0]][pair[1]] = True
    edges[pair[1]][pair[0]] = True

print(bridges)

Solution (Python):
import sys
sys.setrecursionlimit(10000)
n,m=map(int,input().split())
bridge=[list(map(int,input().split())) for _ in range(m)]
def dfs(v):
    for i in g[v]:
        if visited[i]==0:
            visited[i]=1
            dfs(i)
    return

cnt=0
for i in range(m):
    g=[[] for _ in range(n)]
    visited=[0 for i in range(n)]
    bridge_=bridge[:i]+bridge[i+1:]
    for i in range(m-1):
        g[bridge_[i][0]-1].append(bridge_[i][1]-1)
        g[bridge_[i][1]-1].append(bridge_[i][0]-1)

    dfs(0)
    if 0 in visited:
        cnt+=1
print(cnt)

Solution (Python):
class UnionFind:

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

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

  def union(self, x, y):
    x, y = self.find(x), self.find(y)
    if x == y:
      return False
    elif self.rank[x] < self.rank[y]:
      self.par[x] = y
      self.sizes[y] += self.sizes[x]
    elif self.rank[x] > self.rank[y]:
      self.par[y] = x
      self.sizes[x] += self.sizes[y]
    else:
      self.par[y] = x
      self.rank[x] += 1
      self.sizes[x] += self.sizes[y]
    return True

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

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


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

for i in range(m):
  uf = UnionFind(n)
  for j in range(m):
    if i==j:
      continue
    uf.union(edge[j][0], edge[j][1])
  ans += uf.union(edge[i][0], edge[i][1])
print(ans)

Solution (Python):



from scipy.sparse.csgraph import dijkstra
N,M = map(int,input().split())
edge = [[int(x) for x in input().split()] for _ in range(M)]

graph = [[0]*(N+1) for _ in range(N+1)]
for a,b in edge:
  graph[a][b] = 1

answer = 0
INF = 10 ** 9
for a,b in edge:
  graph[a][b] = INF
  dist = dijkstra(graph, indices = a, directed = False)
  if dist[b] >= INF:
    answer += 1
  graph[a][b] = 1

print(answer)

Solution (Python):
def dfs(v):
    stack.append(v)
    while len(stack)!=0:
        x = stack.pop()
        vis.append(x)
        for i in range(n):
            if graph[x][i]==False:
                continue
            if i in vis:
                continue
            if i in stack:
                continue
            stack.append(i)
 
n,m = map(int,input().split())
graph = []
for i in range(n):
    graph.append([False]*n)
a=[]
b=[]
for i in range(m):
    aa,bb = map(int,input().split())
    a.append(aa-1)
    b.append(bb-1)
for i in range(m):
    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
    vis=[]
    stack=[]
    dfs(0)
    bridge=False
    if len(vis) < n:
        bridge=True
    if bridge:
        ans+=1
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True
print(ans)

Solution (Python):
def dfs(v):
    stack = [v]
    vis = []
    while len(stack)!=0:
        x = stack.pop()
        vis.append(x)
        for i in range(n):
            if graph[x][i]==False:
                continue
            if i in vis:
                continue
            if i in stack:
                continue
            stack.append(i)
    return len(vis)
 
n,m = map(int,input().split())
graph = []
for i in range(n):
    graph.append([False]*n)
a=[]
b=[]
for i in range(m):
    aa,bb = map(int,input().split())
    a.append(aa-1)
    b.append(bb-1)
for i in range(m):
    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
    len_vis = dfs(0)
    bridge=False
    if len_vis < n:
        bridge=True
    if bridge:
        ans+=1
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True
print(ans)

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

n,m = map(int,input().split())
visited=[False]*n
graph = []
for i in range(n):
    graph.append([False]*n)
a=[]
b=[]
for i in range(m):
    aa,bb = map(int,input().split())
    a.append(aa-1)
    b.append(bb-1)
for i in range(m):
    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
    dfs(0)
    bridge=False
    for j in range(n):
        if visited[j]==False:
            bridge =True
    if bridge:
        ans += 1
    graph[a[i]][b[i]]=True
    graph[b[i]][a[i]]=True
print(ans)

Solution (Python):



import numpy as np
from scipy.sparse.csgraph import dijkstra
N,M = map(int,input().split())
edge = [[int(x) for x in input().split()] for _ in range(M)]

graph = [[0]*(N+1) for _ in range(N+1)]
for a,b in edge:
  graph[a][b] = 1

answer = 0
for a,b in edge:
  graph[a][b] = np.inf
  dist = dijkstra(graph, indices = a, directed = False)
  if dist[b] == np.inf:
    answer += 1
  graph[a][b] = 1

print(answer)

Solution (Python):
n, m = map(int, input().split())
adj_matrix = [[False]*n for _ in range(n)]
a, b = [False]*m, [False]*m

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

def dfs(v, used):
  used[v] = True
  
  if not False in used:
    return 1

  for i in range(n):
    if adj_matrix[v][i] is False:
      continue
    if used[i] is False:
      dfs(i, used)
  return 1
  
ans = 0

for i in range(m):
  adj_matrix[a[i]-1][b[i]-1] = False
  adj_matrix[b[i]-1][a[i]-1] = False
  used = [False]*n
  dfs(0, used)
  if False in used:
    ans += 1
  adj_matrix[a[i]-1][b[i]-1] = True
  adj_matrix[b[i]-1][a[i]-1] = True

print(ans)

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



def dfs(G,v):
    
    
    seen[v]=True
    
    for i in range(len(G[v])):
        if seen[G[v][i]]==True:
            
            continue
        else:
            
            
            dfs(G,G[v][i])

cnt=0
for i in range(M):
    g=[[] for _ in range(N)]
    seen=[False for _ in range(N)]
    ee=e[:i]+e[i+1:]
    for j in range(M-1):
        a=ee[j][0]
        b=ee[j][1]
        g[a].append(b)
        g[b].append(a)
    
    
    dfs(g,0)
    if False in seen:
        
        cnt+=1
print(cnt)

Solution (Python):
from collections import deque

def dfs(graph, start, goal):
    stack = deque()
    push, pop = stack.append, stack.pop
    push(start)
    visited = [False for i in range(N+1)]
    visited[start] = True
    
    while stack:
        a = pop()
        for b in graph[a].keys():
            if a in [start, goal] and b in [start, goal]:
                continue
            elif b == goal:
                return True
            elif not visited[b]:
                push(b)
                visited[b] = True
    return False

N,M = map(int, input().split())
graph = {}
bridge = []
for i in range(M):
    a,b = map(int, input().split())
    if a not in graph:
        graph[a] = {}
    if b not in graph:
        graph[b] = {}
    graph[a][b] = graph[b][a] = 1
    bridge.append([a,b])

ans = 0
for a,b in bridge:
    ans += not dfs(graph, a, b)
print(ans)

Solution (Python):
N,M = list(map(int,input().split()))
lis_s =[]
count = 0
for _ in range(M):
  lis_s.append(tuple(map(int,input().split())))

graph = [[False for i in range(N+1)] for k in range(N+1)]

for tp in lis_s:
  graph[tp[0]][tp[1]] = True
  graph[tp[1]][tp[0]] = True


visited = [False]*(N+1)
bridge = False

def dfs(v):
  visited[v] = True
  for vs in range(1,N+1):
    if (graph[v][vs] == True) and (visited[vs] == False):
      dfs(vs)

ans = 0

for num in range(M):
  graph[lis_s[num][0]][lis_s[num][1]] = False
  graph[lis_s[num][1]][lis_s[num][0]] = False
  for i in range(N+1):
    visited[i] = False
  
  dfs(1)
  
  bridge = False
  for check in range(1,N+1):
    if visited[check] == False:
      bridge = True
  
  if bridge:
    ans += 1
  
  graph[lis_s[num][0]][lis_s[num][1]] = True 
  graph[lis_s[num][1]][lis_s[num][0]] = True
  
  
print(ans)

Solution (Python):
N, M = map(int, input().split())
G = [[False] * N for _ in range(N)]
A = []
B = []
C = [False] * N
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    A.append(a)
    B.append(b)
    G[a][b] = True
    G[b][a] = True


def dfs(v):
    C[v] = True
    for vv in range(N):
        if G[v][vv] is False:
            continue
        if C[vv] is True:
            continue
        dfs(vv)


def main():
    ans = 0
    for i in range(M):
        G[A[i]][B[i]] = False
        G[B[i]][A[i]] = False
        for j in range(N):
            C[j] = False
        dfs(0)
        G[A[i]][B[i]] = True
        G[B[i]][A[i]] = True
        if all(C) is False:
            ans += 1
            continue
    print(ans)


main()

Solution (Python):
N, M = map(int, input().split())
G = [[False] * N for _ in range(N)]
A = []
B = []
C = [False] * N
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    A.append(a)
    B.append(b)
    G[a][b] = True
    G[b][a] = True


def dfs(v):
    C[v] = True
    for vv in range(N):
        if G[v][vv] is False:
            continue
        if C[vv] is True:
            continue
        dfs(vv)


def main():
    ans = 0
    for i in range(M):
        G[A[i]][B[i]] = False
        G[B[i]][A[i]] = False
        for j in range(N):
            C[j] = False
        dfs(0)
        G[A[i]][B[i]] = True
        G[B[i]][A[i]] = True
        if all(C) is False:
            ans += 1
            continue
    print(ans)


main()

Solution (Python):
n , m =  [ int(v) for v in input().split() ]
connect_matrix = [ [0 for j in range(n)] for i in range(n)]
breaking_list = []
for i in range(m):
    a, b = [ int(v)-1 for v in input().split() ]
    connect_matrix[a][b] = 1
    connect_matrix[b][a] = 1
    breaking_list.append((a,b))




def connect_check(intuple):
    global connect_matrix,n
    p, q = intuple[0], intuple[1]

    connect_matrix2 = [ [connect_matrix[i][j] for j in range(n)] for i in range(n)]
    arriving_list =  [ set([i]) for i in range(n)]
    connect_matrix2[p][q] = 0
    connect_matrix2[q][p] = 0

    
    for k in range(6):
        new_connect_matrix2 = []
        for i in range(n):
            templist = [ j for j in range(n) if connect_matrix2[i][j] > 0 and j not in arriving_list[i]]

            newlist = [ connect_matrix2[i][j] for j in range(n) ]
            for j in templist:
                newlist = [ newlist[h] | connect_matrix2[j][h] for h in range(n) ]
                arriving_list[i].add(j)
            
            new_connect_matrix2.append(newlist)
        connect_matrix2 = new_connect_matrix2


    
    if { i for i in range(n) } not in arriving_list:
        ret = 1
    else:
        ret = 0
    return ret

ans = 0
for i in breaking_list:
    ans += connect_check(i)

print(ans)

Solution (Python):
l = input().split()
N = int(l[0])
M = int(l[1])

C = []

for i in range(M):
    l = input().split()
    C.append([int(x) - 1 for x in l])



def visit(s, G, visited):
    
    visited.add(s)
    for g in G:
        if g[0] in visited:
            n = g[1]
            G.remove(g)
            return visit(n, G, visited)
        elif g[1] in visited:
            n = g[0]
            G.remove(g)
            return visit(n, G, visited)
    return

ans = 0
for i in range(M):
    D = []
    for j in range(M):
        if i != j:
            D.append(C[j])
    visited = set()
    visit(0, D, visited)
    
    if len(visited) != N:
        ans += 1

print(ans)

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

def judge(ab,idx):
    memo = [True] * (N+1)
    al = [[] for _ in range(N+1)]
    for i in range(M):
        if i == idx:continue
        al[ab[i][0]].append(ab[i][1])
        al[ab[i][1]].append(ab[i][0])
            
    child = al[ab[idx][1]]
    memo[ab[idx][1]] = True
    while child:
        pi = child.pop()
        if memo[pi]:
            memo[pi] = False
        else:
            continue
        child = child + al[pi]
        
    if memo[ab[idx][0]] == True:
        return False
    else:
        return True
    
    
    
cnt = 0
for i in range(M):
    if not judge(ab,i):
        cnt += 1
        

print(cnt)

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

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

    def find(self, x):
        if self.par[x] == x:
            return x
        
        self.par[x] = self.find(self.par[x])
        return self.par[x]
    
    def unite(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
    
    def check_root(self, x, y):
        return self.find(x) == self.find(y)

ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j, e in enumerate(E):
        if j != i:
            uf.unite(e[0]-1, e[1]-1)
    
    if not uf.check_root(E[i][0]-1, E[i][1]-1):
        ans += 1

print(ans)

Solution (Python):
from collections import defaultdict

def main():
    node_num, edge_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(edge_num)]

    ans = 0

    for i in range(edge_num):
        dic_graph = defaultdict(set)
        for j in range(edge_num):
            if i == j:
                continue
            dic_graph[data[j][0]].add(data[j][1])
            dic_graph[data[j][1]].add(data[j][0])
        if check(dic_graph, node_num):
            ans += 1

        

    print(ans)

def check(dic_graph, node_num):
    visit_data = [0 for i in range(node_num + 1)]
    visit_data[0] = 1
    visit_data[1] = 1

    now_point = set()
    next_point = set()
    now_point.add(1)

    while len(now_point) > 0:
        for ele in now_point:
            next_data = dic_graph[ele]
            for next_ele in next_data:
                if visit_data[next_ele]:
                    continue
                next_point.add(next_ele)
                visit_data[next_ele] = 1
        now_point = next_point
        next_point = set()

    


    if 0 in visit_data:
        return 1
    else:
        return 0

if __name__ == '__main__':
    main()

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

class Bridge:
    def __init__(self, nodeA, nodeB):
        self.edges = [BridgeEdge(nodeA), BridgeEdge(nodeB)]

class BridgeEdge:
    def __init__(self, node):
        self.node = node
        self.judge = 0

class Node:
    def __init__(self, id):
        self.id = id
        self.bridges = []
    def addEdge(self, bridgeEdge):
        self.bridges.append(bridgeEdge)


nodes = [Node(i) for i in range(N+1)]
bridges = []
for A, B in (map(int, input().split()) for _ in range(M)):
    b = Bridge(nodes[A], nodes[B])
    nodes[A].addEdge(b.edges[1])
    nodes[B].addEdge(b.edges[0])
    bridges.append(b)


s = [(None, nodes[1])]
idx = 0
while idx < len(s):
    pre, cur = s[idx]
    idx += 1

    for nxt in cur.bridges:
        if not pre is nxt.node and nxt.judge < 2:
            nxt.judge += 1
            s.append((cur, nxt.node))

cnt = 0
for bd in bridges:
    if sum(1 for b in bd.edges if b.judge <= 1) > 0:
        cnt += 1

print(cnt)