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():
    """
    parents
        各要素の親要素の番号を格納するリスト
        要素が根（ルート）の場合は-(そのグループの要素数)を格納する
    find(x)
        要素xが属するグループの根を返す
    union(x, y)
        要素xが属するグループと要素yが属するグループとを併合する
    size(x)
        要素xが属するグループのサイズ（要素数）を返す
    same(x, y)
        要素x, yが同じグループに属するかどうかを返す
    members(x)
        要素xが属するグループに属する要素をリストで返す
        関連記事: Pythonリスト内包表記の使い方
    roots()
        すべての根の要素をリストで返す
    group_count()
        グループの数を返す
    all_group_members
        {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
        関連記事: Pythonで辞書を作成するdict()と波括弧、辞書内包表記
    __str__()
        print()での表示用
        ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
    """
    
    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=[tuple(map(int,input().split())) for _ in range(M)]
ans=0

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

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

class UnionFind:
    def __init__(self, N):
        self.root = list(range(N + 1))
        self.size = [1] * (N + 1)

    def __getitem__(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def merge(self, x, y):
        x = self[x]
        y = self[y]
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            x, y = y, x
            sx, sy = sy, sx
        self.root[y] = x
        self.size[x] += sy


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

count = 0
for i in range(M):
    uni = UnionFind(N)
    for j in range(M):
        if j == i:
            continue
        uni.merge(A[j], B[j])
    
    roots = [uni[x] for x in uni.root[1:]]
    counter = Counter(roots)
    if len(counter) > 1:
        count += 1

print(count)

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

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


for i in cnt:
  judge=False
  j=i[0]
  Q=[j]
  visited=[False]*n
  
  while Q:
      v=Q.pop(0)
      for k in lst[v]:
        if (v==i[0] and k==i[1]) or (v==i[1] and k==i[0]):
          continue
        if visited[k]==False:
              visited[k]=True
              Q.append(k)

  if visited[i[1]]==True:
      judge=True

  
  if judge:
    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)]

count = 0
for i in range(m):
    edges = [[]*n for _ in range(n)]
    for j in range(m):
        if j == i:
            continue
        edges[ab[j][0]-1].append(ab[j][1]-1)
        edges[ab[j][1]-1].append(ab[j][0]-1)
    
    d = deque([0])
    visited = [0]*n
    visited[0] = 1
    while d:
        p = d.pop()
        for child in edges[p]:
            if visited[child] == 1:
                continue
            visited[child] = 1
            d.append(child)
    if sum(visited) != n:
        count += 1
print(count)

Solution (Python):
class union_find():
    def __init__(self,n):
        self.n=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 union(self,x,y):
        x=self.find(x)
        y=self.find(y)

        

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

    def same(self,x,y):
        return self.find(x) == self.find(y)
      
n,m=map(int,input().split())
uf=union_find(n)
ans=0
s=[]
for _ in range(m):
  a=list(map(int,input().split()))
  s.append(a)
  uf.union(a[0],a[1])
  
  

for e in range(m):
  uf1=union_find(n)
  ch=0
  for d in range(m):
    if d!=e:
      uf1.union(s[d][0],s[d][1])
      
  for i in range(1,n):
    for j in range(i+1,n+1):
      if not uf1.same(i,j):
        ch+=1
  if ch>0:
    ans+=1

    
print(ans)

Solution (Python):
def FindParent(X):
    if Parent[X]==X:
        return X
    else:
        Parent[X] = FindParent(Parent[X])
        return Parent[X]

def CheckParent(X,Y):
    return FindParent(X)==FindParent(Y)

def UniteParent(X,Y):
    X = FindParent(X)
    Y = FindParent(Y)
    if X==Y:
        return 0
    if Rank[X]<Rank[Y]:
        Parent[X] = Y
    else:
        Parent[Y] = X
        if Rank[X]==Rank[Y]:
            Rank[X] += 1

import copy
N,M = (int(T) for T in input().split())
List = [[] for TM in range(0,M)]
for TM in range(0,M):
    List[TM] = [int(T) for T in input().split()]
    
Count = 0
for TM in range(0,M):
    ListCopy = copy.deepcopy(List)
    del ListCopy[TM]
    
    Parent = [I for I in range(N+1)]
    Rank = [0]*(N+1)
    for TTM in range(0,M-1):
        UniteParent(ListCopy[TTM][0],ListCopy[TTM][1])

    if not CheckParent(List[TM][0],List[TM][1]):
        Count += 1
