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 = [[int(i) for i in input().split()] for j in range(m)]

limit = 60

vis = [False]*(n+2)
graph = [[False for i in range(n+2)] for j in range(n+2)]

def dfs(x):
    vis[x] = True
    for i in range(1,n+1):
        if graph[x][i] == False:
            continue
        if vis[i] == True:
            continue
        
        dfs(i)

for i in range(m):
    graph[ab[i][0]][ab[i][1]] = True
    graph[ab[i][1]][ab[i][0]] = True

bridge = 0

ans = 0

for i in range(m):
    vis = [False]*(n+2)
    graph[ab[i][0]][ab[i][1]] = False
    graph[ab[i][1]][ab[i][0]] = False
    
    dfs(1)
    
    
    
    bridge = False
    for j in range(1,n+1):
        if vis[j] == False:
            bridge = True
    if bridge:
        ans += 1
    
    graph[ab[i][0]][ab[i][1]] = True
    graph[ab[i][1]][ab[i][0]] = True

print(ans)

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

count=0
for i in range(m):
    u,v=map(int,input().split())
    u-=1
    v-=1
    g[u].append(v)
    g[v].append(u)
    x[i]=[u,v]
memo=[False for i in range(n)]
memo[0]=True


def dfs(now,prev):
    for next in g[now]:        
        if next!=prev:
            if memo[next]==True:
                continue
            else:
                memo[next]=True
                dfs(next,now)


for i in range(m):
    g[x[i][0]].remove(x[i][1])
    g[x[i][1]].remove(x[i][0])
    dfs(0,0)
    if memo.count(False)>=1:
        count+=1
    g[x[i][0]].append(x[i][1])
    g[x[i][1]].append(x[i][0])
    memo=[False for i in range(n)]
    memo[0]=True
    
print(count)

Solution (Python):
 

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

count=0
for i in range(m):
    u,v=map(int,input().split())
    u-=1
    v-=1
    g[u].append(v)
    g[v].append(u)
    x[i]=[u,v]
memo=[False for i in range(n)]
memo[0]=True

def dfs(now,prev):
    for next in g[now]:
        
        if next!=prev:
            if memo[next]==True:
                continue
            else:
                memo[next]=True
                dfs(next,now)


for i in range(m):
    g[x[i][0]].remove(x[i][1])
    g[x[i][1]].remove(x[i][0])
    dfs(0,0)
    if memo.count(False)>=1:
        count+=1
    g[x[i][0]].append(x[i][1])
    g[x[i][1]].append(x[i][0])
    memo=[False for i in range(n)]
    memo[0]=True
print(count)

Solution (Python):
import sys
input=sys.stdin.readline
import math

def get_edges_include_node(i, Edges): 
    es = []
    for e in Edges:
        if i in e:
            es.append(e)
    return es

def dfs(i, e0, goal, Edges): 
    if e0 in Edges:
        Edges.remove(e0)
    for e1 in get_edges_include_node(i, Edges):
        if goal in e1:
            return True
        else:
            ni = e1[1] if e1[0] == i else e1[0]
            if dfs(ni, e1, goal, Edges):
                return True                
    return False
