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):
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline
input = sys.stdin.buffer.readline





def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(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=MI()
	li=[]
	for _ in range(m):
		a,b=MI()
		a-=1
		b-=1
		li.append([a,b])
	

	ans=0

	for i in range(m):
		UF=UnionFind(n)
		for j in range(m):
			if i==j:
				continue
			UF.union(li[j][0],li[j][1])
		ans+=(UF.group_count()==1)
	print(m-ans)


if __name__ == "__main__":
	main()

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

from collections import defaultdict
from collections import deque
d=defaultdict(list)
for l in L:
    d[l[0]-1].append(l[1]-1)
    d[l[1]-1].append(l[0]-1)




def check_path(hen):
        
    visit=[False]*n
    q=deque([0])
    


    
    while q:
        node = q.popleft()

        visit[node]=True
        Nexts = d[node]
        for nxt in Nexts:
            if visit[nxt]:

                continue
            
            if node+1 not in L[hen] or nxt+1 not in L[hen]:

                q.append(nxt)
    

    return all(visit)
    
cnt=0
for i in range(m):
    if not check_path(i):
        cnt+=1

print(cnt)

Solution (Python):
import collections
def bfs(start):
    d = [-1]*n
    d[start] = 0
    q = collections.deque([start])
    while q:
        c = q.popleft()
        next_v = edge[c] 
        for v in next_v:
            if d[v] == -1:
                q.append(v)
                d[v] = d[c] + 1
    return d

n,m = map(int,input().split())
koho = []
edge = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    koho.append([a,b])
    edge[a].append(b)
    edge[b].append(a)
cnt = 0
for i in range(m):
    edge = [[] for _ in range(n)]
    for j in range(m):
        if i == j:
            continue
        edge[koho[j][0]].append(koho[j][1])
        edge[koho[j][1]].append(koho[j][0])
    a = bfs(0)
    flag = 0
    for j in a:
        if j == -1:
            flag = 1
    if flag == 1:
        cnt+=1
print(cnt)

Solution (Python):
import copy
from collections import deque

n , m = map(int,input().split())
route = [[] for i in range(n+1)]
nuku = []
for i in range(m):
    a , b = map(int,input().split())
    route[a].append(b)
    route[b].append(a)
    nuku.append([a,b])
ans = 0
for a , b in nuku:
    kari = copy.deepcopy(route)
    kari[a].remove(b)
    kari[b].remove(a)
    d = deque()
    d.append(1)
    tansaku = [True for i in range(n+1)]
    cou = 0
    tansaku[1] = False
    while d:
        cou += 1
        now = d.popleft()
        for k in kari[now]:
            if tansaku[k]:
                tansaku[k] = False
                d.append(k)
    if cou != n:
        ans += 1
print(ans)

Solution (Python):
n,m = map(int,input().split())
graph = {i:[] for i in range(1,n+1)}

for _ in range(m):
  a,b = map(int,input().split())
  graph[a].append(b)
  graph[b].append(a)
  
bridge = set([])

ans = 0
while 1:
  count = 0
  for i in range(1,n+1):
    if len(graph[i]) == 1:
      count += 1
      a = graph[i][0]
      graph[a].remove(i)
      graph[i] = []
  ans += count
  if count == 0:
    break
  else:
    count = 0
print(ans)

Solution (Python):
import sys

def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))

def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]

def to_bin(x: int) -> str: return format(x, 'b') 
def to_oct(x: int) -> str: return format(x, 'o') 
def to_hex(x: int) -> str: return format(x, 'x') 
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i):
            is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]

from itertools import accumulate as acc, combinations as combi, product, combinations_with_replacement as combi_dup
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left


def main():
    n, m = MII()
    ab = [MIIZ() for _ in range(m)]
    cnt = 0
    for i in range(m):
        graph = [[] for _ in range(n)]
        for k,(a,b) in enumerate(ab):
            if i == k: continue
            graph[a].append(b)
            graph[b].append(a)
        dist = [-1]*n
        dq = deque()
        dist[0] = 0
        dq.append(0)
        while dq:
            v = dq.popleft()
            for nv in graph[v]:
                if dist[nv] != -1: continue
                dist[nv] = dist[v] + 1
                dq.append(nv)
        if -1 in dist:
            cnt += 1
    print(cnt)



