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):
from copy import deepcopy
from collections import deque
N, M = map(int, input().split())
adj_mat = [[-float('inf') for i in range(N)] for j in range(N)]
ls = []
for i in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    ls.append([a, b])
    adj_mat[a][b], adj_mat[b][a] = 1, 1

ans = 0
for i in range(M):
    adj_mat_copy = deepcopy(adj_mat)
    adj_mat_copy[ls[i][0]][ls[i][1]] = -float('inf')
    adj_mat_copy[ls[i][1]][ls[i][0]] = -float('inf')
    st = deque([])
    visited = [-1 for i in range(N)]
    st.append(0)
    visited[0] = 1
    while st:
        l = st.pop()
        for j, node in enumerate(adj_mat_copy[l]):
            if node == 1 and visited[j] != 1:
                st.append(j)
                visited[j] = 1
    if sum(visited) != N:
        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):
N, M = map(int, input().split())
G = [[] for _ in range(N)]
edges = []
for _ in range(M):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)
    edges.append([a - 1, b - 1])

def dfs(u, seen, e):
    seen[u] = True
    for v in G[u]:
        if seen[v] == True:
            continue
        if [u, v] == e or [v, u] == e:
            continue
        dfs(v, seen, e)

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

print(ans)

Solution (Python):
from collections import deque
n,m = tuple(map(int,input().split()))

edges = []

for _ in range(m):
  edges.append(tuple(map(int,input().split())))

ans = 0
for i in range(m):
  g = [[] for _ in range(n)]
  for j,e in enumerate(edges):
    if i==j:
      continue
    a,b = e
    a,b = a-1,b-1
    g[a].append(b)
    g[b].append(a)
    
  checked = [False]*n
  queue = deque([0])
  while(len(queue)>0):
    q = queue.popleft()
    if checked[q]:
      continue
    checked[q] = True
    for p in g[q]:
      queue.append(p)
  if not all(checked):
    ans+=1
print(ans)

Solution (Python):
from collections import deque

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

E = [[int(x) - 1 for x in input().split()] for _ in range(M)]

ans = 0
for i in range(M):
    G = [[] for _ in range(N)]
    for j in range(M):
        if i==j:
            continue
        a, b = E[j]
        G[a].append(b)
        G[b].append(a)


    que = deque([0])

    check = [-1 for _ in range(N)]

    while que:
        v = que.popleft()
        check[v] = 0
        for i in G[v]:
            if check[i] == -1:
                que.append(i)
    if sum(check) < 0:
        ans += 1
print(ans)

Solution (Python):
from collections import deque
n,m=map(int,input().split())
l=[[] for _ in range(n)]
edge=[]
ans=0
for _ in range(m):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)
  edge.append([a-1,b-1])
for i,j in edge:
  q=deque([i])
  visited=[0]*n
  while q:
    x=q.pop()
    if x==j:
      break
    visited[x]=1
    for k in l[x]:
      if visited[k]==0 and not (x==i and k==j):
        q.append(k)
  else:
    ans+=1
print(ans)

Solution (Python):
import sys

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def S(): return sys.stdin.readline().rstrip()

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

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

ans = 0
for i in range(M):
    a,b = ab[i]
    unionfind = UnionFind(N)
    for j in range(M):
        if j == i:
            continue
        else:
            unionfind.unite(ab[j][0],ab[j][1])
    if not unionfind.same_check(a,b):
        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())
ab = [list(map(int,input().split())) for _ in range(M)]
r = 0

for z in range(M):
  uf = UnionFind(N)
  for i in range(M):
    if z == i:
      continue
    uf.union(ab[i][0]-1,ab[i][1]-1)
  r += uf.group_count()-1

print(r)

Solution (Python):

def solve(pos):
  for i in range(n):
    if line[pos][i] == 1 and reach[i] == 0:
      reach[i] = 1
      solve(i)
  return

n, m = list(map(int, input().split()))
line = [[0]*n for i in range(n)]
ms = []

for i in range(m):
  a, b = list(map(int, input().split()))
  line[a-1][b-1]=1
  line[b-1][a-1]=1
  ms.append([a, b])
  