def main():

    N,M = map(int, input().split())
    Edges = []
    for _ in range(M):
        a,b = map(int, input().split())
        Edges.append((a,b))
    ans = 0
    for e in Edges:
        tmp = []
        for e2 in Edges:
            tmp.append((e2[0], e2[1]))
        if not dfs(e[0], e, e[1], tmp):
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1 for _ in range(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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

bridge = 0

for i in range(m):
    ins = UnionFind(n)
    for j in range(m):
        if j == i:
            continue
        if not ins.same_check(ab[j][0],ab[j][1]):
            ins.union(ab[j][0],ab[j][1])
        
    
    if ins.size[ins.find(ab[0][0])] != n:
        bridge += 1
        
print(bridge)

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

def dfs(n) :
    queue = [0]
    visited = [False] * N
    visited[0] = True
    counter = 1
    while queue :
        cur = queue.pop()
        for nex, i in v[cur] :
            if i == n : 
                continue
            if not visited[nex] :
                counter += 1
                queue.append(nex)
                visited[nex] = True
    
    return counter != N

ret = 0
for i in range(M) :
    if dfs(i) :
        ret += 1
print(ret)

Solution (Python):
N,M=map(int,input().split())
h=[list(map(int, input().split())) for i in range(M)]
a=0
def s(n,m,l):
    for j in range(n,m):
        if l[h[j][0]-1] or l[h[j][1]-1]:
            l[h[j][0]-1],l[h[j][1]-1]=1,1
    return(l)
for i in range(M):
    l=[1]+[0]*(N-1)
    for _ in range(N-1):
        l=s(0,i,l)
        l=s(i+1,M,l)
    if 0 in l:
        a+=1
print(a)

Solution (Python):
import collections
def main():
    N, M = map(int, input().split())
    graph = collections.defaultdict(list)
    for _ in range(M):
        a, b = [int(c) for c in input().split()]
        graph[a].append(b)
        graph[b].append(a)

    count = 0
    for a in graph:
        for b in graph[a]:
            if a < b:
                start, goal = a, b
                cur = [start]
                visited = set([start])
                isFound = False
                while cur and not isFound:
                    temp = []
                    for c in cur:
                        for d in graph[c]:
                            if [c, d] != [a, b] and d not in visited:
                                if d == goal:
                                    isFound = True
                                    break
                                visited.add(d)
                                temp.append(d)
                        if isFound:
                            break
                        cur = temp
                if not isFound:
                    count += 1
    return count

if __name__ == '__main__':
    print(main())

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import floyd_warshall

inf=10**9
n, m=map(int,input().split())
g1=np.ones((n,n),dtype=int) * inf

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

ans=0
for a,b in bridge:
    graph=np.copy(g1)
    graph[a][b]=inf
    graph[b][a]=inf
    graph=floyd_warshall(graph)
    if inf in graph:
        ans+=1

print(ans)

Solution (Python):
from collections import defaultdict
from collections import deque
N, M = map(int, input().split())
D = defaultdict(list)
Edge = []
for i in range(M):
  A, B = map(int, input().split())
  D[A-1].append(B-1)
  D[B-1].append(A-1)
  Edge.append((A-1, B-1))
def dfs(n, vstd, i):
  vstd.add(n)
  for a in D[n]:
    if a not in vstd and (a, n) != i and (n,a) != i:
      dfs(a, vstd, i)
  return len(vstd)

cnt = 0
for i in Edge:
  if dfs(0, set(), i) < N:
    cnt += 1
print (cnt)

Solution (Python):



import sys
from copy import deepcopy

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(v: int) -> None:
    seen[v] = 1  
    for u in g[v]:
        if not seen[u]:
            dfs(u)


def main():  
    global g, seen
    N, M = tuple(map(int, input().split()))
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    G = [[] for _ in range(N + 1)]  
    for v, u in E:  
        G[v] += [u]
        G[u] += [v]
    bridges = 0
    for v, u in E:
        g = deepcopy(G)  
        g[v].remove(u)
        g[u].remove(v)
        seen = [0] * (N + 1)
        dfs(1)  
        bridges += 1 if 0 in seen[1:] else 0
    print(bridges)


if __name__ == "__main__":
    main()

Solution (Python):



import sys
from copy import deepcopy

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(v: int, g: "List[List[int]]", seen: "List[int]") -> None:
    seen[v] = 1  
    for u in g[v]:
        if not seen[u]:
            dfs(u, g, seen)


def main():
    N, M = tuple(map(int, input().split()))
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    G = [[] for _ in range(N + 1)]
    for v, u in E:  
        G[v] += [u]
        G[u] += [v]
    bridges = 0
    for v, u in E:
        g = deepcopy(G)  
        g[v].remove(u)
        g[u].remove(v)
        seen = [0] * (N + 1)
        dfs(1, g, seen)
        bridges += 1 if 0 in seen[1:] else 0
    print(bridges)


if __name__ == "__main__":
    main()

Solution (Python):
class UnionFind():
    
    
    def __init__(self, n):
        self.n = n
        
        
        self.root = [-1]*(n+1)
        
        self.rnk = [0]*(n+1)

    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return 
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
import copy
n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
ans=0
for i in range(m):
    ltmp=copy.deepcopy(l)
    ltmp=ltmp[:i]+ltmp[i+1:]
    UF=UnionFind(n)
    for j in ltmp:
        UF.Unite(j[0]-1,j[1]-1)
    if UF.Count(0)!=n:ans+=1
print(ans)

Solution (Python):
N, M = map(int, input().split())
 
lines = []
for _ in range(M):
	lines.append(list(map(lambda x: int(x) - 1, input().split())))
 
def root(x):
	if par[x] == x:
		return x
	
	par[x] = root(par[x])
	return par[x]
 
def unite(x, y):
	rx = root(x)
	ry = root(y)
	if rx != ry:
		par[rx] = ry
 
def same(x, y):
	rx = root(x)
	ry = root(y)
	return rx == ry
 
 
ans = 0
 
for i in range(M):
	par = [x for x in range(N)]
	
	for j in range(M):
		if i != j:
			unite(lines[j][0], lines[j][1])
	
	flag = True
	for j in range(1, N):
		if not same(0, j):
			flag = False
	if not flag:
		ans += 1
 
print(ans)

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

lines = []
for _ in range(M):
	lines.append(list(map(lambda x: int(x) - 1, input().split())))

def root(x):
	if par[x] == x:
		return x
	
	par[x] = root(par[x])
	return par[x]

def unite(x, y):
	rx = root(x)
	ry = root(y)
	if rx != ry:
		par[rx] = ry

def same(x, y):
	rx = root(x)
	ry = root(y)
	return rx == ry


ans = 0

for i in range(M):
	par = [x for x in range(N)]
	
	for j in range(M):
		if i != j:
			unite(lines[j][0], lines[j][1])
	
	flag = True
	for j in range(1, N):
		if not same(0, j):
			flag = False
	if not flag:
		ans += 1

print(ans)

Solution (Python):
from collections import deque

N, M = map(int, input().split())
AB = []
for _ in range(M):
    a, b = map(int, input().split())
    AB.append((a - 1, b - 1))
ans = 0
for i in range(M):
    to = [[] for _ in range(N)]
    for j, (a, b) in enumerate(AB):
        if i != j:
            to[a].append(b)
            to[b].append(a)
    visited = [False] * N
    q = deque()
    q.append(0)
    visited[0] = True
    while len(q):
        a = q.pop()
        for b in to[a]:
            if not visited[b]:
                q.append(b)
                visited[b] = True
    if not all(visited):
        ans += 1
print(ans)

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

def create_dict(ab_list):
    d = {}
    for a,b in ab_list:
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
            
    return d


cnt = 0

for i in range(M):

    tmp_ab_list = ab_list[:i] + ab_list[i+1:]

    d = create_dict(tmp_ab_list)

    connected = [0 for _ in range(N+1)]

    def write_connected(a):

        if connected[a] == 0:
            connected[a] = 1
            if a in d:
                for next_a in d[a]:
                    write_connected(next_a)

    write_connected(1)


    if sum(connected) < N:
        cnt += 1


print(cnt)

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)

