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.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

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

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

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

def renketu(Town):
    cnt = 0
    for i in range(1,len(Town.par)):
        for j in range(1,i):
            if not Town.same_check(i,j):
                return True
    return False

if __name__ == '__main__':
    N,M = list(map(int,input().split()))
    
    bridge = [list(map(int,input().split())) for i in range(M)]
    cnt = 0
    for kesu in range(M):
        Town = UnionFind(N)
        for i,(x,y) in enumerate(bridge):
            if i != kesu:
                Town.union(x,y)
        if renketu(Town):
            cnt += 1
    print(cnt)

Solution (Python):

def getInt(): return int(input())
def getIntList(): return [int(x) for x in input().split()]
def getIntFromRows(n): return [int(input()) for i in range(n)]
def getIntMat(n):
    mat = []
    for i in range(n): mat.append(getIntList())
    return mat
def zeros(n): return [0 for i in range(n)]
def zeros2(n, m): return [[0 for i in range(m)] for j in range(n)]

debug = True
def db(x): 
    if debug: print(x)

debug = False
n,m = getIntList()
a,b = zeros(m),zeros(m)
org = zeros(m)

for i in range(m):    org[i] = getIntList()

db(('org graph',org))
count = 0

def find(graph, fromNode, toNode, route): 
    db(('f-t',fromNode, toNode))
    if fromNode in route: return -1
    else:
        route = route + [fromNode]
        if fromNode==toNode: return 0
        for edge in graph:
            if edge[0]==fromNode:  
                val = find(graph, edge[1], toNode, route)
                db(('found', route, edge[1], toNode))
                if val==0: return 0
        db(('cannot',fromNode, toNode))
        return -1
    
graph = zeros((m-1)*2)
count = 0
for i in range(m):
    new = org[:i] + org[i+1:]
    db(('cut',org[i]))
    db(('new',new))
    for j in range(m-1):
        graph[j*2] = new[j]
        graph[j*2+1] = [new[j][1], new[j][0]]
    graph.sort()
    db(('new graph',graph))
    route = []
    if find(graph, org[i][0], org[i][1], route)<0: count += 1
print(count)

def connected(graph, node): 
    db(('check node', node))
    for i in range(n):
        if i==node: continue
        found = False
        for e in graph:
            
            if e[0]==node and e[1]==i: 
                found = True
                break
        if not found: return False
    db(('ok node', node))
    return True

Solution (Python):
N, M = map(int,input().split())
Edge = [list(map(int,input().split())) for i in range(M)]


def dfs(i):
    visited.add(i)
    for k in From[i]:
        if k not in visited:
            dfs(k)
    for k in To[i]:
        if k not in visited:
            dfs(k)

def bridge(j):
    for i in Edge:
        if i == j:
            continue
        else:
            From[i[0]-1].append(i[1]-1)
            To[i[1]-1].append(i[0]-1)
    dfs(0)
    return True if visited.__len__() != N else False
ans = 0
for j in Edge:
    From = [[] for i in range(N)]
    To = [[] for i in range(N)]
    visited = set()
    ans += bridge(j)
    
    
    
print(ans)

Solution (Python):
class Graph:
    def __init__(self):
        self.g = {}
        self.node = set()

    def addEdge_single(self, x, y, w):
        self.g[(x, y)] = w
        self.node.add(x)
        self.node.add(y)

    def addEdge(self, x, y, w):
        self.addEdge_single(x, y, w)
        self.addEdge_single(y, x, w)

    def dijkstra(self, start):
        open = {start: 0}
        closed = {}
        prev = {start: -1}
        while len(open) > 0:
            x = Graph.select_min(open)
            m = open[x]
            del open[x]
            closed[x] = m
            for (y, w) in self.edge(x):
                if y in open:
                    if open[y] > m + w:
                        open[y] = m + w
                        prev[y] = x
                elif y not in closed:
                    open[y] = m + w
                    prev[y] = x
            
            
            
            
        return closed, prev

    @staticmethod
    def select_min(S):
        m = -1
        for a in S:
            if m == -1 or m > S[a]:
                x = a
                m = S[a]
        return x

    def edge(self, x):
        G = self.g
        return [(b, G[(a, b)]) for (a, b) in G if a == x]


