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

def sample():
    uf = UnionFind(6)
    print(uf.parents)
    uf.union(0, 2)
    print(uf.parents)
    uf.union(1, 3)
    print(uf.parents)
    uf.union(4, 5)
    print(uf.parents)

def atc001():
    n, q = map(int, input().split())
    uf = UnionFind(n)
    for i in range(q):
        p, a, b = map(int, input().split())
        if p == 0:
            uf.union(a, b)
        else:
            if uf.same(a, b):
                print("Yes")
            else:
                print("No")

def abc049():
    n, k, l = map(int, input().split())
    road = UnionFind(n)
    train = UnionFind(n)
    for i in range(k):
        p, q = map(int, input().split())
        road.union(p - 1, q - 1)
    for i in range(l):
        p, q = map(int, input().split())
        train.union(p - 1, q - 1)

    pair = []
    pair_cnt = {}
    for i in range(n):
        t, r = road.find(i), train.find(i)
        pair.append([t, r])
        key = t * (10 ** 6) + r
        if key in pair_cnt:
            pair_cnt[key] += 1
        else:
            pair_cnt[key] = 1

    for i in range(n):
        [t, r] = pair[i]
        key = t * (10 ** 6) + r
        print(pair_cnt[key], end = " ")

def arc097():
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    pair = UnionFind(n)
    for i in range(m):
        x, y = map(int, input().split())
        pair.union(x - 1, y - 1)

    cnt = 0
    for i in range(n):
        if pair.same(i, p[i] - 1):
            cnt += 1
    print(cnt)

def arc032():
    n, m = map(int, input().split())
    road = UnionFind(n)
    for i in range(m):
        a, b = map(int, input().split())
        road.union(a - 1, b - 1)

    print(road.group_count() - 1)

def abc075():
    n, m = map(int, input().split())
    input_list = [list(map(int, input().split())) for _ in range(m)]
    cnt = 0
    for i in range(m):
        road = UnionFind(n)
        for j in range(m):
            p1 = input_list[j][0] - 1
            p2 = input_list[j][1] - 1
            if i != j:
                road.union(p1, p2)
        if road.group_count() >= 2:
            cnt += 1

    print(cnt)
abc075()

Solution (Python):
n,m=map(int,input().split())
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())
ab=[]
for _ in range(m):
  a,b=map(int,input().split())
  ab.append((a-1,b-1))
ans=0
uf=UnionFind(n)
for i in range(m):
  uf.__init__(n)
  for j in range(m):
    if j==i:
      continue
    a,b=ab[j]
    uf.union(a,b)
  if uf.group_count()==2:
    ans+=1
print(ans)

Solution (Python):
from collections import Counter

n , m = map(int, input().split())
err = 0
ans = 0

par = [0] * n
rank = [0] * n


for i in range(n):
    par[i] = i
    rank[i] = 0


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

def unite(x , y):
    rx = find(x)
    ry = find(y)
    
    if rx == ry:
        return
    
    if rank[rx] < rank[ry]:
        par[rx] = ry
    elif rank[rx] > rank[ry]:
        par[ry] = rx
    else:
        par[ry] = x
        rank[rx] += 1

a = [0] * m
b = [0] * m

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

ans = 0
for i in range(m):
    for v in range(n):
        par[v] = v
        rank[v] = 0
        
    for j in range(m):
        if j == i:
            continue
        unite(a[j]-1 , b[j]-1)
        r = [find(k) for k in range(n)]
    if len(Counter(r)) != 1:
        ans += 1
        
print(ans)

Solution (Python):
class Unionfind():

    def __init__(self, n):
        self.par = [-1]*n

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

    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return False
        if self.par[x]>self.par[y]:
            x,y = y,x
        self.par[x]+=self.par[y]
        self.par[y] = x
        return True

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

    def count_group():
        c = 0
        for i in range(len(self.par)):
            if self.par[i]<0:
                c+=1
        return c