Solution (Python):


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

list_adjlist = [[] for _ in range(N + 1)]

list_edge = []

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

def FIFO(list_FIFO, node):
    if node != None:
        list_FIFO.append(node)
        return None
    return list_FIFO.pop(0)


all_bridge = 0


for u, v in list_edge:
    
    uv_bridge = 1
    
    list_FIFO = []
    
    list_check = [False] * (N + 1)
    
    FIFO(list_FIFO, u)
    
    list_check[u] = True
    
    while list_FIFO != [] and list_FIFO[-1] != v:
        
        node = FIFO(list_FIFO, None)
        
        for adjnode in list_adjlist[node]:
            
            if list_check[adjnode]:
                
                continue
            
            if adjnode == v:
                
                if node != u:  
                    
                    uv_bridge = 0
                    
                    FIFO(list_FIFO, adjnode)
                    
                    break
            
            else:
                
                FIFO(list_FIFO, adjnode)
                
                list_check[adjnode] = True
    
    all_bridge += uv_bridge
                

print(all_bridge)

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

ans = 0

for i in range(M):
    brid = [[] for _ in range(N)]
    check = [0] * N
    for j in range(M):
        if j != i:
            brid[a[j]-1].append(b[j]-1)
            brid[b[j]-1].append(a[j]-1)



    stack = []
    for j in range(len(brid[0])):
        stack.append(brid[0][j])
        check[brid[0][j]] == 1
    
    while len(stack) != 0 :
        x = stack.pop(-1)
        for j in range(len(brid[x])):
            if check[brid[x][j]] == 0:
                stack.append(brid[x][j])
                check[brid[x][j]] = 1
    


    if check.count(1) != len(check):
        ans += 1


print(ans)

Solution (Python):
import os
import sys

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
A, B = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(M)]))
A = np.array(A) - 1
B = np.array(B) - 1