N, M = [int(x) for x in input().split()]

AB = []
for _ in range(M):
    a, b = [int(x) for x in input().split()]
    AB.append((a, b))

ans = 0
for i in range(M):
    g = Graph()
    for j in range(M):
        if i != j:
            g.addEdge(AB[j][0], AB[j][1], 1)
    w, p = g.dijkstra(1)
    if len(w) != N:
        ans += 1
    

print(ans)

Solution (Python):
import copy
N, M = [int(_) for _ in input().split()]
AB = [[int(_) - 1 for _ in input().split()] for _ in range(M)]

G = [set() for _ in range(N)]
a = set()
for ab in AB:
    G[ab[0]].add(ab[1])


def find(a, x):
    stack = []
    while a[x] != x:
        x = a[x]
        stack += [x]
    while stack:
        a[stack.pop()] = x
    return x


def unite(a, x, y):
    x = find(a, x)
    y = find(a, y)
    a[x] = a[y] = min(x, y)


ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if j in G[i]:
            Gn = copy.deepcopy(G)
            Gn[i].discard(j)
            a = [i for i in range(N)]
            for k in range(N - 1):
                for l in Gn[k]:
                    unite(a, k, l)
            par = set()
            for k in range(N):
                par.add(find(a, k))
            if len(par) > 1:
                ans += 1
print(ans)

Solution (Python):
from collections import deque
from copy import deepcopy

N,M = map(int,input().split())
Matrix = [[False for x in range(N)] for y in range(N)]

Path = []
for i in range(M) :
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    Path.append((a,b))
    Matrix[a][b] = True
    Matrix[b][a] = True

ans = 0
for i in range(M) :
    Matrix_duplicated = deepcopy(Matrix)
    a,b = Path[i]
    Matrix_duplicated[a][b] = False
    Matrix_duplicated[b][a] = False
    Visited = []
    Queue = deque([0])
    while Queue :
        now = Queue.popleft()
        Visited.append(now)
        for i in range(N) :
            if Matrix_duplicated[now][i] :
                Matrix_duplicated[now][i] = False
                Matrix_duplicated[i][now] = False
                Queue.append(i)
    if len(list(set(Visited))) != N :
        ans += 1
print(ans)

Solution (Python):
from collections import deque
from copy import deepcopy

N,M = map(int,input().split())
Matrix = [[False for x in range(N)] for y in range(N)]

Path = []
for i in range(M) :
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    Path.append((a,b))
    Matrix[a][b] = True
    Matrix[b][a] = True

INF = 63
ans = 0
for i in range(M) :
    Matrix_duplicated = deepcopy(Matrix)
    a,b = Path[i]
    Matrix_duplicated[a][b] = False
    Matrix_duplicated[b][a] = False
    Distance = [INF for i in range(N)]
    Distance[0] = 0
    Queue = deque([0])
    while Queue :
        now = Queue.popleft()
        for i in range(N) :
            if Matrix_duplicated[now][i] :
                Matrix_duplicated[now][i] = False
                Matrix_duplicated[i][now] = False
                Distance[i] = min(Distance[now]+1, Distance[i])
                Queue.append(i)
    if INF in Distance :
        ans += 1
print(ans)

Solution (Python):
from collections import deque
from copy import deepcopy

N,M = map(int,input().split())
Matrix = [[False for x in range(N)] for y in range(N)]

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

for i in range(M) :
    a,b = Path[i]
    Matrix[a][b] = True
    Matrix[b][a] = True
    