if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
edge=[[] for _ in range(n+1)]
eab=[]
for i in range(m):
    a,b=map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    eab.append([a-1,b-1])
 
def dfs(visited,count,node):
    visited[node]=True
    count+=1
    ev=edge[node]
    for node in ev:
        if visited[node]:
            continue
        else:
            count=dfs(visited,count,node)
    return count

ans=0
for i in range(m):
    a,b=eab[i]
    edge[a].remove(b)
    edge[b].remove(a)
    ci=dfs([False for _ in range(n)],0,0)
    if ci!=n:
        ans+=1
    edge[a].append(b)
    edge[b].append(a)
print(ans)

Solution (Python):
from collections import deque
 
def dfs(n, start, graph):
  visited = [False] * n
  stack = deque()
  stack.append(start)
  visited[start] = True
  while stack:
    q = stack.popleft()
    nxts = graph[q]
    for nxt in nxts:
      if not visited[nxt]:
        visited[nxt] = True
        stack.append(nxt)
  return visited
 
n, m = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(m)]
 
ans = 0
for i in range(m):
  graph = [[] for _ in range(n)]
  for itr, (a, b) in enumerate(edge):
    if itr != i:
      graph[a - 1].append(b - 1)
      graph[b - 1].append(a - 1)
 
  if not all(dfs(n, 0, graph)):
    ans += 1
print(ans)

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


def dfs(curr):
    visit[curr] = 1
    for x in graph[curr]:
        if visit[x] == 0:
            dfs(x)


ans = 0
for i in range(m):
    temp = ab[:i] + ab[i + 1:]
    graph = [[] for _ in range(n + 1)]
    for a, b in temp:
        graph[a].append(b)
        graph[b].append(a)

    visit = [0] * (n + 1)
    dfs(1)

    if sum(visit[1:]) != n:
        ans += 1

print(ans)

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

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

n,m = map(int,input().split())
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):
    u = UnionFind(n)
    for j in range(m):
        if i==j:continue
        a,b = A[j]-1,B[j]-1
        u.union(a,b)
    for j in range(n):
        u.find(j)
    if len(set(u.parents))!=1:
        ans+=1
print(ans)

Solution (Python):
from sys import setrecursionlimit