def is_bridge(i):
    a = np.concatenate([A[:i], A[i + 1:]])
    b = np.concatenate([B[:i], B[i + 1:]])
    graph = csr_matrix(([True] * (M - 1), (a, b)), shape=(N, N))
    _, components = connected_components(graph, directed=False)
    return components.max() >= 1


ans = 0
for i in range(M):
    ans += is_bridge(i)
print(ans)

Solution (Python):
import queue

N, M = map(int, input().split())
adjacent = [[False] * N for i in range(N)]
bridges = []
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    bridges.append((a, b))
    adjacent[a][b] = adjacent[b][a] = True

ans = 0
for a, b in bridges:
    adjacent[a][b] = adjacent[b][a] = False
    visited = [0] * N

    visited[0] = 1
    q = queue.Queue()
    q.put(0)
    while not q.empty():
        u = q.get()
        for v in range(N):
            if not adjacent[u][v]:
                continue
            if visited[v] == 1:
                continue
            visited[v] = 1
            q.put(v)

    if sum(visited) < N:
        ans += 1
    adjacent[a][b] = adjacent[b][a] = True
print(ans)

Solution (Python):
from scipy.sparse import*;N,M,*A=map(int,open(0).read().split());g=csr_matrix(([1]*M,(A[::2],A[1::2])),shape=(N+1,N+1)).tolil();c=0
for a,b in zip(*g.nonzero()):g[a,b]=0;n,_=csgraph.connected_components(g);c+=n!=2;g[a,b]=1
print(c)

Solution (Python):
from scipy.sparse import *;N,M,*A=map(int,open(0).read().split());g=csr_matrix(([1]*M,(A[::2],A[1::2])),shape=(N+1,N+1)).tolil();c=0
for a,b in zip(*g.nonzero()):
 g[a,b]=0;n,_=csgraph.connected_components(g);c+=n!=2;g[a,b]=1
print(c)

Solution (Python):
from scipy.sparse import *;from scipy.sparse.csgraph import connected_components;N,M=map(int,input().split());g=lil_matrix((N,N))
for _ in [0]*M:
  a,b=list(map(int,input().split()));g[a-1,b-1]=1
c=0
for a,b in zip(*g.nonzero()):
  g[a,b]=0;c+=connected_components(g,return_labels=False)!=1;g[a,b]=1
print(c)

Solution (Python):
from scipy.sparse import lil_matrix
from scipy.sparse.csgraph import connected_components

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

g = lil_matrix((N, N))
for _ in range(M):
  a, b = list(map(int, input().split()))
  g[a - 1, b - 1] = 1

c = 0
for a, b in zip(*g.nonzero()):
  g[a, b] = 0
  c += connected_components(g, return_labels=False) != 1
  g[a, b] = 1
  
print(c)

Solution (Python):

class uf_tree():

    def __init__(self,n):
        self.n = n
        self.par = [i for i in range(n)]

    def indep(self):
        dep =0
        for i in range(self.n):
            if i == self.par[i]:
                dep += 1

        return dep

    def unite(self,child,mas):
        if self.root(child) == self.root(mas):
            return
        else:
            self.par[self.root(child)] = self.root(mas)

    def root(self,i):
        if self.par[i] == i:
            return i
        else:
            self.par[i] = self.root(self.par[i])
            return self.par[i]

    def same(self,x,y):
        if self.root(x) == self.root(y):
            return True
        else:
            return False
n,m = map(int,input().split())
arr = [[0 for i in range(n)] for j in range(n)]
e = set()
ans = 0
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    e.add((a,b))

for el in e:
    tree = uf_tree(n)
    for key in e:
        if key != el:
            tree.unite(key[0],key[1])
    if tree.indep() > 1:
        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)

Solution (Python):
from heapq import heappop,heappush
n,m = map(int,input().split())
edge = [[] for _ in range(n)]
del_edge = []
cnt = 0

for _ in range(m):
    a,b = map(int,input().split())
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)
    del_edge.append((a,b))

def find(s,de):
    visited = [False] * n
    visited[s] = True
    que = []
    for e in edge[s]:
        if s in de and e in de:
            continue
        heappush(que,e)
    while que:
        v = heappop(que)
        if visited[v]:
            continue
        visited[v] = True
        for vtx in edge[v]:
            if v in de and vtx in de:
                continue
            hq = vtx
            heappush(que,hq)
    if False in visited:
        return 1
    else:
        return 0

