Problem:
 Score : 300 points    Problem Statement You are given an undirected connected graph with N vertices and M edges that does not contain self-loops and double edges. The i -th edge (1 \leq i \leq M) connects Vertex a_i and Vertex b_i .  An edge whose removal disconnects the graph is called a bridge . Find the number of the edges that are bridges among the M edges.      Notes  A self-loop is an edge i such that a_i=b_i  (1 \leq i \leq M) .  Double edges are a pair of edges i,j such that a_i=a_j and b_i=b_j  (1 \leq i<j \leq M) .  An undirected graph is said to be connected when there exists a path between every pair of vertices.       Constraints  2 \leq N \leq 50  N-1 \leq M \leq min(N(N−1)⁄2,50)  1 \leq a_i<b_i \leq N  The given graph does not contain self-loops and double edges.  The given graph is connected.         Input Input is given from Standard Input in the following format:  N  M  a_1  b_1  a_2  b_2  :  a_M  b_M       Output Print the number of the edges that are bridges among the M edges.        Sample Input 1 7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7      Sample Output 1 4  The figure below shows the given graph:     The edges shown in red are bridges. There are four of them.       Sample Input 2 3 3
1 2
1 3
2 3      Sample Output 2 0  It is possible that there is no bridge.       Sample Input 3 6 5
1 2
2 3
3 4
4 5
5 6      Sample Output 3 5  It is possible that every edge is a bridge.

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

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

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())



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


uf=UnionFind(n)
for i in range(m):
    uf.union(edge[i][0],edge[i][1])
groups=uf.group_count()

ans=0


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

print(ans)

Solution (Python):
from collections import deque

n, m = map(int, input().split())
eg = [[] for _ in range(n + 1)]

al = [0] * m
bl = [0] * m

for i in range(m):
    a, b = map(int, input().split())
    eg[a].append(b)
    eg[b].append(a)
    al[i], bl[i] = a, b

ans = 0
for i in range(m):
    x, y = al[i], bl[i]
    q = deque()
    q.append(1)
    seen = {1}
    while len(q) > 0:
        v = q.pop()
        for t in eg[v]:
            if t in seen:
                continue
            elif (v == x and t == y) or (v == y and t == x):
                continue
            q.append(t)
            seen.add(t)
    if len(seen) != n:
        ans += 1
print(ans)

Solution (Python):
from collections import deque

n, m = map(int, input().split())
eg = [[] for _ in range(n + 1)]

al = [0] * m
bl = [0] * m

for i in range(m):
    a, b = map(int, input().split())
    eg[a].append(b)
    eg[b].append(a)
    al[i], bl[i] = a, b

ans = 0
for i in range(m):
    x, y = al[i], bl[i]
    q = deque()
    q.append(1)
    seen = {1}
    while q:
        v = q.pop()
        for t in eg[v]:
            if t in seen:
                continue
            elif (v == x and t == y) or (v == y and t == x):
                continue
            q.append(t)
            seen.add(t)
    if len(seen) != n:
        ans += 1
print(ans)

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

al = [0] * m
bl = [0] * m

for i in range(m):
    a, b = map(int, input().split())
    eg[a].append(b)
    eg[b].append(a)
    al[i], bl[i] = a, b

ans = 0
for i in range(m):
    x, y = al[i], bl[i]
    q = [1]
    seen = {1}
    while len(q) > 0:
        v = q.pop()
        for t in eg[v]:
            if t in seen:
                continue
            elif (v == x and t == y) or (v == y and t == x):
                continue
            q.append(t)
            seen.add(t)
    if len(seen) != n:
        ans += 1
print(ans)

Solution (Python):
from collections import deque

n, m = map(int, input().split())
eg = [[] for _ in range(n + 1)]

al = [0] * m
bl = [0] * m

for i in range(m):
    a, b = map(int, input().split())
    eg[a].append(b)
    eg[b].append(a)
    al[i], bl[i] = a, b

ans = 0
for i in range(m):
    x, y = al[i], bl[i]
    q = deque()
    q.append(1)
    seen = {1}
    while q:
        v = q.pop()
        for t in eg[v]:
            if t in seen:
                continue
            elif (v == x and t == y) or (v == y and t == x):
                continue
            q.append(t)
            seen.add(t)
    if len(seen) != n:
        ans += 1
print(ans)

Solution (Python):
from collections import deque

n, m = map(int, input().split())
eg = [[] for _ in range(n + 1)]

al = [0] * m
bl = [0] * m