n,m = map(int, input().split())
a = []
for i in range(m):
    b = list(map(int, input().split()))
    b[0]-=1
    b[1]-=1
    a.append(b)
ans = 0
for i in range(m):
    uf = Unionfind(n)
    for j in range(m):
        if i==j:
            continue
        uf.union(a[j][0],a[j][1])
    if uf.same(a[i][0],a[i][1]):
        continue
    else:
        ans+=1
print(ans)

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

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

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

    def 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())
L = [[] for i in range(M)]
for i in range(M):
  L[i]=list(map(int,input().split()))

def chk(LL):
  uf = UnionFind(N)
  for l in LL:
    uf.union(l[0]-1, l[1]-1)
  return uf.group_count()

ret = 0
for i in range(M):
  LL = L[:]
  LL.pop(i)
  if chk(LL)>1:
    ret+=1
print(ret)

Solution (Python):



import sys
sys.setrecursionlimit(10**8)

def main():
  n, m = map(int, input().split())
  tree = [[] for _ in range(n)]
  for im in range(m):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
  
  def get_bridge(tree):
    bridge_targets = []
    n = len(tree)
    pres = [0 for _ in range(n)]
    lows = [0 for _ in range(n)]
    visited = [0 for _ in range(n)]
    used_edges = []
    def dfs(inode, count=0):
      pres[inode] = lows[inode] = count
      visited[inode] = 1
      for ichild in tree[inode]:
        if not visited[ichild]:
          used_edges.append((inode, ichild))
          count = dfs(ichild, count+1)
        if lows[ichild] < lows[inode]:
          if not (ichild, inode) in used_edges:
            lows[inode] = lows[ichild]
      if pres[inode] == lows[inode]:
        bridge_targets.append(inode)
      
      return count
    dfs(0)
    return [(s, t) for (s, t) in used_edges if t in bridge_targets]
  bridges = get_bridge(tree)
  print(len(bridges))
  
if __name__=='__main__':
  main()

Solution (Python):
n , m = map(int, input().split())
combis = [set(list(map(int, input().split()))) for i in range(m)]
count = 0
for i in range(m):
    combis_x = combis[0:i] + combis[i+1:m]
    islands = []
    for combi in combis_x:
        
        if not islands:
            islands.append(combi)
            continue
        
        new_islands = islands
        joint_i = []
        for j, island in enumerate(islands):
            if not island.isdisjoint(combi):
                new_islands[j] = island | combi
                joint_i.append(j)
        else:
            if not joint_i:
                new_islands.append(combi)
            elif len(joint_i) == 2:
                new_islands[joint_i[0]] = new_islands[joint_i[0]] | new_islands[joint_i[1]]
                new_islands.pop(joint_i[1])
        islands = new_islands

    
    if len(islands) == 1 and len(islands[0]) == n:
        continue
    elif len(islands) == 1 and len(islands[0]) == n - 1:
        count += 1
    else:
        count += 1
print(count)

Solution (Python):
def dfs(v, p, a):
    global ans
    if pre[v] != -1:
        low[a] = min(low[a], low[v])
        return low[a]
    pre[v] = p
    low[v] = p
    for u in links[v]:
        if u == a:
            continue
        low[v] = min(low[v], dfs(u, p + 1, v))
    if pre[v] == low[v]:
        ans += 1
    return low[v]
  
n, m = map(int, input().split())
links = [set() for _ in range(n)]
 
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
 