ans = 0
for i in range(m):
  line[ms[i][0]-1][ms[i][1]-1]=0
  line[ms[i][1]-1][ms[i][0]-1]=0
  reach=[0]*n
  reach[0]=1
  solve(0)
  if 0 in reach:
    ans += 1
  line[ms[i][0]-1][ms[i][1]-1]=1
  line[ms[i][1]-1][ms[i][0]-1]=1
print(ans)

Solution (Python):
from collections import deque
import copy

n, m = map(int, input().split())
arr = [[False] * 60 for x in range(60)]
ab = []

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


def dfs(x):
    if visited[x]:
        return
    else:
        visited[x] = True
        for i in range(n):
            if graph[x][i]:
                dfs(i)


connected = [True] * m
for i in range(m):
    graph = copy.deepcopy(arr)
    graph[ab[i][0]][ab[i][1]] = False
    graph[ab[i][1]][ab[i][0]] = False
    visited = [False] * 60
    dfs(0)

    for j in range(n):
        if not visited[j]:
            connected[i] = False
            break


print(m - sum(connected))

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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 main():
    N, M = map(int, readline().split())
    AB = [[int(s) - 1 for s in line.split()] for line in readlines()]

    ans = 0
    for i in range(M):
        uf = UnionFind(N)
        for j, (a, b) in enumerate(AB):
            if i == j:
                continue
            uf.union(a, b)
        if uf.group_count() > 1:
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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 main():
    N, M = map(int, readline().split())
    AB = [[int(s) - 1 for s in line.split()] for line in readlines()]

    ans = 0
    for i in range(M):
        uf = UnionFind(N)
        for j, (a, b) in enumerate(AB):
            if i == j:
                continue
            uf.union(a, b)
        if uf.group_count() > 1:
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):





import math
import sys
import bisect
import heapq  
import collections
from collections import deque

inf = 10**18
mod = 10**9+7

n,m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
edge = [[]for k in range(n)]
for i in range(m):
    a,b = ab[i]
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
ans = 0
for i in range(m): 
    s,g = ab[i]
    s-=1
    g-=1
    visited = [False for j in range(n)]
    q = deque([s])
    while q:
        now = q.popleft()
        visited[now]=True
        for nn in edge[now]:
            if (now!=s or nn!=g) and (not visited[nn]):
                q.append(nn)
    if not all(visited):
        ans += 1
print(ans)

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

def dfs(pos):
  if visit[pos] == 1:
    return
  visit[pos] = 1
  
  for i in range(n):
    if graph[pos][i] == 1:
      dfs(i)

count = 0
for hen in range(m):
  graph = [[0]*n for i in range(n)]
  visit = [0]*n

  for i in range(m):
    pos1 = data[i][0] - 1
    pos2 = data[i][1] - 1
    if i != hen:
      graph[pos1][pos2] = 1
      graph[pos2][pos1] = 1
  dfs(0)
  connected = True
  for i in range(n):
    if visit[i] == 0:
      connected = False
  if not connected:
    count += 1
print(count)

Solution (Python):
from collections import deque

n, m = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(m)]
d = {i: [] for i in range(1, n+1)}
for a, b in L:
    d[a].append(b)
    d[b].append(a)
cnt = 0
for a, b in L:
    d[a].remove(b)
    d[b].remove(a)
    ds = {i: -1 for i in range(1, n+1)}
    ds[1] = 0
    q = deque([1])
    while q:
        t = q.popleft()
        for v in d[t]:
            if ds[v] < 0:
                ds[v] += 1
                q.append(v)
    if -1 in ds.values():
        cnt += 1
    d[a].append(b)
    d[b].append(a)
print(cnt)

Solution (Python):

import sys
sys.setrecursionlimit(10 ** 8)


def lowLink(N: int, Adj: list):
	articulation = []
	bridge = []
	order = [None] * N
	lowest = [1 << 100] * N

	def _dfs(cur, pre, k):
		order[cur] = lowest[cur] = k
		is_articulation = False
		cnt = 0
		for nxt in Adj[cur]:
			if order[nxt] is None:
				cnt += 1
				_dfs(nxt, cur, k + 1)
				if lowest[cur] > lowest[nxt]:
					lowest[cur] = lowest[nxt]
				is_articulation |= pre >= 0 and lowest[nxt] >= order[cur]
				if order[cur] < lowest[nxt]:
					if cur < nxt:
						bridge.append((cur, nxt))
					else:
						bridge.append((nxt, cur))
			elif nxt != pre and lowest[cur] > order[nxt]:
				lowest[cur] = order[nxt]
		is_articulation |= pre < 0 and cnt > 1
		if is_articulation:
			articulation.append(cur)

	"""
	kk = 0
	for i in range(N):
		if order[i] is None:
			kk = _dfs(i, -1, kk)
	"""
	_dfs(0, -1, 0)
	return articulation, bridge

