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




"""

計算量
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: 各点までの距離と何番目に発見したかを返す
        """


        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(self.edges[p]) >= 2:
            """ 根に子が二つ異常存在する場合は、根も関節点 """
            articular.append(p)

        while True:
            if self.edges[p]:
                q = self.edges[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=True)
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

"""

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=True)
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

"""

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

"""

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

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

  def union(self, u,v):
    p1,p2 = self.find(u),self.find(v)
    if p1==p2: return
    if p1 > p2:
      p1,p2 = p2,p1
    self.parents[p1] += self.parents[p2]
    self.parents[p2] = p1

  def same(self, u,v):
    return self.find(u) == self.find(v)

N,M = map(int,input().split())
uf = UF(N+1)
ans = 0
edges = []
for _ in range(M):
  u,v = map(int,input().split())
  edges.append((u,v))

res = 0
for i in range(M):
  uf = UF(N+1)
  for j,edge in enumerate(edges):
    if i==j: continue
    uf.union(edge[0],edge[1])

  u,v = edges[i]
  if not uf.same(u,v):
    res += 1

print(res)

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

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

def dfs(f):
    if vis[f] == 1:
        return
    vis[f] = 1
    for t in l[f]:
        if f != a or t != b:
            dfs(t)

for a, b in o:
    vis = [0]*n
    dfs(a)
    if vis[b] == 0:
        ans += 1

print(ans)

Solution (Python):
def dfs(f):
    if vis[f] == 1:
        return
    vis[f] = 1 
    for t in v[f]: 
        if f != a or t != b: 
            dfs(t)

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

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

ans = 0

for a, b in e:
    vis = [0]*n
    dfs(a)
    if vis[b] == 0: 
        ans += 1

print(ans)

Solution (Python):
import networkx as nx

n, m = map(int, input().split())
g = nx.Graph()
g.add_nodes_from(range(1, n + 1))
g.add_edges_from([tuple(map(int, input().split())) for i in range(m)])

print(len(tuple(nx.bridges(g))))

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.nodes = n
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
        self.rank = [0] * n

    def find(self, i): 
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i]) 
            return self.parents[i]

    def unite(self, i, j): 
        pi = self.find(i)
        pj = self.find(j)
        if pi != pj:
            if self.rank[pi] < self.rank[pj]:
                self.sizes[pj] += self.sizes[pi]
                self.parents[pi] = pj
            else:
                self.sizes[pi] += self.sizes[pj]
                self.parents[pj] = pi
                if self.rank[pi] == self.rank[pj]:
                    self.rank[pi] += 1
    def same(self, i, j): 
        return self.find(i)==self.find(j)

    def get_parents(self): 
        for n in range(self.nodes): 
            self.find(n)
        return self.parents

adj = []
N, M = map(int,input().split())
for m in range(M):
    a,b = map(int,input().split())
    adj.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(*adj[j])
    
    if len(set(uf.get_parents()))!=1: 
        ans += 1
print (ans)

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

for i in range(m):
    temp = [[] for i in range(n+1)]
    v = [0]*(n+1)
    for j in range(m):
        if j==i:
            continue
        else:
            temp[ab[j][0]] += [ab[j][1]]
            temp[ab[j][1]] += [ab[j][0]]
    q = [1]
    
    while q:
        a = q.pop()
        for j in temp[a]:
            if v[j] == 0:
                v[j] = 1
                q.append(j)
    if v.count(1) != n:
        ans += 1
    
print(ans)

Solution (Python):
from collections import deque
n, m = map(int, input().split())
ab = []
for i in range(m):
    a, b = map(int, input().split())
    a-=1; b-=1
    ab.append((a, b))

ans = 0
for i in range(m):
    
    g = [[] for i in range(n)]
    for j in range(m):
        if i == j: continue
        a, b = ab[j]
        g[a].append(b)
        g[b].append(a)
    
    dist = [-1] * n
    dq = deque([0])
    dist[0] = 0
    while dq:
        now = dq.popleft()
        for to in g[now]:
            if dist[to]>=0: continue
            dist[to] = dist[now] + 1
            dq.append(to)
    if dist.count(-1) > 0:
        ans+=1
print(ans)

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


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

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

    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


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

ans = 0
for i in range(M):
    A, B = ways[i]
    tree = UnionFind(N)
    for j in range(M):
        if i != j:
            a, b = ways[j]
            tree.unite(a, b)
    if not tree.same(A, B):
        ans += 1

print(ans)

Solution (Python):
def bridge(G, N):
    result = set()
    label = [None] * (N+1)
    gen = 0
    cost = [0] * (N+1)
    def dfs(u, p):
        nonlocal gen
        res = 0
        for v in G[u]:
            if v == p:
                continue
            if label[v] is not None:
                if label[v] < label[u]:
                    cost[v] += 1
                    res += 1
            else:
                label[v] = gen; gen += 1
                r = dfs(v, u)
                if r == 0:
                    result.add((u, v) if u < v else (v, u))
                res += r
        res -= cost[u]
        return res
    for v in range(N):
        if not label[v]:
            label[v] = gen; gen += 1
            r = dfs(v, -1)
            assert r == 0, r
    return result

from collections import deque

N,M,*abf = map(int, open(0).read().split())
ab = [abf[i*2:i*2+2] for i in range(M)]
connected = [[] for _ in range(N+1)]
ans = 0
for a, b in ab:
    connected[a].append(b)
    connected[b].append(a)
print(len(bridge(connected,N)))

Solution (Python):
import sys
import math
import itertools
import bisect
from copy import copy,deepcopy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(map(int,input().split()))
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7


N,M = I()
links = [[] for _ in range(N)]
link = []
for i in range(M):
    a,b = I()
    links[a-1].append(b-1)
    links[b-1].append(a-1)
    link.append((a-1,b-1))
def dfs(n):
    if visited[n] == 1:
        return
    visited[n] = 1
    L = linky[n]
    for l in L:
        dfs(l)
ans = 0
for i in range(M):
    visited = [0]*N
    linky = deepcopy(links)
    a,b = link[i]
    linky[a].remove(b)
    linky[b].remove(a)
    dfs(0)
    if 0 in visited:
        ans += 1
print(ans)

Solution (Python):
def main():
    from collections import defaultdict,deque
    N,M = map(int,input().split())
    AB = []
    for _ in range(M):
        a,b = map(int,input().split())
        AB.append((a-1,b-1))
    ans = M
    for i in range(M):
        s,g = AB[i]

        edge = defaultdict(list)
        for j in range(M):
            if i == j:
                continue
            a,b = AB[j]
            edge[a].append(b)
            edge[b].append(a)

        visited = [False]*N
        targets = deque([s])
        while targets:
            t = targets.popleft()
            visited[t] = True
            for dest in edge[t]:
                if visited[dest]:
                    continue
                if dest == g:
                    ans -= 1
                    break
                targets.append(dest)
            else:
                continue
            break
    print(ans)
        
        







main()

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())
ms = [list(map(int, input().split())) for _ in range(m)]
res = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i!=j:
            uf.union(ms[j][0]-1,ms[j][1]-1)
    if len(uf.roots())!=1:
        res += 1
print(res)

Solution (Python):










import sys

def input(): return sys.stdin.readline()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip('\n') for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]

def OutH(lst, deli=' '): print(deli.join(map(str, lst)))
def OutV(lst): print('\n'.join(map(str, lst)))

sys.setrecursionlimit(10 ** 6)

int1 = lambda x: int(x) - 1

INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)








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 = iInM()
AB = iInLD1(M)





ans = 0
for i in range(M):
    
    uf = UnionFind(N)
    for j in range(M):
        if j == i:
            continue
        uf.Unite(AB[j][0], AB[j][1])
    if uf.Count(0) != N:
        ans += 1
    
print(ans)

Solution (Python):
import copy
from collections import deque
n,m = map(int,input().split())
a = [0 for _ in range(m)]
b = [0 for _ in range(m)]
joint = [[]for _ in range(n)]
for i in range(m):
    a[i],b[i] = map(int,input().split())
    a[i] -= 1
    b[i] -= 1
    joint[a[i]].append(b[i])
    joint[b[i]].append(a[i])

ans = 0
jointdef = copy.deepcopy(joint)
for i in range(m):
    joint = copy.deepcopy(jointdef)
    joint[a[i]].remove(b[i])
    joint[b[i]].remove(a[i])
    
    looked = [1 for _ in range(n)]
    looked[0] = 0
    queue = deque([0])
    while(queue):
        now = queue.popleft()
        for i in joint[now]:
            if looked[i]:
                queue.append(i)
                looked[i] = 0
    if sum(looked) != 0:
        ans += 1
print(ans)

Solution (Python):



class UnionFindTree():
    def __init__(self, n):
        self.rank = [0] * n
        self.par = [x for x in range(n)]
        
    def find(self, x):
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] > self.rank[y]:
            self.par[y] = x
        elif self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            self.rank[x] += 1
    
    def same(self, x, y):
        return (self.find(x) == self.find(y))

n, m = map(int, input().split())
ab_l = [[int(x)-1 for x in input().split()] for y in range(m)]

ans = 0

for i in range(m):
    UF = UnionFindTree(n)
    for j in range(m):
        if i != j:
            UF.unite(ab_l[j][0], ab_l[j][1])
    for j in range(1,n):
        if not UF.same(0, j):
            ans += 1
            break

print(ans)

Solution (Python):
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

from collections import deque
def dfs(pair):
    q = deque()
    q.append((1, -1, 0))
    log = [0] * n
    log[0] = 1
    while q:
        V, P, S = q.popleft()
        if S == 0:
        
        
            for new_v in G[V - 1]:
                if new_v == P:continue
                if set(pair) == {V, new_v}:continue 
                if log[new_v - 1]:continue 
                log[new_v - 1] = 1
                q.append((new_v, V, 0))
    return sum(log) == n 


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

res = 0
for t in ab:
    if dfs(t):
        
        continue
    res += 1
print(res)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.rank = [1]*n
    
    def root(self, x):
        if x == self.p[x]:
            return x
        self.p[x] = y = self.root(self.p[x])
        return y
    
    def unite(self, x, y):
        px = self.root(x); py = self.root(y)
        if px == py:
            return 0
        rx = self.rank[px]; ry = self.rank[py]
        if ry < rx:
            self.p[py] = px
        elif rx < ry:
            self.p[px] = py
        else:
            self.p[py] = px
            self.rank[px] += 1
        return 1

    def same(self, x, y):
        px = self.root(x); py = self.root(y)
        return px == py

N,M = list(map(int,input().split()))
AB = [list(map(int,input().split())) for _ in range(M)]
count = 0
for i in range(M):
    a,b = AB[i]
    union_find = UnionFind(N+10)
    for j in range(M):
        if i == j:
            continue
        union_find.unite(AB[j][0],AB[j][1])
    if not union_find.same(a,b):
        count += 1
print(count)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def dfs(v, remove):
        for u in tree[v]:
            if [u, v] == remove or [v, u] == remove:
                continue
            elif visited[u]:
                continue
            else:
                visited[u] = True
                dfs(u, remove)

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

    res = 0
    for remove in edge:
        visited = [False for _ in range(n)]
        visited[0] = True
        dfs(0, remove)
        if not all(visited):
            res += 1
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
from collections import deque
n,m = map(int,input().split())
V = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    V[a].append([b,i])
    V[b].append([a,i])
ans = 0
for i in range(m):
    q = deque([])
    reach = [0] + [-1]*n
    q.append(1)
    reach[1] = 0
    while q:
        x = q.popleft()
        for X,j in V[x]:
            if j == i:
                pass
            else:
                if reach[X] == -1:
                    q.append(X)
                    reach[X] = 0
    if -1 in reach:
        ans += 1
print(ans)

Solution (Python):
def dfs(f):
    if vis[f] == 1: return
    vis[f] = 1
    for t in V[f]:
        if f!=a or t!=b: dfs(t)

n, m = map(int, input().split())
E = [[*map(lambda x: int(x)-1, input().split())] for _ in range(m)]
V = [[] for _ in range(n)]
for a, b in E: V[a].append(b); V[b].append(a)
ans = 0
for a, b in E:
    vis = [0]*n
    dfs(a)
    if vis[b] == 0: ans += 1
print(ans)

Solution (Python):
def dfs(a, b, f):
    if vis[f] == 1: return
    vis[f] = 1
    for t in V[f]:
        if f!=a or t!=b: dfs(a, b, t)

n, m = map(int, input().split())
E, V = [], [[] for _ in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    E.append([a, b])
    V[a].append(b); V[b].append(a)
ans = 0
for a, b in E:
    vis = [0]*n
    dfs(a, b, a)
    if vis[b] == 0: ans += 1
print(ans)

Solution (Python):
def dfs(a, b, f):
    if vis[f] == 1: return
    vis[f] = 1
    for t in V[f]:
        if f!=a or t!=b: dfs(a, b, t)

n, m = map(int, input().split())
E = [[*map(lambda x: int(x)-1, input().split())] for _ in range(m)]
V = [[] for _ in range(n)]
for a, b in E: V[a].append(b); V[b].append(a)
ans = 0
for a, b in E:
    vis = [0]*n
    dfs(a, b, a)
    if vis[b] == 0: ans += 1
print(ans)