ans = 0
pre = [-1] * n
low = [-1] * n
dfs(0, 0, None)
print(ans - 1)
'''
まず、頂点を１つ選び、DFSを開始する。
各頂点には、pre、lowという２つのデータを記録する。
preは、DFS木の行きがけ順（pre-order）の値を保持する。
lowは、DFS木でその頂点から到達しうる頂点のpreの最小値を保持する。
初期値はその頂点のpreである。
次の頂点が、すでに訪れてある（preの値が存在する）場合は、
自分のlowを、次の頂点のlowと比べて小さい方に更新する。
次の頂点をまだ訪れていない場合は、その頂点に対してDFSを続ける。
そして、その頂点へのDFSが終了した際に、lowがpreより小さくなっていれば、
その頂点へ向かう辺は橋である。
'''

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

    
    def find(self, x):
        
        root = x
        queue = [x]
        data = []
        while queue:
            now = queue.pop()
            if self.par[now] == now:
                root = now
            else:
                
                data.append(now)
                queue.append(self.par[now])
        
        for y in data:
            self.par[y] = root
        return root

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return True
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.count[y] += self.count[x]
            self.count[x] = 0
        else:
            self.par[y] = x
            self.count[x] += self.count[y]
            self.count[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        return False

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

    
    def size(self, x):
        q = UnionFind.find(self, x)
        return self.count[q]


n, m = map(int, input().split())
data = [tuple(map(lambda z: int(z) - 1, input().split())) for _ in range(m)]
ans = 0
for i in range(m):
    u = UnionFind(n)
    for j in range(m):
        if i == j:
            continue
        u.union(data[j][0], data[j][1])
    ans += 0 if u.same_check(data[i][0], data[i][1]) else 1

print(ans)

Solution (Python):
from collections import defaultdict
import queue

N,M=map(int,input().split())
ab=[]
d=defaultdict(list)
for i in range(M):
    a,b=map(int,input().split())
    ab.append((a,b))
    d[a].append(b)
    d[b].append(a)


ans=0
for i in range(M):
    Remove=ab[i]
    d[Remove[0]].remove(Remove[1])
    d[Remove[1]].remove(Remove[0])
    
    dist=[False]*N
    q=queue.Queue()
    q.put(list(d.keys())[0])

    while not q.empty():
        From=q.get()
        dist[From-1]=True
        for g in d[From]:
            if dist[g-1]==False:
                q.put(g)
    
    if False in dist:
        ans+=1

    d[Remove[0]].append(Remove[1])
    d[Remove[1]].append(Remove[0])

print(ans)

Solution (Python):
import numpy as np
import sys

class UnionFind:
	def __init__(self, n):
		self.n = n
		self.root = [-1]*(n+1)
		self.rnk = [0]*(n+1)
		self.Maxroot = -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]
			if self.root[x] < self.Maxroot:
				self.Maxroot = self.root[x]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			if self.root[y] < self.Maxroot:
				self.Maxroot = self.root[y]
			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)] * (-1)

	def Max_tree(self):
		return min(self.root) * (-1)

n, m = map(int, input().split())
AB = np.array(sys.stdin.read().split(), np.int64)
A = AB[::2]
B = AB[1::2]

ans = 0
for i in range(m):
	solve = UnionFind(n+1)
	for j in range(m):
		if j == i:
			continue
		
		solve.Unite(A[j],B[j])

	if solve.Max_tree() != n:
		ans += 1

print(ans)

Solution (Python):
import numpy as np
import sys 

N, M = map(int, input().split())
AB = np.array(sys.stdin.read().split(), np.int64)
A = AB[::2]
B = AB[1::2]
E = np.zeros([N+1, N+1], np.int64)

np.add.at(E,(A,B),1)
np.add.at(E,(B,A),1)

def dfs(E):
	flg = np.zeros(1+N)
	flg[0] = 0
	q = [1]

	while q:
		cp = q.pop()
		flg[cp] = 1

		for n in range(1,N+1):
			if flg[n] == 0 and E[cp][n] == 1:
				flg[n] = 1
				q.append(n)

	if flg.sum() == N:
		return 0
	else:
		return 1

ans = 0
for i in range(1,N+1):
	for j in range(i+1,N+1):
		if E[i,j] == 0:
			continue

		E[i,j] = 0
		E[j,i] = 0

		ans += dfs(E)

		E[i,j] = 1
		E[j,i] = 1