ans = 0
for i in range(M) :
    a,b = Path[i]
    Matrix_ = deepcopy(Matrix)
    Matrix_[a][b] = False
    Matrix_[b][a] = False
    INF = 63
    Distance = [INF for i in range(N)]
    Distance[0] = 0
    
    QUEUE = deque([0])
    while QUEUE :
        now = QUEUE.popleft()
        
        for i in range(N) :
            if Matrix_[now][i] :
                Matrix_[now][i] = False
                Matrix_[i][now] = False
                Distance[i] = min(Distance[now]+1,Distance[i])
                QUEUE.append(i)
    
    if (INF in Distance) :
        ans += 1
print(ans)

Solution (Python):


import sys
from collections import deque, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n, m = LI()
edge = [LI() for _ in range(m)]


def dfs(s):
    q = deque([s])
    visited = set()

    while q:
        curr = q.pop()
        visited.add(curr)
        for next in G[curr]:
            if next in visited:
                continue
            q.append(next)

    return True if len(visited) == n else False


ans = 0
for i in range(m):
    G = defaultdict(list)
    for j, e in enumerate(edge):
        if i == j:
            continue
        a, b = e
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)

    ans += 0 if dfs(0) else 1

print(ans)

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

def dfs(p):
    visited[p] = True
    for i in range(N):
        if dis[p][i] == 1 and visited[i] is False:
            dfs(i)

def check(start,n):
    global visited
    visited = [False] * N
    a = info[n][0]
    b = info[n][1]
    dis[a][b] = 0
    dis[b][a] = 0
    dfs(start)
    if set(visited) != {True}:
        global ans 
        ans += 1
    dis[a][b] = 1
    dis[b][a] = 1

for i in range(M):
    check(0,i)

print(ans)

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

def dfs(p):
    visited[p] = True
    for d in dis[p]:
        if visited[d] is False:
            dfs(d)

def check(start,n):
    global visited
    visited = [False] * N
    a = info[n][0]
    b = info[n][1]
    dis[a].remove(b)
    dis[b].remove(a)
    dfs(start)
    if set(visited) != {True}:
        global ans 
        ans += 1
    dis[a].append(b)
    dis[b].append(a)

for i in range(M):
    check(0,i)

print(ans)

Solution (Python):
def root(nodes,x):
    if nodes[x] < 0:
        return x
    else:
        nodes[x] = root(nodes,nodes[x])
        return nodes[x]

def unite(nodes,x,y):
    root_x, root_y = root(nodes,x) , root(nodes,y)
    if root_x != root_y:
        nodes[root_x] = root_y

def is_same(nodes,x,y):
    return root(nodes,x) == root(nodes,y)


N,M = list(map(int,input().split()))
data = [[0 for s in range(2)] for k in range(M)]
for i in range(M):
    temp = input().split()
    data[i][0] = int(temp[0])-1
    data[i][1] = int(temp[1])-1
    
sum = 0

for i in range(M):
    nodes = [-1]*(N)
    for j in range(M):
        if j != i:
            unite(nodes,data[j][0],data[j][1])
    for k in range(1,N):
        if is_same(nodes,k-1,k):
            continue
        else:
            sum += 1
            break

print(sum)

Solution (Python):
import queue
N,M=map(int,input().split())
a=[0 for i in range(M)]
b=[0 for i in range(M)]
for i in range(M):
    a[i],b[i]=map(int,input().split())
    a[i]-=1
    b[i]-=1

def isbridge(j):
    G=[set() for i in range(N)]
    for i in range(M):
        if i==j:
            continue
        G[a[i]].add(b[i])
        G[b[i]].add(a[i])
    q=queue.Queue()
    reached=[0 for i in range(N)]
    q.put(0)
    reached[0]=1
    while(not(q.empty())):
        r=q.get()
        reached[r]=1
        for p in G[r]:
            if reached[p]==0:
                q.put(p)
    if sum(reached)==N:
        return False
    else:
        return True

ans=0
for i in range(M):
    if isbridge(i):
        ans+=1
print(ans)