for i in range(m):
    tmp = del_edge[i]
    cnt += find(0,tmp)

print(cnt)

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

g = [[0] * N for _ in range(N)]
for i, j in l:
  g[i - 1][j - 1] = 1
  g[j - 1][i - 1] = 1

def dfs(n):
  v[n - 1] = 1
  for n2 in range(1, N + 1):
    if g[n - 1][n2 - 1] == 1 and v[n2 - 1] == 0:
      dfs(n2)

r = 0
for i, j in l:
  g[i - 1][j - 1] = 0
  g[j - 1][i - 1] = 0
  
  v = [0] * N
  dfs(i)
  if sum(v) != N:
    r += 1
  
  g[i - 1][j - 1] = 1
  g[j - 1][i - 1] = 1
  
print(r)

Solution (Python):
from collections import deque

N, M = map(int, input().split())
edges = []

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

ans = 0
for removeEdge in range(M):
    confilm = [False for _ in range(N)]
    que = deque([])
    que.append(0)

    while que:
        now = que.popleft()
        confilm[now] = True
        for i, (a, b) in enumerate(edges):
            if i == removeEdge:
                continue
            if a == now:
                if not confilm[b]:
                    que.append(b)
            if b == now:
                if not confilm[a]:
                    que.append(a)
    if False in confilm:
        ans += 1

print(ans)

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

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)
    edges[to].append(fr)

leafList = set([])
ans = 0
while True:
    isAll = True
    for v in range(N):
        if v in leafList:
            continue
        edgeCount = 0
        for to in edges[v]:
            if to in leafList:
                continue
            edgeCount += 1
        if edgeCount == 1:
            isAll = False
            ans += 1
            leafList.add(v)
    if isAll:
        break
print(ans)

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

def dfs(x):
    global v
    v.append(x)
    for k in range(n):
        global i
        if ab[x][k] == 1 and not k in v:
            dfs(k)
count = 0
for i in range(m):
    ab[eda[i][0]][eda[i][1]] = 0
    ab[eda[i][1]][eda[i][0]] = 0
    v = []
    dfs(0)
    if len(v) != n:
        count += 1
    ab[eda[i][0]][eda[i][1]] = 1
    ab[eda[i][1]][eda[i][0]] = 1
print(count)

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

paths = [[0] * (N + 1) for _ in range(N + 1)]

edges = []
for i in range(M):
    a, b = [int(_) for _ in input().split()]
    paths[a][b] = 1
    paths[b][a] = 1
    edges.append((a, b))


class UF:
    def __init__(self, v):
        self.parent = None
        self.val = v

    @property
    def root(self):
        if not self.parent:
            return self
        return self.parent.root

    def __str__(self):
        if self.parent:
            return str(self.val) + ' ' + str(self.parent.val)
        return str(self.val) + ' None'


def merge(u1, u2):
    r1 = u1.root
    r2 = u2.root
    if r1 == r2:
        return
    r1.parent = r2


def chk(a, b):
    nodes = [UF(i) for i in range(N + 1)]
    for i in range(1, N):
        for j in range(i + 1, N + 1):
            if paths[i][j]:
                merge(nodes[i], nodes[j])
    return int(nodes[a].root != nodes[b].root)


ans = 0
for e in edges:
    paths[e[0]][e[1]] = 0
    paths[e[1]][e[0]] = 0
    ans += chk(e[0], e[1])
    paths[e[0]][e[1]] = 1
    paths[e[1]][e[0]] = 1
print(ans)

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

paths = [[0] * (N + 1) for _ in range(N + 1)]


def has_path(c, t, arrived):
    if c == t: return True
    for i in range(1, N + 1):
        if i in arrived: continue
        if paths[c][i]:
            arrived.append(i)
            if has_path(i, t, arrived):
                return True
            arrived.pop()
    return False


edge = []
for i in range(M):
    a, b = [int(_) for _ in input().split()]
    paths[a][b] = 1
    paths[b][a] = 1
    edge.append((a, b,))

ans = 0
for e in edge:
    paths[e[0]][e[1]] = 0
    paths[e[1]][e[0]] = 0
    if not has_path(e[0], e[1], []):
        ans += 1
    paths[e[0]][e[1]] = 1
    paths[e[1]][e[0]] = 1
print(ans)

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

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

def rec(now, i):
    seen[now] = True
    for e in edges[now]:
        if e[1] == i:
            continue
        if seen[e[0]]:
            continue
        rec(e[0], i)