for i in range(m):
    a, b = map(int, input().split())
    eg[a].append(b)
    eg[b].append(a)
    al[i], bl[i] = a, b

ans = 0
for i in range(m):
    x, y = al[i], bl[i]
    q = deque()
    q.append(1)
    seen = {1}
    while len(q) > 0:
        v = q.pop()
        for t in eg[v]:
            if t in seen:
                continue
            elif (v == x and t == y) or (v == y and t == x):
                continue
            q.append(t)
            seen.add(t)
    if len(seen) != n:
        ans += 1
print(ans)

Solution (Python):
from collections import deque

n, m = map(int, input().split())
eg = [[] for _ in range(n + 1)]

al = [0] * m
bl = [0] * m

for i in range(m):
    a, b = map(int, input().split())
    eg[a].append(b)
    eg[b].append(a)
    al[i], bl[i] = a, b

ans = 0
for i in range(m):
    x, y = al[i], bl[i]
    q = deque()
    q.append(1)
    seen = {1}
    while len(q) > 0:
        v = q.pop()
        for t in eg[v]:
            if t in seen:
                continue
            elif (v == x and t == y) or (v == y and t == x):
                continue
            q.append(t)
            seen.add(t)
    if len(seen) != n:
        ans += 1
print(ans)

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

al = [0] * m
bl = [0] * m

for i in range(m):
    a, b = map(int, input().split())
    eg[a].append(b)
    eg[b].append(a)
    al[i], bl[i] = a, b

ans = 0
for i in range(m):
    x, y = al[i], bl[i]
    q = [1]
    seen = {1}
    while len(q) > 0:
        v = q.pop()
        for t in eg[v]:
            if t in seen:
                continue
            elif (v == x and t == y) or (v == y and t == x):
                continue
            q.append(t)
            seen.add(t)
    if len(seen) != n:
        ans += 1
print(ans)

Solution (Python):
from collections import deque

n, m = map(int, input().split())
eg = [[] for _ in range(n + 1)]

al = [0] * m
bl = [0] * m

for i in range(m):
    a, b = map(int, input().split())
    eg[a].append(b)
    eg[b].append(a)
    al[i], bl[i] = a, b

ans = 0
for i in range(m):
    x, y = al[i], bl[i]
    q = deque()
    q.append(1)
    seen = {1}
    while q:
        v = q.pop()
        for t in eg[v]:
            if t in seen:
                continue
            elif (v == x and t == y) or (v == y and t == x):
                continue
            q.append(t)
            seen.add(t)
    if len(seen) != n:
        ans += 1
print(ans)

Solution (Python):
import sys, math
from collections import defaultdict
from itertools import product
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

class Graph:
    

    
    no_labeling_num = -1

    class Vertex:
        

        def __init__(self, g, no, label):
            """

            :param g: グラフを表す。またVertexを所有するオブジェクトでもある
            :param no: 頂点にグラフのなかで一意に割り振られた識別用の番号
            :param label: 探索された順番を表す番号。ラベル。
            """
            self.no = no
            self.g = g
            self.label = label

        def __str__(self):
            """
            　
            """
            return "no:{0},label:{1}".format(self.no,self.label)

        def adjacentVs(self):
            """ selfと隣接している頂点のリストを返す

            :return:
            """
            result = []
            for c in range(self.g.order):
                if self.g.aDJM[self.no][c] == 1:
                    result.append((self.g.vs[c]))
            return result

        def back_to_previous(self):
            """ 前に探索した頂点を返す（厳密な表現ではない）
            詳細
            ・この頂点に隣接する頂点において、ラベル付けされていない（未探索）なものがないときに、
            次に探索する頂点を返す関数
            ・自身のラベル番号より小さい頂点の中で一番近いものを返す
            ・存在しないときは「None」を返す

            :return:
            """
            result = None
            vs = list(filter(lambda x: self.label > x.label, self.adjacentVs()))
            if vs != []:
                result = vs[0]
                key0 = self.label - result.label
                for v in vs:
                    key1 = self.label - v.label
                    if (key1 < key0):
                        key0 = key1
                        result = v

            return result

    def __init__(self, aDJM):
        """
        
        :param aDJM:隣接行列
        """
        self.aDJM = aDJM
        self.order = len(aDJM)
        self.vs = [Graph.Vertex(self, i, self.no_labeling_num) for i in range(self.order)]

    def no_labelingVs(self, vs):
        """ 渡された頂点リストにおいてlabelingされていない頂点のリストを返す

        :return:
        """
        result = []
        for v in vs:
            if v.label == self.no_labeling_num:
                result.append(v)
        return result

    def isconnected(self):
        """ このグラフが連結グラフであるかどうかを判定する
        
        :return:
        """
        label = 0
        v = self.vs[0]
        v.label = label
        
        if v.adjacentVs()==[]:
            v=None
        else:
            v = v.adjacentVs()[0]
            label += 1
            v.label = label
        while (v != None):  
            vs = self.no_labelingVs(v.adjacentVs())
            if vs == []:
                v = v.back_to_previous()
            else:
                v = vs[0]
                label += 1
                v.label = label

        return not(self.no_labeling_num in list(map(lambda x:x.label,self.vs)))