print(Count)

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

parent = [i for i in range(N)]
height = [1] * N

def find(i):
    while i != parent[i]:
        i = parent[i]
    return i

def union(i, j):
    i = find(i)
    j = find(j)
    if height[i] >= height[j]:
        parent[j] = i
        height[i] = max(height[i], height[j] + 1)
    else:
        parent[i] = j
        height[j] = max(height[j], height[i] + 1)

bridges = 0
for cand in range(M):
    parent = [i for i in range(N)]
    height = [1] * N
    islands = N
    for i in range(M):
        if i == cand:
            continue
        a, b = edges[i]
        if find(a) == find(b):
            continue
        islands -= 1
        union(a, b)
    if islands > 1:
        bridges += 1
print(bridges)

Solution (Python):
def FindParent(X):
    if Parent[X]==X:
        return X
    else:
        Parent[X] = FindParent(Parent[X])
        return Parent[X]

def UniteParent(X,Y):
    X = FindParent(X)
    Y = FindParent(Y)
    if X==Y:
        return 0
    if Rank[X]<Rank[Y]:
        Parent[X] = Y
    else:
        Parent[Y] = X
        if Rank[X]==Rank[Y]:
            Rank[X] += 1

import copy
N,M = (int(T) for T in input().split())
List = [[] for TM in range(0,M)]
for TM in range(0,M):
    List[TM] = [int(T) for T in input().split()]
    
Count = 0
for TM in range(0,M):
    ListCopy = copy.deepcopy(List)
    del ListCopy[TM]
    
    Parent = [I for I in range(N+1)]
    Rank = [0]*(N+1)
    for TTM in range(0,M-1):
        UniteParent(ListCopy[TTM][0],ListCopy[TTM][1])
    for TN in range(1,N+1):
        FindParent(TN)
    if len(set(Parent[1:]))>1:
        Count += 1
print(Count)

Solution (Python):
from networkx import *
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
g = Graph(a)
print(len(tuple(bridges(g))))

Solution (Python):
from networkx import *
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
g = Graph(a)
ans = 0
for x in a:
  g.remove_edges_from([x])
  if not is_connected(g):
    ans += 1
  g.add_edges_from([x])
print(ans)

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

def dfs(v,ID): 
  visited.add(v)
  for u,idx in G[v]:
    if idx == ID or u in visited:
      continue
    dfs(u,ID)

for i in range(M):
  visited = set([])
  start = H[i][0]
  goal = H[i][1]
  dfs(start,i)
  if goal not in visited:
    ans +=1
print(ans)

Solution (Python):
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parent = [i for i in range(self.n)]
    self.rank = [0] * self.n
  
  def find_root(self, x):
    if self.parent[x] == x:
      return x
    else:
      self.parent[x] = self.find_root(self.parent[x])
      return self.parent[x]
  
  def unite(self, x, y):
    rx = self.find_root(x)
    ry = self.find_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
  
  def is_same(self, x, y):
    return self.find_root(x) == self.find_root(y)

N, M = map(int, input().split())
edge = []
bridge = 0
for _ in range(M):
  e = list(map(lambda x: int(x)-1, input().split()))
  edge.append(e)

for i in range(M):
  uf = UnionFind(N)
  for j in range(M):
    if j == i:
      continue
    uf.unite(edge[j][0], edge[j][1])
  if uf.find_root(edge[i][0]) != uf.find_root(edge[i][1]):
    bridge += 1

print(bridge)

Solution (Python):
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parent = [i for i in range(self.n)]
    self.rank = [0] * self.n
  
  def find_root(self, x):
    if self.parent[x] == x:
      return x
    else:
      self.parent[x] = self.find_root(self.parent[x])
      return self.parent[x]
  
  def unite(self, x, y):
    rx = self.find_root(x)
    ry = self.find_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
  
  def is_same(self, x, y):
    return self.find_root(x) == self.find_root(y)

N, M = map(int, input().split())
edge = []
bridge = 0
for _ in range(M):
  e = list(map(lambda x: int(x)-1, input().split()))
  edge.append(e)