print(ans)

Solution (Python):
import math
import bisect
import heapq
from collections import deque

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

p = [[0] * n for _ in range(n)]

c, d = [0] * m, [0] * m
for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    c[i],d[i] = a,b

    p[a][b], p[b][a] = 1, 1


def dfs(p):
    seen = [False] * n
    s = 0
    deq = deque([0])
    while deq:
        s = deq.pop()
        seen[s] = True
        for i in range(n):
            if p[s][i] == 0 or seen[i]:
                continue
            deq.append(i)

    for i in range(n):
        if not seen[i]:
            return 1
    return 0


ans = 0

for i in range(m):
    a,b = c[i],d[i]
    p[a][b], p[b][a] = 0, 0

    ans += dfs(p)
    p[a][b], p[b][a] = 1, 1

print(ans)

Solution (Python):
import math
import bisect
import heapq
from collections import deque

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

p = [[0] * n for _ in range(n)]

c, d = [0] * m, [0] * m
for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    c[i],d[i] = a,b

    p[a][b], p[b][a] = 1, 1


def dfs(p,n):
    seen = [False] * n
    s = 0
    deq = deque([0])
    while deq:
        s = deq.pop()
        seen[s] = True
        for i in range(n):
            if p[s][i] == 0 or seen[i]:
                continue
            deq.append(i)

    for i in range(n):
        if not seen[i]:
            return 1
    return 0


ans = 0

for i in range(m):
    a,b = c[i],d[i]
    p[a][b], p[b][a] = 0, 0

    ans += dfs(p,n)
    p[a][b], p[b][a] = 1, 1

print(ans)

Solution (Python):
def find(x):
    if x != T[x][0]:
        while x!=T[x][0]:
            x = T[x][0]
    return x
def union(x,y):
    rt0 = find(x)
    rt1 = find(y)
    if T[rt0][1]>T[rt1][1]:
        T[rt1][0] = rt0
    elif T[rt0][1]==T[rt1][1]:
        T[rt1][0] = rt0
        T[rt0][1] += 1
    else:
        T[rt0][0] = rt1
        
N,M = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(M)]
B = []
for j in range(M):
    T = {i:[i,0] for i in range(1,N+1)}
    for i in range(M):
        if i==j:continue
        a,b = A[i]
        union(a,b)
    R = [0 for _ in range(N+1)]
    for k in range(1,N+1):
        rt = find(k)
        if R[rt]==0:
            R[rt]=1
    if sum(R)>1:
        B.append(j)
print(len(B))

Solution (Python):

from sys import stdin
N, M = [int(x) for x in stdin.readline().rstrip().split()]
adj_matrix = [[0]*(N+2) for i in range(N+2)]

edges = []

for i in range(M):
    a, b = [int(x) for x in stdin.readline().rstrip().split()]
    edges.append((a, b))
    adj_matrix[a][b] = 1
    adj_matrix[b][a] = 1

def dfs(i):
    if is_visited[i]:
        return False

    is_visited[i] = True

    for node,bi in enumerate(adj_matrix[i][:-1]):
        if bi == 1:
            dfs(node)

ans = 0
for j, k in edges:
    is_visited = [False for i in range(N+1)]
    adj_matrix[j][k] = 0
    adj_matrix[k][j] = 0
    dfs(1)
    if not all(is_visited[1:]):
        ans += 1
    adj_matrix[j][k] = 1
    adj_matrix[k][j] = 1
        
print(ans)

Solution (Python):
from copy import deepcopy

n, m = map(int, input().split())
graph = [[] for i in range(n)]
arcs = []
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    arcs.append((a, b))
answer = 0
for a, b in arcs:
    graph_ = deepcopy(graph)
    graph_[a].remove(b)
    graph_[b].remove(a)

    initial = 0
    stack = []
    history = set()
    stack.append(initial)
    history.add(initial)

    while stack:
        node = stack.pop()
        for new_node in graph_[node]:
            if new_node not in history:
                stack.append(new_node)
                history.add(new_node)
    
    if len(history) != n:
        answer += 1