def main():
    N, M = mi()
    aDJM = [[0]*N for i in range(N)]
    a, b = i2(M)
    cnt = 0

    for i in range(M):
        aDJM[a[i]-1][b[i]-1] = 1
        aDJM[b[i]-1][a[i]-1] = 1
    
    for i in range(M):
        aDJM[a[i]-1][b[i]-1] = 0
        aDJM[b[i]-1][a[i]-1] = 0
        if not Graph(aDJM).isconnected():
            cnt += 1
        aDJM[a[i]-1][b[i]-1] = 1
        aDJM[b[i]-1][a[i]-1] = 1

    print(cnt)

if __name__ == '__main__':
    main()

Solution (Python):
from numpy import *
from scipy.sparse.csgraph import *
N,M = map(int,input().split())
E = [list(map(int,input().split())) for m in range(M)]
G1 = zeros((N,N))
ans = 0

for a,b in E:
  G1[a-1][b-1]+=1
  G1[b-1][a-1]+=1

for a,b in E:
  G2 = G1.copy()
  G2[a-1][b-1]-=1
  G2[b-1][a-1]-=1
  D = floyd_warshall(G2)
  if inf in D:
    ans+=1

print(ans)

Solution (Python):
from collections import deque
n,m = map(int,input().split())
L =[list(map(int, input().split())) for _ in range(m)]

cnt = 0
for i in range(m):
    G = [[] for _ in range(n)]
    
    for j in range(m):
        if i == j:
            continue
        a,b = L[j][0],L[j][1]
        
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    
    Q = deque()
    Q.append(0)
    visited = [0]*n
    visited[0] = 1
    while Q:
        q = Q.pop()
        for g in G[q]:
            if visited[g] == 0:
                visited[g] = 1
                
                Q.append(g)

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

Solution (Python):
n,m = map(int,input().split())
g = [[] for i in range(n)]
ab = []
for k in range(m):
  i,j = map(int,input().split())
  i,j = i-1,j-1
  g[i].append(j)
  g[j].append(i)
  ab.append((i,j))
c = 0
for i in range(m):
  visited = [1]+[0]*(n-1)
  stack = [0]
  while stack:
    cur = stack.pop()
    for j in g[cur]:
      if ab[i] in [(cur,j),(j,cur)]:
        continue
      if visited[j] == 0:
        visited[j] = 1
        stack.append(j)
  if 0 in visited:
    c += 1
print(c)

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

con = [[0]*(N+1) for _ in range(N+1)]
edge = []
for i in range(M):
    a, b = map(int, input().split())
    con[a][b] = con[b][a] = 1
    edge.append((a, b))

def floodfill(listz, comp):
    cnt = 0
    
    while len(listz):
        newlistz = []
        for node in listz:
            compo[node] = comp
            cnt += 1
            
            for i in range(1, N+1):
                if visited[i] == 0 and con[node][i] > 0:
                    visited[i] = 1
                    newlistz.append(i)
        listz = newlistz

    return cnt

ans = 0

for kk in range(M):
    a, b = edge[kk]
    con[a][b] = con[b][a] = 0
    
    visited = [0] * (N + 1)
    compo = [0] * (N + 1)
    compID = 0
    total = 0
    for i in range(1, N+1):
        if visited[i] == 0:
            visited[i] = 1
            count = floodfill([i], compID)
            if count > 0:
                compID += 1
                total += count
                if total >= N:
                    break

    if compID > 1:
        ans += 1
    
    con[a][b] = con[b][a] = 1


print(ans)

Solution (Python):
n, m = map(int, input().split())
l = []
edges = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    l.append([a - 1, b - 1])
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
def dfs(cur, a, b):
    if visited[cur] == 1:
        return None
    visited[cur] = 1
    for v in edges[cur]:
        if v != b or cur != a:
            dfs(v, a, b)