for i in range(M):
  uf = UnionFind(N)
  for j in range(M):
    if j == i:
      continue
    uf.unite(edge[j][0], edge[j][1])
  
  root = uf.find_root(0)
  for i in range(1, N):
    if root != uf.find_root(i):
      bridge += 1
      break

print(bridge)

Solution (Python):
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
r=0
for m in range(M):
    c=[[] for i in range(N)]
    for i,(a,b) in enumerate(AB):
        if i!=m:
            c[a-1].append(b-1)
            c[b-1].append(a-1)
    q=[0]
    v=[1]+[0]*(N-1)
    while q:
        p=q.pop()
        for n in c[p]:
            if v[n]==0:
                v[n]=1
                q.append(n)
    if 0 in v:
        r+=1
print(r)

Solution (Python):
import sys

input = sys.stdin.readline


class UnionFind:
    """Union Find class.

    "Path compression" and "Union by rank" are used.

    References:
        <https://en.wikipedia.org/wiki/Disjoint-set_data_structure>
    """

    def __init__(self, N):
        self.N = N
        self.__make_set()

    def __make_set(self):
        self._parent = list(range(self.N + 1))
        self._rank = [0] * (self.N + 1)
        self._size = [1] * (self.N + 1)

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

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

        if x_root == y_root:
            return

        x_rank = self._rank[x_root]
        y_rank = self._rank[y_root]
        if x_rank > y_rank:
            self._parent[y_root] = x_root
            self._size[x_root] += self._size[y_root]
        elif x_rank < y_rank:
            self._parent[x_root] = y_root
            self._size[y_root] += self._size[x_root]
        else:
            self._parent[y_root] = x_root
            self._rank[x_root] += 1
            self._size[x_root] += self._size[y_root]

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

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


def main():
    N, M = map(int, input().split())
    a = [None] * M
    b = [None] * M
    for i in range(M):
        a[i], b[i] = map(int, input().split())

    ans = 0
    for i in range(M):
        uf = UnionFind(N)
        for j in range(M):
            if j == i:
                continue
            uf.union(a[j], b[j])
        if not uf.same_set(a[i], b[i]):
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
def BFS(N,M,List):
    Edge = [[] for TN in range(N+1)]
    for TM in range(0,M):
        Edge[List[TM][0]].append(List[TM][1])
        Edge[List[TM][1]].append(List[TM][0])

    Distance = [-1]*(N+1)
    Distance[0] = 0
    Distance[1] = 0
    
    From = [0]*(N+1)
    From[1] = 1

    Deque = deque()
    Deque.append(1)
    while Deque:
        Now = Deque.popleft()
        for Con in Edge[Now]:
            if Distance[Con]==-1:
                Distance[Con] = Distance[Now]+1
                Deque.append(Con)
                From[Con] = Now

    return Distance[1:],From[1:]

import copy
N,M = (int(T) for T in input().split())
List = [[] for TM in range(0,M)]
for TM in range(0,M):
    List[TM] = [int(T) for T in input().split()]
Count = 0
for TM in range(0,M):
    ListCopy = copy.deepcopy(List)
    del ListCopy[TM]
    Distance,From = BFS(N,M-1,ListCopy)
    if -1 in Distance:
        Count += 1