class UnionFind:
    def __init__(self, n):
        
        
        self.par = [i for i in range(n + 1)]
        
        self.rank = [0] * (n + 1)
        self.size = [1] * (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 check(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
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def count_group(self, n):
        return len({self.find(x) for x in range(1, n + 1)})

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

cnt = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i == j:continue
        a, b = ab[j]
        uf.union(a, b)

    if uf.count_group(n) != 1:cnt += 1
print(cnt)

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(G, a, b):
    
    q=deque()
    q.append((1, -1, 0))
    log = [0] * n
    log[0] = 1
    while q:
        V,P,S=q.pop()
        if S==0:
            
            
            for new_v in G[V-1]:
                if {a, b} == {new_v, V}:continue
                if new_v==P:continue
                if log[new_v - 1]:continue
                log[new_v - 1] = 1
                q.append((new_v,V,0))

    return sum(log) != n

n, m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
G = Graph(ab)
'''
ab一個を除いた時に連結かどうか調べる
'''

ans = 0
for a, b in ab:
    if dfs(G, a, b):ans += 1
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(G, a, b):
    
    q=deque()
    q.append((1, -1, 0))
    log = [0] * n
    log[0] = 1
    while q:
        V,P,S=q.pop()
        if S==0:
            
            
            for new_v in G[V-1]:
                if {a, b} == {new_v, V}:continue
                if new_v==P:continue
                if log[new_v - 1]:continue
                log[new_v - 1] = 1
                q.append((new_v,V,0))

    return sum(log) != n

n, m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
G = Graph(ab)
'''
ab一個を除いた時に連結かどうか調べる
'''

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

Solution (Python):
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10 ** 7)

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

n, m = na()
ab = nan(m)

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

def bfs(va, vb):
    q = deque()
    q.append((0, 0))
    dist = [-1] * n
    while len(q):
        p, d = q.popleft()
        if dist[p] != -1:
            continue
        dist[p] = d
        for nv in g[p]:
            if (p == va and nv == vb) or (p == vb and nv == va):
                continue
            q.append((nv, dist[p] + 1))
    
    for i in range(n):
        if dist[i] == -1:
            return 1
    return 0

proc = [False] * n
def dfs(v, p):
    if proc[v]:
        return 0
    proc[v] = True
    res = 0
    for nv in g[v]:
        if nv == p:
            continue
        res += bfs(nv, v)
        res += dfs(nv, v)
    return res

print(dfs(0, -1))

Solution (Python):
from sys import setrecursionlimit

class UnionFind:
    def __init__(self, n):
        
        
        self.par = [i for i in range(n + 1)]
        
        self.rank = [0] * (n + 1)
        self.size = [1] * (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 check(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
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def count_group(self, n):
        return len({self.find(x) for x in range(1, n + 1)})

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

cnt = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i == j:continue
        a, b = ab[j]
        uf.union(a, b)

    if uf.count_group(n) != 1:cnt += 1
print(cnt)

Solution (Python):
import copy


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


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    if par[x] > par[y]:
        x, y = y, x
    par[y] = x
    return True


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


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


N, M = map(int, input().split())
Road = [tuple(map(int, input().split())) for _ in range(M)]
ans = 0
for i in range(M):
    Roadi = copy.deepcopy(Road)
    par = [-1] * N
    for j, r in enumerate(Road):
        if i == j:
            continue
        ra, rb = r
        ra -= 1
        rb -= 1
        unite(ra, rb)
    if par.count(-1) > 1:
        ans += 1

print(ans)

Solution (Python):



from collections import deque

def dfs(n, start, graph):
  visited = [False] * n
  stack = deque()
  stack.append(start)
  visited[start] = True
  while stack:
    q = stack.popleft()
    nxts = graph[q]
    for nxt in nxts:
      if not visited[nxt]:
        visited[nxt] = True
        stack.append(nxt)
  return visited

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

ans = 0
for i in range(m):
  graph = [[] for _ in range(n)]
  for itr, (a, b) in enumerate(edge):
    if itr != i:
      graph[a - 1].append(b - 1)
      graph[b - 1].append(a - 1)

  if not all(dfs(n, 0, graph)):
    ans += 1

print(ans)

Solution (Python):
from collections import deque

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

A,B=[0]*M,[0]*M
graph=[[] for _ in range(N)]
for i in range(M):
    A[i],B[i]=map(int,input().split())
    A[i]-=1
    B[i]-=1
    graph[A[i]].append(B[i])
    graph[B[i]].append(A[i])

def bfs(graph,visited,start):
    queue=deque([start])
    visited[start]=True
    while queue:
        vartex=queue.popleft()
        for new_vartex in graph[vartex]:
            if visited[new_vartex]==False:
                visited[new_vartex]=True
                queue.append(new_vartex)
    
    if False in visited:
        return False
    else:
        return True

ans=0
for i in range(M):
    if i == 0:
        graph[A[0]].remove(B[0])
        graph[B[0]].remove(A[0])
    else:
        graph[A[i]].remove(B[i])
        graph[B[i]].remove(A[i])
        graph[A[i-1]].append(B[i-1])
        graph[B[i-1]].append(A[i-1])
    
    visited=[False]*N
    if bfs(graph,visited,0):
        continue
    else:
        ans+=1
print(ans)

Solution (Python):
import numpy as np
import copy as cp

def isTree(graph,know=[],now=0):
    if not know: know = [0]*len(graph[0])
    know[now] = 1
    for next in range(n):
        if know[next]==1 or graph[now][next]==0: continue
        else: isTree(graph,know,next)
    if all(know): return 1
    else: return 0

n,m = map(int,input().split())
ab = np.array([list(map(int,input().split()))for i in range(m)])
a,b = ab.T[0]-1, ab.T[1]-1

G = [[0]*n for i in range(n)]
for i in range(m):
    aa,bb = a[i],b[i]
    G[aa][bb],G[bb][aa] = 1,1


ans = 0
for i in range(m):
    aa,bb = a[i],b[i]
    tree = cp.deepcopy(G)
    tree[aa][bb],tree[bb][aa] = 0,0
    if not isTree(tree): ans += 1

print(ans)

Solution (Python):
import numpy as np
import copy as cp

def isTree(now=0):
    know[now] = 1
    for next in range(n):
        if know[next]==1 or graph[now][next]==0: continue
        else: isTree(next)
    if all(know): return 1
    else: return 0


n, m = map(int,input().split())
ab = np.array([list(map(int,input().split())) for i in range(m)])
a,b = ab.T[0]-1,ab.T[1]-1


G = [[0] * n for _ in range(n)]
for aa,bb in zip(a,b): G[aa][bb],G[bb][aa] = 1,1

ans = 0
for x,y in zip(a,b):
    graph = cp.deepcopy(G)
    graph[x][y],graph[y][x] = 0,0
    know = [0]*(n)
    if not isTree(): ans += 1

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline  
sys.setrecursionlimit(10 ** 7)  


def dfs(G, v, visited):
    """G: graph, v: vertex"""
    visited[v] = True
    for c in G[v]:
        if visited[c]:
            continue
        dfs(G, c, visited)


def main():
    N, M = map(int, input().split())
    a = [None] * M
    b = [None] * M
    G = [[] for _ in range(N)]
    for i in range(M):
        a[i], b[i] = map(int, input().split())
        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])

        visited = [False] * N
        visited[0] = True
        dfs(G, 0, visited)

        if visited.count(True) != N:
            ans += 1

        
        G[a[i]].append(b[i])
        G[b[i]].append(a[i])

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline


def dfs(G, v, visited):
    visited[v] = True
    stack = deque([v])
    while stack:
        v = stack.pop()
        for u in G[v]:
            if visited[u]:
                continue
            visited[u] = True
            stack.append(u)


def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    a = [0] * M
    b = [0] * M
    for i in range(M):
        a[i], b[i] = map(int, input().split())
        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])

        visited = [False] * N
        dfs(G, 0, visited)

        if not all(visited):
            ans += 1

        G[a[i]].append(b[i])
        G[b[i]].append(a[i])

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline


def bfs(G, v, visited):
    visited[v] = True
    queue = deque([v])
    while queue:
        v = queue.popleft()
        for u in G[v]:
            if visited[u]:
                continue
            visited[u] = True
            queue.append(u)


def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    a = [0] * M
    b = [0] * M
    for i in range(M):
        a[i], b[i] = map(int, input().split())
        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])

        visited = [False] * N
        bfs(G, 0, visited)

        if not all(visited):
            ans += 1

        G[a[i]].append(b[i])
        G[b[i]].append(a[i])

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline


def bfs(G, v, visited):
    visited[v] = True
    queue = deque([v])
    while queue:
        v = queue.popleft()
        for u in G[v]:
            if visited[u]:
                continue
            visited[u] = True
            queue.append(u)


def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    a = [0] * M
    b = [0] * M
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        G[u].append(v)
        G[v].append(u)
        a[i] = u
        b[i] = v

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

        visited = [False] * N
        bfs(G, 0, visited)

        if not all(visited):
            ans += 1

        G[a[i]].append(b[i])
        G[b[i]].append(a[i])

    print(ans)


if __name__ == "__main__":
    main()

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

pa = None

def root(a):
    if pa[a] == a:
        return a
    else:
        pa[a] = root(pa[a])
        return pa[a]
def is_same(a,b):
    return root(a) == root(b)
def unite(a,b):
    aa = root(a)
    bb = root(b)
    if aa == bb:
        return
    pa[aa] = bb

ans = 0
for i in range(m):
    pa = [x for x in range(n)]
    for j,v in enumerate(d):
        
        if i == j:continue
        a,b = v
        unite(a,b)
    a,b = d[i]
    if not is_same(a,b):
        ans +=1
print(ans)

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline


def bfs(G, v, visited):
    visited[v] = True
    queue = deque([v])
    while queue:
        v = queue.popleft()
        for u in G[v]:
            if visited[u]:
                continue
            visited[u] = True
            queue.append(u)