ans = 0
for i in l:
    i, j = i[0], i[1]
    visited = [0 for i in range(n)]
    dfs(i, i, j)
    if visited[j] == 0:
        ans += 1
print(ans)

Solution (Python):
from collections import deque
N, M = map(int, input().split())

ab = [list(map(int, input().split())) for _ in range(M)]
c = 0
for i in range(M):
    G = [[] for _ in range(N)]
    for j in range(M):
        if i == j:
            continue
        a, b = ab[j][0], ab[j][1]
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)
    Q = deque()
    Q.append(0)
    d = [0] * N
    d[0] = 1
    while Q:
        q = Q.popleft()
        for g in G[q]:
            if d[g] == 0:
                d[g] = 1
                Q.append(g)
    if 0 in d:
        c += 1

print(c)

Solution (Python):
import sys
from collections import deque
 
N, M = list(map(int,input().split()))
AB = [ list(map(int,input().split())) for _ in range(M)] 
 


count = 0
for sub in range(M):
    graph = [[] for _ in range(N + 1)] 
    for i in range(len(AB)): 
        if i == sub:
            continue
        else:
            graph[AB[i][0]].append(AB[i][1])
            graph[AB[i][1]].append(AB[i][0]) 
     
    
    queue = deque([1]) 
    signposts = [0] * (N + 1) 
    visit = []
    while queue: 
        u = queue.popleft() 
        visit.append(u)
        for v in graph[u]: 
            if (v not in visit) and (v not in queue): 
                queue.append(v) 

    if len(visit)!= N:
        count +=1
print(count)

Solution (Python):
class UnionFind:
  def __init__(self, n):
    self.p = [-1]*n
    
    self.r = [1]*n
 
  def find(self, x):
    if self.p[x] < 0:
      return x
    else:
      self.p[x] = self.find(self.p[x])
      return self.p[x]

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

    if rx != ry:
      if self.r[rx] > self.r[ry]:
        rx, ry = ry, rx
      if self.r[rx] == self.r[ry]:
        self.r[ry] += 1
      self.p[ry] += self.p[rx]
      self.p[rx] = ry

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

  def count_member(self, x):
    return -self.p[self.find(x)]

n,m=map(int,input().split())
ab=[]
for i in range(m):
  a,b=map(int,input().split())
  ab.append((a,b))
ans=0
for i in range(m):
  uf=UnionFind(n+1)
  connection=0
  for j in range(m):
    if i==j:continue
    a,b=ab[j]
    uf.union(a,b)
  connection=uf.count_member(1)
  if connection!=n:ans+=1
print(ans)

Solution (Python):
from copy import deepcopy
from collections import deque
n, m = map(int, input().split())
G = [[] for _ in range(n)]
V = []
for i in range(m):
    a, b = list(map(lambda x: x-1, map(int, input().split())))
    G[a].append(b)
    G[b].append(a)
    V.append([a,b])

ans = 0


for i in range(m):
    _G = deepcopy(G)
    _G[V[i][0]].remove(V[i][1])
    _G[V[i][1]].remove(V[i][0])
    
    
    que = deque([0])
    
    D = [-1]*n
    D[0] = 0
    
    while que:
        
        nw = que.popleft()
        
        for nx in _G[nw]:
            if D[nx]!=-1: continue
            D[nx] = D[nw]+1
            que.append(nx)
    if min(D) == -1:
        ans += 1
print(ans)

Solution (Python):
n,m = map(int,input().split())
g = [[]*(n+1) for _ in range(n+1)]
d = []
for _ in range(m):
    a,b = map(int,input().split())
    g[a].append(b)
    g[b].append(a)
    d.append([a,b])
seen = [False]*(n+1)
seen[0]=True
def dfs(s):
    seen[s]=True
    for e in g[s]:
        if not seen[e]:
            dfs(e)
cnt = 0
for i in range(m):
    a,b = d[i]
    g[a].remove(b)
    g[b].remove(a)
    dfs(1)
    for i in range(n+1):
        if not seen[i]:
            cnt += 1
            break
    seen = [False]*(n+1)
    seen[0]=True
    g[a].append(b)
    g[b].append(a)
print(cnt)

Solution (Python):
from collections import deque
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
c = 0