Solution (Python):
import queue
N,M=map(int,input().split())
a=[0 for i in range(M)]
b=[0 for i in range(M)]
for i in range(M):
    a[i],b[i]=map(int,input().split())
    a[i]-=1
    b[i]-=1

def isbridge(j):
    G=[set() for i in range(N)]
    for i in range(M):
        if i==j:
            continue
        G[a[i]].add(b[i])
        G[b[i]].add(a[i])
    q=queue.Queue()
    reached=[0 for i in range(N)]
    q.put(0)
    reached[0]=1
    while(not(q.empty())):
        r=q.get()
        reached[r]=1
        for p in G[r]:
            if reached[p]==0:
                q.put(p)
    if sum(reached)==N:
        return False
    else:
        return True

ans=0
for i in range(M):
    if isbridge(i):
        ans+=1
print(ans)

Solution (Python):
n,m = (int(i) for i in input().split())
a = []
b = []
for i in range(m):
    tmp = list(int(i) for i in input().split())
    a.append(tmp[0])
    b.append(tmp[1])
next = list([] for i in range(n))
for i in range(1,n+1):
    for j in range(m):
        if a[j]==i:
            next[i-1].append(b[j])
        elif b[j]==i:
            next[i-1].append(a[j])
cut = True
while cut:
    cut = False
    for i in range(n):
        if len(next[i])==1:
            if i+1 in next[next[i][0]-1]:
                next[next[i][0]-1].remove(i+1)
                cut = True
count = 0
for i in range(n):
    if len(next[i])==1:
        count += 1
print(count)

Solution (Python):
from collections import deque
n,m = map(int,input().split())
a = [None]*m;b = [None]*m
ans = 0
for i in range(m):
    a[i],b[i] = map(int,input().split())
for i in range(m):
    check = [False]*n
    a_ls = list(a);b_ls = list(b)
    del a_ls[i],b_ls[i]
    deq = deque()
    num = 1
    deq.append(1)
    check[0] = True
    while not not deq:
        num = deq.pop()
        for i in range(m-1):
            if a_ls[i] == num:
                if check[b_ls[i]-1] == False:
                    deq.append(b_ls[i])
                    check[b_ls[i]-1] = True
            if b_ls[i] == num:
                if check[a_ls[i]-1] == False:
                    deq.append(a_ls[i])
                    check[a_ls[i]-1] = True
    if check.count(False) == 0:pass
    else:ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split(' '))
path = [[False for i in range(N+1)] for j in range(N+1)]
connect_list = []
for i in range(M):
    a, b = map(int, input().split(' '))
    path[a][b] = True
    path[b][a] = True
    connect_list.append((a, b))
visit = []


def dfs(x):
    if visit[x]:
        return
    visit[x] = True
    for i in range(1, N+1):
        if path[x][i]:
            dfs(i)


ans = 0
for j in range(M):
    a, b = connect_list[j]
    path[a][b] = False
    path[b][a] = False
    visit = [False for i in range(N+1)]
    connect = True
    dfs(1)
    for i in range(1, N+1):
        if not visit[i]:
            connect = False
    if not connect:
        ans += 1
    path[a][b] = True
    path[b][a] = True
print(ans)

Solution (Python):
class union_find:
    def __init__(self, n):
        self.num_list = [i for i in range(n)]


    def root(self, n):
        if self.num_list[n] == n:
            return n
        else:
            self.num_list[n] = self.root(self.num_list[n])
            return self.num_list[n]

    def merge(self, a, b):
        a_root = self.root(a)
        b_root = self.root(b)
        tmp = min(a_root, b_root)
        self.num_list[a_root] = tmp
        self.num_list[b_root] = tmp
        return


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

ans = 0
U = union_find(n)
for i in range(m):
    U.__init__(n)
    for j in range(m):
        if i == j:
            continue
        U.merge(edge[j][0]-1, edge[j][1]-1)
    setE = set()
    for k in range(n):
        setE.add(U.root(k))
    if len(setE) > 1:
        
        ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().strip().split())