def main():
	n,m,*L=map(int,open(0).read().split())
	con=[[] for _ in range(n)]
	for a,b in zip(*[iter(L)]*2):
		con[a-1].append(b-1)
		con[b-1].append(a-1)
	_,br=lowLink(n,con)
	print(len(br))

if __name__ == '__main__':
	main()

Solution (Python):
from collections import deque
n,m = map(int,input().split())
data = [[] for _ in range(n)]
hen = []
ans = 0
for _ in range(m):
    v,w = map(int,input().split())
    v -= 1
    w -= 1
    data[v].append(w)
    data[w].append(v)
    hen.append((v,w))
for i,j in hen:
    dq = deque([i])
    visited = [0]*n
    while dq:
        p = dq.pop()
        if p == j:
            break
        visited[p] = 1
        for k in data[p]:
            if (not visited[k]) and (not (p == i and k == j)):
                dq.append(k)
    else:
        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 same(self, x, y):
        return self.find(x) == self.find(y)

    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())


n, m = map(int, input().split())

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

ans = 0
for i in range(m):
    uf = UnionFind(n)
    for j, (a, b) in enumerate(edge):
        if i == j:
            continue
        uf.union(a, b)
    if uf.group_count() == 1:
        ans += 1

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


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

ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j, (a, b) in enumerate(bridge):
        if i == j:
            continue
        uf.union(a,b)
    if uf.group_count() == 2:
        ans += 1


print(ans)

Solution (Python):
a, b = map(int,input().split())
v = []
for _ in range(b):
    aa,bb = map(int, input().split())
    v.append([aa-1, bb-1])
res = 0
for i in range(b):
    visited = [False] * a
    curv = []
    for j in range(a):
        curv.append([])
    for j in range(b):
        if i == j:
            continue
        else:
            x, y = v[j]
            curv[x].append(y)
            curv[y].append(x)
    import collections
    q = collections.deque([])
    q.append(0)

    while len(q) > 0:
        curnode = q.pop()
        if visited[curnode] is True:
            continue

        visited[curnode] = True
        for j in range(len(curv[curnode])):
            nextnode = curv[curnode][j]
            if visited[nextnode] is False:
                q.append(nextnode)

    isbridge = False
    for j in range(a):
        if visited[j] is False:
            isbridge = True
    if isbridge:
        res += 1

print(res)

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

N,M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
I,J = zip(*edges)

g = coo_matrix(([1]*M, (I,J)), (N+1, N+1))
g = g.tolil()

ans = 0
for i,j in edges:
    g[i,j] = 0
    cnt, _ = connected_components(g, directed=False)
    g[i,j] = 1
    ans += (cnt > 2)
print(ans)

Solution (Python):
from collections import deque
def main():
    n, m = list(map(int, input().split()))
    G = [[] for _ in range(n)]
    L = []
    for _ in range(m):
        a, b = list(map(lambda x: int(x) - 1, input().split()))
        G[a].append(b)
        G[b].append(a)
        L.append(set([a, b]))
    ans = 0
    for l in L:
        stack = deque([0, ])
        visited = [False] * n
        while stack:
            x = stack.popleft()
            if visited[x]:
                continue
            visited[x] = True
            for dx in G[x]:
                if set([x, dx]) == l:
                    continue
                if not visited[dx]:
                    stack.append(dx)
        if not all(visited):
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self._n = n
        self._table = [-1]*n
        self._rank = [0]*n

    def _root(self, x):
        stack = []
        while self._table[x] >= 0:
            stack.append(x)
            x = self._table[x]
        for y in stack:
            self._table[y] = x
        return x
    
    def unite(self, x, y):
        x, y = self._root(x), self._root(y)
        if x == y:
            return
        elif self._rank[x] > self._rank[y]:
            self._table[x] += self._table[y]
            self._table[y] = x
        else:
            self._table[y] += self._table[x]
            self._table[x] = y
            if self._rank[x] == self._rank[y]:
                self._rank[y] += 1
    
    def find(self, x, y):
        return self._root(x) == self._root(y)

    def count(self, x):
        return -self._table[self._root(x)]
    
    def __str__(self):
        return str(list(self))
    def __repr__(self):           
        return repr(list(self))
    def __iter__(self):
        return (self._root(i) for i in range(n))