def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    a = [0] * M
    b = [0] * M
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        G[u].append(v)
        G[v].append(u)
        a[i] = u
        b[i] = v

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

        visited = [False] * N
        bfs(G, 0, visited)

        if not all(visited):
            ans += 1

        G[a[i]].append(b[i])
        G[b[i]].append(a[i])

    print(ans)


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 Union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def same(self, x, y):
        if self.find(x) == self.find(y):
            return True
        else:
            return False
n,m = map(int,input().split())
bridge = []
for i in range(m):
    s,t = map(lambda x:int(x) - 1,input().split())
    bridge.append([s,t])
cnt = 0

for i in range(m):
    Uni = UnionFind(n)
    for j,root in enumerate(bridge,start = 0):
        if i == j: 
            continue
        s,t = root
        Uni.Union(s,t)
    
    s,t = bridge[i]
    
    if not Uni.same(s,t):
        cnt += 1
print(cnt)

Solution (Python):
N,M=map(int, input().split())
G=[[] for _ in range(N)]
H=[]
import sys
sys.setrecursionlimit(10**6)
for i in range(M):
    a,b=map(int, input().split())
    G[a-1].append((b-1,i))
    G[b-1].append((a-1,i))
    H.append((i,a-1,b-1))
def dfs(start, goal, banned):
    done[start]=1
    if start==goal:
        ok[0]=True
    for t in G[start]:
        nex, num=t
        if num==banned:
            continue
        elif done[nex]==-1:
            dfs(nex, goal, banned)
    
ans=M
for h in H:
    i,a,b=h
    done=[-1]*N
    ok=[False]
    dfs(a,b,i)
    if ok[0]:
        ans-=1
print(ans)

Solution (Python):
from collections import deque
n,m = map(int,input().split())
edge_ls = [0] * m
for i in range(m):
    a,b = map(int,input().split())
    edge_ls[i] = [a,b]
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        '''
        xとyは-=1して使うのが基本
        '''
        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())
edge_q = deque(edge_ls)
num_bridge = 0
for i in range(m):
    tar = edge_q.popleft()
    uf = UnionFind(n)
    for a,b in edge_q:
        a -= 1
        b -= 1
        uf.union(a,b)
    if not uf.group_count() == 1:
        num_bridge += 1
    edge_q.append(tar)
print(num_bridge)

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


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

def union(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

n,m = LI()
ab = [LI() for _ in range(m)]
ans = 0
for i in range(m):
    par = [i for i in range(n)]
    rank = [0] * n
    for j in range(m):
        if i == j:
            continue
        a, b = ab[j]
        if root(a-1) != root(b-1):
            union(a-1, b-1)
    cnt = len(set([root(i) for i in range(n)]))
    if cnt > 1:
        ans += 1
print(ans)

Solution (Python):


import sys
sys.setrecursionlimit(10**9)
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))


def resolve():
    N,M=pin()
    gragh={(v+1):[] for v in range(N)}
    for i in range(M):
        a,b=pin()
        gragh[a].append(b)
        gragh[b].append(a)
    
    heiro=dict()
    heiro2=set()
    def dfs(v_from,travel,prev=None):
        tra=list(travel)    
        for v_to in gragh[v_from]:
            
            if v_to==prev:
                
                continue
            if v_to in(tra):
                dicset=set()
                f=0
                kyori=0
                for n,t in enumerate(tra):
                    if v_to==t:
                        f=1
                    if f==1:
                        kyori+=1
                        dicset.add(t)
                if len(dicset)>2:
                    dicset=frozenset(dicset)
                    heiro.setdefault(dicset,kyori)
                    
                    break
                continue
            
            prev=v_from
            tra2=tra[:]
            tra2.append(v_to)  
            
            dfs(v_to,tra2,prev)

        return
        
    dfs(1,[1])
    
    for j in (heiro.keys()):
        temp=set(j)
        
        for k in temp:
            heiro2.add(k)
    
    seen=heiro2.copy()
    global ans
    def dfs2(f):
        global ans
        if  f in seen:return
        ans+=1
        seen.add(f)
        for t in gragh[f]:
            dfs2(t)
            
    ans=0        
    for i in range(1,N+1):
        if i in seen:continue
        dfs2(i)
    if len(heiro2)==0:ans-=1
    print(ans)    

resolve()