graph = [[False for _ in range(N)] for _ in range(N)]
visited = [False for _ in range(N)]
aa, bb = [], []
ans = 0
for _ in range(M):
  a, b = map(int, input().strip().split())
  aa.append(a)
  bb.append(b)
  graph[a-1][b-1] = graph[b-1][a-1] = True

def dfs(x):
  visited[x] = True
  for i, y in enumerate(graph[x]):
    if y and not visited[i]:
      dfs(i)

for a, b in zip(aa, bb):
  graph[a-1][b-1] = graph[b-1][a-1] = False
  for _v in range(len(visited)):
    visited[_v] = False
  dfs(0)
  if all(v for v in visited):
    ans += 1
  graph[a-1][b-1] = graph[b-1][a-1] = True

print(M - ans)

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

def cal(AB):
    matrix = [[] for i in range(N)]
    for a, b in AB:
        matrix[a].append(b)
        matrix[b].append(a)
    check = [0] * N
    check[0] = 1
    deque = [0]
    while deque:
        now = deque.pop()
        for i in matrix[now]:
            if check[i] == 0:
                deque.append(i)
                check[i] = 1
    if len(set(check)) == 1:
        return 0
    else:
        return 1

for i in range(M):
    AB = ab[:]
    del AB[i]
    ans += cal(AB)

print(ans)

Solution (Python):

def print_arr2(arr):
    for i in range(len(arr)):
        for j in range(len(arr[i])):
            print(arr[i][j],end="")
        print()
    print()

import copy

def dfs(node,edge):
    ok = True
    narr = [0 for _ in range(node)]
    M = len(edge)
    stack = []
    stack.append([0,-1])
    narr[0] = 1
    while(stack != []):
        start = stack.pop(-1)
        for i in range(M):
            if edge[start[0]][i] == 1 and narr[i] != 1:
                narr[i] = 1
                stack.append([i,start[0]])
    for i in range(node):
        if narr[i] != 1:
            ok = False
    return ok
        
N,M = map(int,input().split())
edge = [[0]*N for _ in range(N)]
tedge = [[0]*N for _ in range(N)]
count = 0
for i in range(M):
    go, to = map(int,input().split())
    edge[go-1][to-1] = 1
    edge[to-1][go-1] = 1

for go in range(N):
    for to in range(go,N):
        if edge[go][to] == 1:
            tedge = copy.deepcopy(edge)
            tedge[go][to] = 0
            tedge[to][go] = 0
            if dfs(N,tedge) == False:
                count += 1

print(count)

Solution (Python):
n, m = map(int, input().split())
a_list = []
b_list = []

for i in range(m):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)

import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        route_count = [0 for _ in range(num_of_city)]
        route_count[self.start_point] = 1
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
                if dist[dest] == dist[src] + cost:
                    route_count[dest] += route_count[src]

        if self.goal_point is not None:
            return self._get_path(self.goal_point, prev)
        else:
            return dist, route_count

    def _get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))


count = 0
for j in range(m):
    items = [dict() for _ in range(n)]
    for i in range(m):
        a, b = a_list[i] - 1, b_list[i] - 1
        if i == j:
            continue
        items[a][b] = 1
        items[b][a] = 1
    di = Dijkstra(items, a_list[0] - 1).execute()
    if len([True for d in di[0] if d == float("inf")]) >= 1:
        count += 1
print(count)

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

graph=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    
def dfs(s,a,b):
    flag[s]=1
    for v in graph[s]:
        if s==a and v==b or s==b and v==a:
            continue
        if flag[v]==1:
            continue
        dfs(v,a,b)

ans=0
for i in range(n):
    for v in graph[i]:
        flag=[0 for i in range(n)]
        dfs(0,i,v)
        num=0
        for j in flag:
            if j==0:
                num=1
        if num==1:
            ans+=1