n, m, *AB = map(int, open(0).read().split())
ans = 0
for i in range(m):
    uf = UnionFind(n)
    for j, (a, b) in enumerate(zip(AB[::2], AB[1::2])):
        if i == j:
            continue
        uf.unite(a-1, b-1)
    ans += len(set(uf)) != 1
print(ans)

Solution (Python):
[n,m] = [int(i) for i in input().split()]
ans = 0
ab = []
stage = [[0] * n for i in range(n)]
for i in range(m):
    ab.append([int(j)-1 for j in input().split()])
    stage[ab[-1][0]][ab[-1][1]] = 1
    stage[ab[-1][1]][ab[-1][0]] = 1
for i in range(m):
    visit = [0] * n
    now = 0
    stage[ab[i][0]][ab[i][1]] = 0
    stage[ab[i][1]][ab[i][0]] = 0
    next = [0]
    while len(next):
        now = next.pop()
        visit[now] = 1
        for j in range(n):
            if stage[now][j] == 1 and visit[j] != 1:
                next.append(j)

    stage[ab[i][0]][ab[i][1]] = 1
    stage[ab[i][1]][ab[i][0]] = 1



    if 0 in visit:
        ans += 1
print(ans)

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

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

def ne(now,s,visit):
  visit.append(now)
  for i in e[now]:
    if i not in visit:
      ne(i, s, visit[:])
    elif len(visit)>2 and s==i:
      v1=visit[1]
      v2=visit[-1]
      if [s,v1] in b: b.remove([s,v1])
      elif [v1,s] in b: b.remove([v1,s])
      if [s,v2] in b:b.remove([s,v2])
      elif [v2,s] in b:b.remove([v2,s])
      break

for i in range(n):
  ne(i,i,[])
print(len(b))

Solution (Python):
from collections import deque