print(answer)

Solution (Python):

import math
import heapq
import bisect
import numpy as np
from collections import Counter


N,M = map(int, input().split())
G = [[] for _ in range(N)]

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

d = [0] + [-1]*(N-1)

def dfs(n):
    d[n] = 0
    for v in G[n]:
        if d[v] == -1:
            dfs(v)

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

    dfs(0)

    if -1 in d:
        ans += 1
    
    for i in range(1,N):
        d[i] = -1
    G[a].append(b)
    G[b].append(a)

print(ans)

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

ans = 0
for i in range(M) :
    a, b = edge[i]
    G[a][b] = G[b][a] = 0
    visited = [0]*N
    stuck = [0]
    while stuck :
        next = stuck.pop()
        visited[next] = 1
        for i in range(N) :
            if G[next][i] == 1 :
                if visited[i] == 1 :
                    continue
                if i in stuck :
                    continue
                stuck.append(i)
    G[a][b] = G[b][a] = 1
    if 0 in visited :
        ans += 1

print(ans)

Solution (Python):

import sys
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))

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

def main():
    N,M=MAP()
    
    edges = []
    for _ in range(M):
        a,b = MAP()
        edges.append((a-1,b-1))

    answer = 0
    for i in range(M): 
        uf = UnionFind(N)

        for j in range(M):
            if i == j:
                continue

            a,b = edges[j]
            uf.union(a,b)
        if uf.group_count() > 1:
            answer += 1
    print(answer)
    return

if __name__ == '__main__':
    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 unite(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)

n, m = map(int, input().split())
edge = []
for i in range(m):
    a, b = map(int, input().split())
    edge.append([a - 1, b - 1])
ans = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i != j: uf.unite(edge[j][0], edge[j][1])
    ans += not uf.same(edge[i][0], edge[i][1])
print(ans)

Solution (Python):
from collections import deque

def DFS_Stack_matrix(matrix,start): 
    list_nodes = [start]
    n = len(matrix[0])
    stac = deque()
    flag = False
    while len(list_nodes) <  n :
        for i in range(n):
            if matrix[start][i] == 1:
                stac.append(i)  
        while stac:
            start = stac.pop() 
            if start in list_nodes:
                continue
            else:
                list_nodes.append(start) 
                break
        else:
            break
    else:
        flag = True
    return flag


n,m = map(int,input().split())
mat = [[0]*n for i in range(n)]
ind = []
for i in range(m):
    u,v = map(int,input().split())
    mat[u-1][v-1] =1
    mat[v-1][u-1] = 1
    ind.append([u,v])

cnt = 0
for u,v in ind:
    mat[u-1][v-1] = 0
    mat[v-1][u-1] = 0
    if DFS_Stack_matrix(mat,0):
        pass
    else:
        cnt +=1
    mat[u-1][v-1] = 1
    mat[v-1][u-1] = 1
print(cnt)

Solution (Python):



parent = None