ans = 0
for i in range(m):
    seen = [False for i in range(n)]
    rec(0, i)
    if False in seen:
        ans += 1

print(ans)

Solution (Python):
n,m = map(int,input().split())
raw = []
ans = 0
for i in range(m):
  raw.append(list(map(lambda x:int(x)-1,input().split())))
for i in range(m):
  ab = [[] for _ in range(n)]
  for mi in range(m):
    if mi != i:
      try:
        here = raw[mi]
        ab[here[0]].append(here[1])
        ab[here[1]].append(here[0])
      except:
        print(ab,here,here[0],here[1])
  for ni in range(n):
    now = [ni]
    rest = [j for j in range(n)]
    for _ in range(50):
      nex = []
      for x in now:
        if x in rest:
          rest.remove(x)
        nex += ab[x]
      now = list(set(nex))
      if rest == []:
        break
    else:
      continue
    break
  else:
    ans += 1
print(ans)

Solution (Python):
def c_bridge(N, M, Edges):
    def dfs(v):
        is_visited[v] = True  
        for v2 in range(N):
            if not graph[v][v2] or is_visited[v2]:
                continue  
            dfs(v2)

    graph = [[False for _ in range(N)] for _ in range(N)]
    for a, b in Edges:
        graph[a - 1][b - 1] = True
        graph[b - 1][a - 1] = True

    
    ans = 0
    for a, b in Edges:
        
        graph[a - 1][b - 1] = False
        graph[b - 1][a - 1] = False

        
        is_visited = [False for _ in range(N)]
        
        dfs(0)
        ans += 1 if not all(is_visited) else 0

        
        graph[a - 1][b - 1] = True
        graph[b - 1][a - 1] = True
    return ans

N, M = [int(i) for i in input().split()]
Edges = [[int(i) for i in input().split()] for j in range(M)]
print(c_bridge(N, M, Edges))

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N, M = LI()
A, B = [], []
for i in range(M):
    a, b = LI()
    A.append(a)
    B.append(b)

"""
頂点ごとにみる。
その頂点につながっている辺を洗い出す
洗い出した辺の頂点同士がつながっているか確認する
最終的に自分のもとに戻ってこれるか。
dfsで全経路を洗い出す
1とそれ以外が全部つながるか。
2とそれ以外が全部つながるかを調査すればよい
"""





















def dfs(visited_nodes, lines):
    print(visited_nodes, file=sys.stderr)
    if len(set(visited_nodes)) == N:
        print('False',file=sys.stderr)
        return False
    
    for l in lines:
        if l[0] in visited_nodes or l[1] in visited_nodes:
            if not (l[0] in visited_nodes and l[1] in visited_nodes):
                return dfs(visited_nodes + l, lines)
    else:
        
        print('True', file=sys.stderr)
        return True


ans = 0
for idx in range(M):
    
    lines = []
    for m in range(M):
        if m == idx:
            continue
        else:
            lines.append([A[m], B[m]])
    print('idx, lines', idx, lines, file=sys.stderr)
    
    
    
    if len(lines) == 0:
        print(1)
        exit()
    if dfs(lines[0], lines):
        ans += 1
print(ans)

Solution (Python):
import queue

n, m = map(int, input().split())
ab = [[] for i in range(n)]
A = []
B = []

for i in range(m):
    a, b = map(int, input().split())
    a-=1
    b-=1
    ab[a].append(b)
    ab[b].append(a)
    A.append(a)
    B.append(b)

def bfs(ab, n, na, nb):
    ok = [False for i in range(n)]
    q = queue.Queue()
    q.put(0)
    while not q.empty():
        f = q.get()
        ok[f] = True
        for c in ab[f]:
            if (f==na and c==nb) or (f==nb and c==na):
                continue
            if ok[c] == False:
                q.put(c)
    
    flag = True
    for i in ok:
        flag &= i
    return flag

ans = 0
for a, b in zip(A, B):
    if bfs(ab, n, a, b) == False:
        ans += 1

print(ans)

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

es = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(m)]

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

    def root(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def is_same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        else:
            self.parent[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
        self.count += 1


ans = 0
for i in range(m):
    uf = UnionFind(n)
    for j, (a, b) in enumerate(es):
        if i == j:
            continue 
        if uf.is_same(a, b):
            continue 
        uf.unite(a, b)
    x, y = es[i]
    if not uf.is_same(x, y):
        ans += 1 

print(ans)