def Graph(ab):
    G = [[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G

def dfs(G, a, b):
    
    q = deque()
    q.append((1,-1))
    log = [0] * n
    log[0] = 1
    while q:
        V, P = q.pop()
        for new_v in G[V-1]:
            if {a, b} == {new_v, V}:
                continue
            if new_v == P:
                continue
            if log[new_v - 1]:
                continue
            log[new_v - 1] = 1
            q.append((new_v,V))
    return sum(log) != n

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
G = Graph(ab)

ans = 0
for a, b in ab:
    if dfs(G, a, b):
        ans += 1
print(ans)

Solution (Python):
from collections import deque

def Graph(ab):
    G = [[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G

def dfs(G, a, b):
    
    q = deque()
    q.append((1,-1))
    log = [0] * n
    log[0] = 1
    while q:
        V, P = q.pop()
        for new_v in G[V-1]:
            if {a, b} == {new_v, V}:
                continue
            if new_v == P:
                continue
            if log[new_v - 1]:
                continue
            log[new_v - 1] = 1
            q.append((new_v,V))
    return sum(log) != n

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
G = Graph(ab)

ans = 0
for a, b in ab:
    if dfs(G, a, b):
        ans += 1
print(ans)

Solution (Python):
class UnionFind:
    
    
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        return True
    def size(self, x: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum(1 for i in  self._parents if i<0)-self._first_idx
    def connected(self) ->bool:
        return self._parents[self.find(self._first_idx)]==-self._size
n,m=map(int,input().split())
edges=[list(map(int,input().split()))for i in range(m)]
a=0
for i in range(m):
    uf=UnionFind(n,1)
    for j in  range(m):
        if j==i:continue
        uf.unite(*edges[j])
    a+=uf.connected()
print(m-a)

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

def root(par, a):
    a_ = a
    while par[a] != a:
        a = par[a]
    par[a_] = a
    return a

def unite(par, a, b):
    ar = root(par, a)
    br = root(par, b)
    if ar != br:
        par[ar] = br

ans = 0
for i in range(M):
    par = list(range(N))
    for j in range(M):
        if i == j:
            continue
        a, b = E[j]
        unite(par, a, b)

    r0 = root(par, 0)
    for k in range(1, N):
        if root(par, k) != r0:
            ans += 1
            break
print(ans)

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

ans = 0
for i in range(M):
    G = [set() for _ in range(N)]
    for j in range(M):
        if i == j:
            continue
        a, b = E[j]
        G[a].add(b)
        G[b].add(a)

    todo = [0]
    done = set()
    while todo:
        p = todo.pop()
        done.add(p)
        for np in G[p]:
            if not np in done:
                todo.append(np)

    if len(done) < N:
        ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
edges = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a,b = map(int, input().split())
    edges[a-1][b-1] = 1
    edges[b-1][a-1] = 1

def dfs(start):
    if visited[start]:
        return
    visited[start] = 1
    for i in range(n):
        if edges[start][i]:
            dfs(i)

ans = m

for i in range(n-1):
    for j in range(i+1, n):
        if not edges[i][j]:
            continue
        
        
        visited = [0] * n
        edges[i][j] = 0
        edges[j][i] = 0
        dfs(0)
        
        edges[i][j] = 1
        edges[j][i] = 1
        
        if sum(visited) == n:
            ans -=1

print(ans)

Solution (Python):
n, m = map(int, input().split())
edges = [[0 for _ in range(50)] for _ in range(50)]
for _ in range(m):
    a,b = map(int, input().split())
    edges[a-1][b-1] = 1
    edges[b-1][a-1] = 1

def dfs(start):
    if visited[start]:
        return
    visited[start] = 1
    for i in range(n):
        if edges[start][i]:
            dfs(i)

ans = m

for i in range(m-1):
    for j in range(i+1, m):
        if not edges[i][j]:
            continue
        
        
        visited = [0] * n
        edges[i][j] = 0
        edges[j][i] = 0
        dfs(0)
        
        edges[i][j] = 1
        edges[j][i] = 1
        
        if sum(visited) == n:
            ans -=1

print(ans)

Solution (Python):
import collections
import queue
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M = map(int, input().split())
X, Y = [0] * M, [0] * M
g = [[] for _ in range(N)]

for i in range(M):
    X[i], Y[i] = map(int, input().split())

    X[i] -= 1
    Y[i] -= 1
    g[X[i]].append(Y[i])
    g[Y[i]].append(X[i])


def bfs(x, y):
    visited = [False] * N
    q = queue.Queue()
    for nx in g[x]:
        if nx == y:
            continue
        q.put(nx)
        visited[nx] = True

    visited[x] = True

    while not q.empty():
        cur = q.get()
        if cur == y:
            return True

        for nx in g[cur]:
            if visited[nx]:
                continue
            q.put(nx)
            visited[nx] = True

    return False


cnt = 0
for i in range(M):
    if not bfs(X[i], Y[i]):
        cnt += 1

print(cnt)

Solution (Python):
from functools import reduce


def is_all_true(arg):
  if isinstance(arg, bool):
    return arg
  return reduce(lambda x, y: is_all_true(x) and is_all_true(y), arg)

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

lines_ft = []
for _ in range(M):
  _from, _to = list(map(int, input().split()))
  lines_ft.append((_from, _to))

reachable_counter = 0

for i in range(M):
  
  is_reachable = [[False if i != j else True for i in range(N)] for j in range(N)]
  
  for f, t in lines_ft[:i] + lines_ft[i + 1:]:
    is_reachable[f - 1][t - 1] = True
    is_reachable[t - 1][f - 1] = True
  
  for k in range(N):
    for i in range(N):
      for j in range(N):
        is_reachable[i][j] = is_reachable[i][j] or (is_reachable[i][k] and is_reachable[k][j])
  
  if not is_all_true(is_reachable):
    reachable_counter += 1

print(reachable_counter)

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












parents = None


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


count = 0


def unit(x, y):
    root_x = root(x)
    root_y = root(y)
    if root_x < root_y:
        parents[root_y] = root_x
    else:
        parents[root_x] = root_y


def same(x, y):
    root_x = root(x)
    root_y = root(y)
    return (root_x == root_y)


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

ans = 0
for i in range(M):
    parents = [k for k in range(N)]
    for j, e in enumerate(es):
        if j == i:
            continue
        a, b = e
        unit(a, b)
    a, b = es[i]
    if not same(a, b):
        ans += 1
print(ans)