def root(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = root(parent[a])
        return parent[a]


def is_same(a, b):
    return root(a) == root(b)


def unite(a, b):
    
    
    ra = root(a)
    rb = root(b)
    
    if ra == rb:
        return
    parent[ra] = rb




n, m = map(int, input().split())
grid = []

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



ans = 0
for i in range(m):
    
    parent = [k for k in range(n)]
    

    for j, e in enumerate(grid):
        
        if j == i:
            continue
        a, b = e
        unite(a, b)

    
    a, b = grid[i]
    if not is_same(a, b):
        
        ans += 1
    

print(ans)

Solution (Python):
from collections import deque
n,m = map(int,input().split())
to = [[] for _ in range(n)]
v = []
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
    v.append((a,b))
ans = m
seen = [False]*n
q = deque()
for i in range(m):
    a,b = v[i]
    q.clear()
    q.append((a,-1))
    for j in range(n): seen[j] = False
    flag = True
    while q and flag:
        cur,prev = q.popleft()
        seen[cur] = True
        for nxt in to[cur]:
            if nxt == b:
                if cur == a: continue
                ans -= 1
                flag = False
                break
            if nxt == prev: continue
            if seen[nxt]: continue
            q.append((nxt,cur))
print(ans)

Solution (Python):
from collections import deque
n,m = map(int,input().split())
to = [[] for _ in range(n)]
v = []
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
    v.append((a,b))
ans = m
seen = [False]*n
stk = deque()
for i in range(m):
    a,b = v[i]
    stk.clear()
    stk.append((a,-1))
    for j in range(n): seen[j] = False
    flag = True
    while stk and flag:
        cur,prev = stk.pop()
        seen[cur] = True
        for nxt in to[cur]:
            if nxt == b:
                if cur == a: continue
                ans -= 1
                flag = False
                break
            if nxt == prev: continue
            if seen[nxt]: continue
            stk.append((nxt,cur))
print(ans)

Solution (Python):
from collections import deque
n,m = map(int,input().split())
to = [[] for _ in range(n)]
v = []
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
    v.append((a,b))
ans = m
seen = [False]*n
stk = deque()
for i in range(m):
    a,b = v[i]
    stk.clear()
    stk.append((a,-1))
    for j in range(n): seen[j] = False
    seen[a] = True
    flag = True
    while stk and flag:
        cur,prev = stk.pop()
        seen[cur] = True
        for nxt in to[cur]:
            if nxt == b:
                if cur == a: continue
                ans -= 1
                flag = False
                break
            if nxt == prev: continue
            if seen[nxt]: continue
            stk.append((nxt,cur))

print(ans)

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

node_list = [[False]*n for i in range(n)]
graph = [0]*m
for i in range(m):
    a, b = map(int, input().split())
    graph[i] = [a, b]
    node_list[a-1][b-1] = True
    node_list[b-1][a-1] = True

ans = m
for i in range(m):
    p, q = graph[i][0], graph[i][1]
    node_list[p-1][q-1] = False
    node_list[q-1][p-1] = False
    already = [False]*n
    not_yet = []
    already[0] = True
    for j in range(n):
        if node_list[0][j]:
            not_yet.append(j)
    while not_yet:
        k = not_yet[-1]
        not_yet.pop()
        already[k] = True
        for j in range(n):
            key = node_list[k][j]
            if key:
                if not already[j]:
                    not_yet.append(j)
    node_list[p-1][q-1] = True
    node_list[q-1][p-1] = True
    if all(already):
        ans -= 1
  
print(ans)

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


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

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

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

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

node_list = []
for i in range(m):
    node_list.append([int(x) for x in input().split()])

ans = 0
for i in range(m):
    par = [-1 for _ in range(n)]
    for j in range(m):
        if i == j:
            continue
        else:
            union(node_list[j][0]-1, node_list[j][1]-1)
    limit = 2
    flag = False
    for value in par:
        if value < 0:
            limit -= 1
        if not limit:
            flag = True
            break
    if flag:
        ans += 1
print(ans)

Solution (Python):

n,m=map(int,input().split())
graph=[[0]*n for _ in range(n)]
visited=[0]*n
hen=[]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    hen.append([a,b])
    graph[a][b]=graph[b][a]=1

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


ans=0
for i in range(m):
    a,b=hen[i]
    graph[a][b]=graph[b][a]=0
    visited=[0]*n
    dfs(0)
    bridge=False
    for j in range(n):
        if visited[j]==0:
            bridge=True
    if bridge:
        ans+=1
    graph[a][b]=graph[b][a]=1

print(ans)