print(Count)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.rank = [0] * n
        self.par = list(range(n))

    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return
        if self.rank[rx] >= self.rank[ry]:
            self.par[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
        else:
            self.par[rx] = ry

    
    def find(self, x):
        ch = []
        while self.par[x] != x:
            ch.append(x)
            x = self.par[x]
        for c in ch:
            self.par[c] = x
        return x

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

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

ans = 0
for (a, b) in E:
    uf = UnionFind(N)
    for (c, d) in E: 
        if (c, d) != (a, b):
            uf.union(c, d)
    if not uf.same(a, b):
        ans += 1

print(ans)

Solution (Python):
import sys
N, M = map(int, sys.stdin.readline().split())
graph = [[False for i in range(N)] for i in range(N)]
ab = []
for i in range(M):
    a, b = map(int, sys.stdin.readline().split())
    a -= 1
    b -= 1
    ab.append([a, b])
    graph[a][b] = graph[b][a] = True

all_use = (1 << N) - 1


def rec(v, use):
    use |= 1 << v
    for u in range(N):
        if (not graph[u][v]) or (use >> u) & 1:
            continue
        use |= rec(u, use)
    return use


ans = 0
for a, b in ab:
    graph[a][b] = graph[b][a] = False
    if rec(0, 0) != all_use:
        ans += 1
    graph[a][b] = graph[b][a] = True
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
N, M = map(int, input().split())
graph = [[0]*N for _ in range(N)]
visited = [0]*N
ab = []
ans = 0

def dfs(u):
  visited[u] = 1
  for v in range(N):
    if graph[u][v] == 1 and visited[v] == 0:
      dfs(v)

for _ in range(M):
  a, b = map(lambda x:int(x)-1, input().split())
  graph[a][b] = 1
  graph[b][a] = 1
  ab += [[a, b]]

for _ in range(M):
  a, b = ab.pop(0)
  graph[a][b] = 0
  graph[b][a] = 0

  for i in range(N):
    visited[i] = 0
  
  dfs(0)
  
  if sum(visited) != N:
    ans += 1

  graph[a][b] = 1
  graph[b][a] = 1

print(ans)

Solution (Python):
import heapq
N, M = map(int, input().split())
ab = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
ans = 0

def dijkstra(s, graph, n):
  dist = [float('inf')]*n
  dist[s] = 0
  num = [0]*n
  num[s] = 1
  q = [[0, s]]
  heapq.heapify(q)
  while q:
    c, u = heapq.heappop(q)
    if dist[u] < c:
      continue
    for v, weight in graph[u]:
      if dist[v] > dist[u] + weight:
        dist[v] = dist[u] + weight
        num[v] = num[u]
        heapq.heappush(q, [dist[v], v])
      elif dist[v] == dist[u] + weight:
        num[v] += num[u]
  return dist, num

for i in range(M):
  graph = [[] for _ in range(N)]
  for j in range(M):
    if i != j:
      a, b = ab[j]
      graph[a] += [[b, 1]]
      graph[b] += [[a, 1]]

  for j in range(N):
    d, _ = dijkstra(j, graph, N)
    if max(d) == float('inf'):
      ans += 1
      break
print(ans)

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    que = deque([0])
    c[0] = 1
    while que:
        v = que.popleft()
        for w in g[v]:
            if c[w] == 1:
                continue
            c[w] = 1
            que.append(w)

n, m  = MAP()
g = [[] for i in range(n)]
a = [0]*m
b = [0]*m
for i in range(m):
    a[i], b[i] = MAP()
    a[i] -= 1
    b[i] -= 1
    g[a[i]].append(b[i])
    g[b[i]].append(a[i])

ans = 0
for i in range(m):
    g[a[i]].remove(b[i])
    g[b[i]].remove(a[i])
    c = [0]*n
    bfs()
    for j in range(n):
        if c[j] == 0:
            ans += 1
            break
    g[a[i]].append(b[i])
    g[b[i]].append(a[i])

print(ans)

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

n,m=map(int,input().split())
pair=[i for i in range(n)]
a=[0]*m
b=[0]*m
for i in range(m):
    ai,bi=map(int,input().split())
    a[i]=ai-1
    b[i]=bi-1
    
def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return
    pair[x]=y

icnt=0
for i in range(m):
    pair=[i for i in range(n)]
    for ii in range(m):
        if ii==i:
            continue
        unite(a[ii],b[ii])

    l=[root(ii) for ii in range(n)]

    lenpair=len(set(l))    
    if lenpair!=1:
        icnt+=1

print(icnt)

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

par = [-1]*n
num = [0]*n

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

def union(x, y):
    p,q=find(x), find(y)
    if p==q:
        return
    if p>q:
        p,q = q,p
    par[p] += par[q]
    par[q] = p

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

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

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

ans=0

for i in range(m):
    L=lst[:i]+lst[i+1:]
    par=[-1]*n
    for l in L:
        union(l[0],l[1])
    if [p<0 for p in par].count(1)>1:
        ans+=1

print(ans)

Solution (Python):
"""
何回も再帰するときはlimitを増やす
dfs
"""
import sys
sys.setrecursionlimit(200000)

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


tree = [[] for _ in range(n)]
for a,b in l:
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

bit = [0 for _ in range(n)]
def dfs(v):
    bit[v] = 1
    for j in tree[v]:
        if bit[j]==0:
            dfs(j)

ans = 0
for i in range(m):
    a,b = l[i]
    a -= 1
    b -= 1
    tree[a].remove(b)
    tree[b].remove(a)
    bit = [0 for _ in range(n)]
    dfs(a)
    if bit.count(1) !=n:
        ans += 1

    tree[a].append(b)
    tree[b].append(a)
print(ans)

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

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

def union(x,y):
    x,y=find(x),find(y)
    if x!=y:
        if x>y:
            x,y=y,x
        par[x]+=par[y]
        par[y]=x
M=[]
for i in range(m):
    x,y=map(int,input().split())
    M.append([x-1,y-1])

ans=0

for i in range(m):
    X=M[:i]+M[i+1:]
    par = [-1] * n
    for x in X:
        union(x[0],x[1])
    if [p<0 for p in par].count(1)>1:
        ans+=1
print(ans)

Solution (Python):
n,m=map(int,input().split())
t=[[0 for i in range(n)] for j in range(n)]
A,B=[],[]
for _ in range(m):
    a,b=map(int,input().split())
    A.append(a-1)
    B.append(b-1)
    t[a-1][b-1]=1
    t[b-1][a-1]=1
ans=0
for i in range(m):
    t[A[i]][B[i]]=0
    t[B[i]][A[i]]=0
    
    q=[0]
    visited={0}
    while q:
        temp=q.pop()
        for j in range(n):
            if j not in visited and t[temp][j]==1:
                q.append(j)
                visited.add(j)
    if len(visited)!=n: ans+=1
    t[A[i]][B[i]]=1
    t[B[i]][A[i]]=1
print(ans)

Solution (Python):
class UnionFindVerSize():
    def __init__(self,N):
        
        self._parent = [n for n in range(0, N)]
        
        self._size=[1]*N
    def find_root(self,x):
        if self._parent[x]==x:
            return x
        self._parent[x]=self.find_root(self._parent[x])
        return self._parent[x]
    def unite(self, x, y):
        
        gx=self.find_root(x)
        gy=self.find_root(y)
        if gx == gy:
            return
        
        if self._size[gx]<self._size[gy]:
            self._parent[gx] = gy
            self._size[gy]+=self._size[gx]
        else:
            self._parent[gy]=gx
            self._size[gx]+=self._size[gy]
    def get_size(self, x):
        
        return self._size[self.find_root(x)]
    def is_same_group(self, x, y):
        
        return self.find_root(x) == self.find_root(y)
    def calc_group_num(self):
        
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans
n,m=list(map(int,input().split()))

ab=[]
for i in range(m):
    ab.append(list(map(int,input().split())))
ans=0
for i in range(m):
    union=UnionFindVerSize(n)
    for j in range(m):
        if i!=j:
          union.unite(ab[j][0]-1,ab[j][1]-1)
    if union.calc_group_num()!=1:
        ans=ans+1
        
print(ans)

Solution (Python):
from collections import Counter

class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n
        self.g = set()
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.g.add(x)
        if y in self.g:self.g.remove(y)
        self.d[y] = x
        return True

    def same(self,x,y): return self.find(x)==self.find(y)
    def size(self,x): return -self.d[self.find(x)]
    
N,M=map(int,input().split())
edges=[tuple(map(int,input().split())) for _ in range(M)]
count=0
for m in range(M):
  uf = UnionFind(N+1)
  for i in range(M):
    if m==i:continue
    a,b=edges[i]
    uf.unite(a,b)
  if len(uf.g)+Counter(uf.d)[-1]-1==2:count+=1
print(count)

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,M=mi()
    G = [[] for _ in range(N)]
    E = []
    for i in range(M):
        a,b = mi()
        a-=1; b -= 1 

        G[a].append(b)
        G[b].append(a)
        E.append((a,b))
    
    deg1_v = -1
    for i in range(N):
        deg = len(G[i])
        if deg == 1:
            deg1_v = i
            break
    
    if deg1_v == -1:
        print(0)
        exit()

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

        visited_count = 0
        stack = deque([deg1_v])
        seen = set()
        visited = set()
        while stack:
            visited_count += 1
            current_e = stack.popleft()

            visited.add(current_e)
            for next in G[current_e]:
                if (current_e,next) in seen: continue
                stack.append(next)
                seen.add((current_e,next))
    
        if len(visited) != N:
            
            ans += 1
    
        G[a].append(b)
        G[b].append(a)
    
    print(ans)





    


if __name__ == "__main__":
    main()

Solution (Python):
class UnionFind:
  def __init__(self, n):
    self.parent = [i for i in range(n)]
    self.height = [0 for i in range(n)]
        
  def get_root(self, i):
    if self.parent[i] == i:
      return i
    else:
      self.parent[i] = self.get_root(self.parent[i])
      return self.parent[i]
            
  def unite(self, i, j):
    root_i = self.get_root(i)
    root_j = self.get_root(j)
    if root_i != root_j:
      if self.height[root_i] < self.height[root_j]:
        self.parent[root_i] = root_j
      else:
        self.parent[root_j] = root_i
        if self.height[root_i] == self.height[root_j]:
          self.height[root_i] += 1
                
  def is_in_group(self, i, j):
    if self.get_root(i) == self.get_root(j):
      return True
    else:
      return False
    
N, M = map(int, input().split())
graph = list()
ans = 0
for i in range(M):
  a, b = map(int, input().split())
  graph.append([a-1, b-1])
for i in range(M):
  flag = 0
  uf = UnionFind(N)
  for j in range(M):
    if(i != j):
      uf.unite(graph[j][0], graph[j][1])
  for k in range(1, N):
    if uf.is_in_group(0, k) == False:
      flag = 1
  if(flag == 1):
    ans += 1
print(ans)

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

from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n 
    d[u] = 0 
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    flag=True
    for _i in range(n):
        if d[_i]==None:
            flag=False
    return flag

cnt=0
for i in range(m):
    graph = [[] for _ in range(n)]
    for j in range(m):
        if i!=j:
            graph[ab[j][0]-1].append(ab[j][1]-1)
            graph[ab[j][1]-1].append(ab[j][0]-1)
    if not bfs(0):
        cnt+=1
print(cnt)

Solution (Python):


from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


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






def root(u):
    if parents[u] < 0:
        return u
    parents[u] = root(parents[u])
    return parents[u]


def has_same_root(u, v):
    return root(u) == root(v)


def size(root_u):
    return -parents[root_u]


def unite(u, v):
    if has_same_root(u, v):
        return
    root_u = root(u)
    root_v = root(v)
    if size(root_u) > size(root_v):
        root_u, root_v = root_v, root_u
    parents[root_v] = root_u


ans = 0
for e_i in edges:
    parents = [-1 for _ in range(N)]
    for e_j in edges:
        if e_i == e_j:
            continue
        u, v = e_j
        unite(u, v)

    count = 0
    for i in range(N):
        if parents[i] < 0:
            count += 1
    if count > 1:
        ans += 1

print(ans)

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


N,M = map(int,readline().split())
G = [[] for i in range(N)]
bridges = [None] * M
for i in range(M):
  a,b = map(int,readline().split())
  G[a - 1].append(b - 1)
  G[b - 1].append(a - 1)
  bridges[i] = (a - 1,b - 1)
  
ans = 0
for i in range(M):
  
  NG = bridges[i]
  seen = set()
  stack = []
  
  stack.append([0, -1])
  while stack:
    v,parent = stack.pop()
    if v in seen:
      continue
    seen.add(v)
    for child in G[v]:
      if child == parent:
        continue
      if (v, child) == NG or (child, v) == NG: 
        continue
      stack.append([child, v])
  if len(seen) != N:
    ans += 1

print(ans)

Solution (Python):
from collections import Counter


class UnionFind:
    def __init__(self, n):
        self.root = list(range(n + 1))
        self.size = [1] * (n + 1)

    def __getitem__(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def merge(self, x, y):
        x = self[x]
        y = self[y]
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            x, y = y, x
            sx, sy = sy, sx
        self.root[y] = x
        self.size[x] += sy


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

for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)


res = 0
for i in range(M):
    uni = UnionFind(N)
    for j in range(M):
        if j == i:
            continue
        else:
            uni.merge(A[j], B[j])
    
    roots = [uni[x] for x in uni.root[1:]]
    counter = Counter(roots)
    if len(counter) > 1:
        res += 1

print(res)