for i in range(M):
    G = [[] for _ in range(N)]
    for j in range(M):
        if i == j:
            continue
        a, b = ab[j][0], ab[j][1]
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)
    Q = deque()
    Q.append(0)
    d = [0] * N
    d[0] = 1
    while Q:
        q = Q.popleft()
        for g in G[q]:
            if d[g] == 0:
                d[g] = 1
                Q.append(g)
    if 0 in d:
        c += 1

print(c)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
from collections import deque, defaultdict
n , m = map(int, input().split())



li = []

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




def bfs(i):
    parent = [-10]*n 
    order = []
    parent[i] = -1
    stack = deque()
    u = i
    stack.append(u)
    while stack:
        x = stack.popleft()
        order.append(x)
        for v in G[x]:
            if v == parent[x]:
                continue
            if parent[v] != -10:
                continue
            parent[v] = x
            stack.append(v)
    return parent
            
ans = 0
for i in range(m):
    G = [[] for _ in range(n)]
    for j in range(m):
        if i == j:
            continue
        a, b = li[j]
        G[a].append(b)
        G[b].append(a)
    li_p = bfs(0)
    for k in li_p:
        if k == -10:
            ans += 1
            break
print(ans)

Solution (Python):
from itertools import combinations
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)]

n,m=map(int,input().split())
uf=UnionFind(n)
e=[]
comb=list(combinations(list(range(n)),2))
for _ in range(m):
  a,b=map(int,input().split())
  e.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.Unite(*e[j])
  if not all([uf.isSameGroup(x,y) for x,y in comb]):ans+=1
print(ans)

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

def dfs(lst):
    visited=[None]*n
    visited[0]=1
    stack=[]
    for i in lst[0]:
        stack.append(i)
    while stack:
        new=stack.pop()
        if visited[new]==None:
            visited[new]=1
            for i in lst[new]:
                stack.append(i)
    if None in visited:
        return True
    else:
        return False

ans=0
for i in range(m): 
    edge=[[] for _ in range(n)]
    for j in range(m): 
        if i==j:
            continue
        a=all_edge[j][0]
        b=all_edge[j][1]
        edge[a].append(b)
        edge[b].append(a)
    if dfs(edge):
        ans+=1
print(ans)

Solution (Python):

def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]