print(ans//2)

Solution (Python):
def is_tree(g, n):
    visiteds = [False] * n
    q = [0]
    while q:
        i = q.pop()
        if visiteds[i]:
            continue
        visiteds[i] = True
        for to in g[i]:
            if not visiteds[to]:
                q.append(to)
    return all(visiteds)


def main():
    global n
    n, m = map(int, input().split())
    g = [set() for _ in range(n)]
    es = []
    for _ in range(m):
        a, b = map(lambda s: int(s) - 1, input().split())
        g[a].add(b)
        g[b].add(a)
        es.append((a, b))

    res = 0
    for a, b in es:
        g[a].remove(b)
        g[b].remove(a)
        if not is_tree(g, n):
            res += 1
        g[a].add(b)
        g[b].add(a)

    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind(object):
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self._size = 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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self._size -= 1
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

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

    def size(self):
        return self._size

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

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

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

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

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

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


N, M = map(int, input().split())
a, b = [0] * M, [0] * M

for i in range(M):
    a[i], b[i] = map(int, input().split())
    a[i] -= 1; b[i] -= 1
ans = 0
for i in range(M):
    uf = uf_tree(N+1)
    for j in range(M):
        if i == j:
            continue
        uf.unite(a[j], b[j])

    bridge = False
    for i in range(N):
        if not uf.same(0, i):
            bridge = True
    if bridge:
        ans += 1

print(ans)

Solution (Python):
import heapq
from collections import defaultdict

ans = 0
N, M = list(map(int, input().split()))
mlist = []
for i in range(M):
	mlist.append(list(map(int, input().split())))

for i in range(M):
	graph = defaultdict(list)
	for j in range(M):
		if j != i:
			a = mlist[j][0]
			b = mlist[j][1]
			graph[a - 1].append([b - 1, 1])
			graph[b - 1].append([a - 1, 1])
		dist_node = [float("inf") for i in range(N)]
		s = 0
		dist_node[s] = 0

		Q = []
		heapq.heappush(Q, (dist_node[s], s)) 

		while Q: 
			dis, v = heapq.heappop(Q)
			if dist_node[v] < dis:
				continue
			for u, w in graph[v]:
				alt = dis + w
				if dist_node[u] > alt:
					dist_node[u] = alt
					heapq.heappush(Q, (alt, u))
	if dist_node.count(float("inf")) != 0:
		ans += 1

print(ans)

Solution (Python):
from queue import Queue
N, M = map(int, input().split())
a, b = [0] * M, [0] * M
g = [[False] * N for _ in range(N)]
for i in range(M):
    a[i], b[i] = map(int, input().split())
    g[a[i]-1][b[i]-1] = True
    g[b[i]-1][a[i]-1] = True

ans = 0
for _a, _b in zip(a, b):
    g[_a-1][_b-1] = False
    g[_b-1][_a-1] = False
    visit = [False] * N
    q = Queue()
    q.put(0)
    while not q.empty():
        v = q.get()
        visit[v] = True
        for adj_v, adj in enumerate(g[v]):
            if not adj or visit[adj_v]:
                continue
            q.put(adj_v)
    if not all(visit):
        ans += 1
    g[_a-1][_b-1] = True
    g[_b-1][_a-1] = True
print(ans)

Solution (Python):
def dfs(v):
    visit[v] = True
    for adj_v in [v for v, adj in enumerate(g[v]) if adj and not visit[v]]:
        dfs(adj_v)

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

g = [[False] * N for _ in range(N)]
for _a, _b in zip(a, b):
    g[_a-1][_b-1] = True
    g[_b-1][_a-1] = True

ans = 0
for _a, _b in zip(a, b):
    g[_a-1][_b-1] = False
    g[_b-1][_a-1] = False
    visit = [False] * N
    dfs(0)
    if not all(visit):
        ans += 1
    g[_a-1][_b-1] = True
    g[_b-1][_a-1] = True
print(ans)

Solution (Python):
from math import isinf

V,E = map(int, input().split())
a,b = [0]*E, [0]*E
for i in range(E):
    ai,bi = map(int, input().split())
    a[i],b[i] = ai-1, bi-1
    
ans = 0
for l in range(E):
    d = [[float('inf')]*V for _ in range(V)] 
    for i in range(V):
        d[i][i] = 0
    for i in range(E):
        if i==l: continue 
        d[a[i]][b[i]] = 1
        d[b[i]][a[i]] = 1
        
    
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if d[i][j] > d[i][k]+d[k][j]:
                    d[i][j] = d[i][k]+d[k][j]
    bridge = False
    
    for dd in d[0]:
        if isinf(dd): bridge=True
    if bridge:
        ans += 1
        
print(ans)

Solution (Python):
class UnionFind:
    
    def __init__(self, size:int):
        self.par = [-1]*size
        self.rank = [0]*size
        for i in range(size):
            self.par[i] = i
    
    def root(self, x:int)->int:
        """根を求める"""
        if self.par[x] == x: 
            return x
        else:
            self.par[x] = self.root(self.par[x]) 
            return self.par[x]
        
    def isSame(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)
    
    def unite(self, x:int, y:int):
        """x と y の属する集合を併合"""
        root_x = self.root(x)
        root_y = self.root(y)
        if root_x == root_y: return
        
        
        if self.rank[root_x] < self.rank[root_y]:
            self.par[root_x] = root_y
        else:
            self.par[root_y] = root_x
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_x] += 1
                