def union(x, y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return

    
    if par[x] > par[y]:
        x, y = y, x

    par[x] += par[y]
    par[y] = x



def size(x):
    return -par[find(x)]



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


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

res = 0
for i in range(m):
    par = [-1] * n
    flag = False

    for j in range(m):
        if i == j:
            continue
        a, b = e[j]
        union(a-1, b-1)
    
    for j in range(n):
        for k in range(j+1, n):
            if not same(j, k):
                flag = True
    
    if flag:
        res += 1

print(res)

Solution (Python):
from collections import deque

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

res = 0
for i in range(m):
    edge = [[] for _ in range(n)]
    for j in range(m):
        if i == j:
            continue
        a, b = e[j]
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    
    flag = False
    for j in range(n):
        d = deque([j])
        visited = [False] * n
        visit_cnt = 0
        while d:
            node = d.popleft()
            visited[node] = True
            visit_cnt += 1
            for next_node in edge[node]:
                if not visited[next_node]:
                    d.append(next_node)
        if visit_cnt < n:
            flag = True
            break
    
    if flag:
        res += 1

print(res)

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



def dfs(v):
    global da, db
    if tf[v]:
        return
    tf[v] = True
    for nv in ab[v]:
        if v == da and nv == db:
            continue
        if v == db and nv == da:
            continue
        dfs(nv)
    return



ans = 0
for i in range(M):
    da, db = abl[i]
    tf = [False for _ in range(N)]
    dfs(0)
    if not all(e for e in tf):
        ans += 1
print(ans)

Solution (Python):
N, M = list(map(int,input().split()))
in_ = []
for i in range(M):
    a, b = map(int, input().split())
    in_.append([a, b])
    
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 __str__(self):  return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
        
ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if i == j:  continue
        uf.union(in_[j][0] - 1, in_[j][1] - 1)
    ans += (uf.group_count() != 1)
print(ans)

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

def dfs(node, parent):
    ret = 1
    global seen
    if seen[node]:  return 0
    seen[node] = True
    for i in range(N):
        if graph[node][i] == 1 and i != parent:
            ret = min(dfs(i, node), ret)
    return ret

ans = 0

for i in range(M):
    
    graph[in_list[i][0] - 1][in_list[i][1] - 1] = -1
    graph[in_list[i][1] - 1][in_list[i][0] - 1] = -1
    
    seen = [False for _ in range(N)]
    link = 0 
    wood = 0 
    
    for j in range(N):
        if seen[j] == False:
            link += 1
            wood += dfs(j, 0)
            seen[j] = True
            
    ans += (link != 1)
    
    graph[in_list[i][0] - 1][in_list[i][1] - 1] = 1
    graph[in_list[i][1] - 1][in_list[i][0] - 1] = 1
    
print(ans)

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

ans = 0
for num in hashi:
	settansaku = set([])
	setmada = {0}
	kouho = 1
	
	while kouho != 0:
		for i in list(setmada):
			settansaku.add(i)
			setmada.remove(i)
			kouho -= 1
			for k in ikeru[i]:
				if not k in setmada:
					if not k in settansaku:
						if (k, i) != num and (i, k) != num:
							setmada.add(k)
							kouho += 1
	
	if len(settansaku) != n:
		ans += 1

print(ans)

Solution (Python):




"""

計算量
O(V+E)

参考
https://algo-logic.info/bridge-lowlink/


"""



import sys
input = sys.stdin.readline
import marshal


class Graph:
    def __init__(self, n, dictated=False, decrement=True, destroy=False, edges=[]):
        self.n = n
        self.dictated = dictated
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        if self.dictated == False:
            self.edges[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edges[i] = set(map(lambda x: x - 1, adjacent_list))
        else:
            self.edges[i] = set(adjacent_list)

    def bridge_detector(self, articular_list=False):
        """
        :param p: スタート地点
        :param save: True = 前回の探索結果を保持する
        :param articular_list: True = 関節点のリストを返す
        :return: 各点までの距離と何番目に発見したかを返す
        """

        if self.destroy:
            edge2 = self.edges
        else:
            edge2 = marshal.loads(marshal.dumps(self.edges))

        start, time = 0, 0
        p, t = start, time
        self.parent[p] = -2
        ord = [-1]*self.n       
        ord[p] = t
        low = [-1]*self.n       
        low[p] = 0
        articular = []          
        bridge = []             

        if len(edge2[p]) >= 2:
            """ 根に子が二つ異常存在する場合は、根も関節点 """
            articular.append(p)

        while True:
            if edge2[p]:
                q = edge2[p].pop()
                if q == self.parent[p] and not self.dictated:
                    """ 逆流した時の処理 """
                    """"""""""""""""""""
                    continue
                if self.parent[q] != -1:
                    """ サイクルで同一点を訪れた時の処理 """
                    if ord[q] < low[p]:
                        low[p] = ord[q]
                    """"""""""""""""""""
                    continue
                """ p から q への引継ぎ"""
                """"""""""""""""""""
                ord[q] = low[q] = t + 1
                self.parent[q] = p
                p, t = q, t + 1
            else:
                if p == start and t == time:
                    break
                """ p から進める点がもう無い時の点 p における処理 """
                parent_p = self.parent[p]
                if low[p] < low[parent_p]:
                    low[parent_p] = low[p]
                """ この時点でlow[p]が確定するので、ord[parent[p]] ≤ low[p] を判定しておく"""
                if ord[parent_p] <= low[p]:
                    if ord[parent_p]:
                        articular.append(parent_p + self.decrement)
                    if ord[parent_p] < low[p]:
                        bridge.append((parent_p + self.decrement, p + self.decrement))
                """"""""""""""""""""
                p, t = self.parent[p], t - 1
                """ 点 p から親ノードに戻ってきた時の親ノードにおける処理 """
                """"""""""""""""""""
        if articular_list == False:
            return bridge
        else:
            return articular

    def draw(self):
        """
        :return: グラフを可視化
        """
        import matplotlib.pyplot as plt
        import networkx as nx

        if self.dictated:
            G = nx.DiGraph()
        else:
            G = nx.Graph()
        for x in range(self.n):
            for y in self.edges[x]:
                G.add_edge(x + self.decrement, y + self.decrement)

        nx.draw_networkx(G)
        plt.show()


def inc(A):
    return list(map(lambda x: x+1, A))


def dec(A):
    return list(map(lambda x: x-1, A))



N, M = map(int, input().split())
graph = Graph(N, dictated=False, decrement=True, destroy=False)
for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x, y)



print(len(graph.bridge_detector(articular_list=False)))



"""
9 10
7 8
8 9
3 6
9 2
1 2
2 3
3 4
4 5
5 6
6 7

"""