N,M = map(int, input().split())
a,b = [0]*M, [0]*M
for i in range(M):
    ai,bi = map(int, input().split())
    a[i],b[i] = ai-1, bi-1
    
ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if i==j: continue 
        uf.unite(a[j], b[j])
    bridge = False
    for i in range(N):
        if not uf.isSame(0,i):
            bridge = True
    if bridge:
        ans += 1
print(ans)

Solution (Python):
class UnionFind:
    """
    - sizeを指定
    - 要素をグループにまとめる(unite) 
    - 要素同士が同じグループか判定する(isSame)
    - 分離はできない
    - par: 親の番号(はじめ par[i]==i つまりすべての頂点が根)
     - 始め各要素は別々のグループ"""
    def __init__(self, size: int):
        self.par = [-1]*size
        for i in range(size):
            self.par[i] = i 
    
    def root(self, x: int) -> int:
        """根を求める"""
        if self.par[x] == x: 
            return x
        else:
            self.par[x] = self.root(self.par[x]) 
            return self.par[x]
    
    def isSame(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)
    
    def unite(self, x:int, y:int):
        """x と y の属する集合を併合"""
        x = self.root(x)
        y = self.root(y)
        if x == y: return
        self.par[x] = y

        
        

N,M = map(int, input().split())
a,b = [0]*M, [0]*M
for i in range(M):
    ai,bi = map(int, input().split())
    a[i],b[i] = ai-1, bi-1
    
ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if i==j: continue 
        uf.unite(a[j], b[j])
    bridge = False
    for i in range(N):
        if not uf.isSame(0,i):
            bridge = True
    if bridge:
        ans += 1
print(ans)

Solution (Python):

N,M = map(int, input().split())
graph = [[False]*N for _ in range(N)]
visited = [False]*N

def dfs(cur):
    global visited
    visited[cur] = True
    for nxt in range(N):
        if graph[cur][nxt]==False: continue
        if visited[nxt]==True: continue
        dfs(nxt)


a = [-1]*M
b = [-1]*M
for i in range(M):
    ai,bi = map(int, input().split())
    a[i],b[i] = ai-1, bi-1
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True

ans = 0
for i in range(M):
    graph[a[i]][b[i]] = False 
    graph[b[i]][a[i]] = False
    
    visited = [False]*N
    dfs(0)
    if not all(visited):
        ans += 1
    graph[a[i]][b[i]] = True 
    graph[b[i]][a[i]] = True
    
print(ans)