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):
def main():
    from collections import deque

    def traversal(ignore_idx):
        s = 0
        visited = [-1] * N
        visited[s] = 0

        dq = deque([s])
        while dq:
            v = dq.popleft()
            for u, edge_idx in g[v]:
                if ~visited[u] or edge_idx == ignore_idx:
                    continue
                dq.append(u)
                visited[u] = 0
        return all(~flg for flg in visited)  

    N, M = map(int, input().split())
    g = tuple(set() for _ in range(N))
    for edge_idx in range(M):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add((b, edge_idx))
        g[b].add((a, edge_idx))

    ret = 0
    for ignore_idx in range(M):
        res = traversal(ignore_idx)
        if not res:
            ret += 1
    print(ret)


if __name__ == '__main__':
    main()

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.d = [-1] * n

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

        if x == y:
            return False
        else:
            if self.d[x] > self.d[y]:
                x, y = y, x
            self.d[x] += self.d[y]
            self.d[y] = x
            return True

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


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

n, m = map(int, input().split())
a = [0] * m
b = [0] * m
for i in range(m):
    val1, val2 = map(int, input().split())
    val1 -= 1
    val2 -= 1
    a[i], b[i] = val1, val2
ans = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if j == i:
            continue
        else:
            uf.unite(a[j], b[j])
    cnt = uf.find(0)
    
    for j in range(n):
        if uf.find(j) != cnt:
            ans += 1
            break

print(ans)

Solution (Python):



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

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

def dfs(graph, n):
    visited = [False] * (n + 1)
    visited[0] = True 
    stack = [1]
    num = 0
    while stack:
        t = stack.pop()
        for node in graph[t]:
            if visited[node]:
                continue
            visited[node] = True
            stack.append(node)
            num += 1
    if num == n:
        return True
    return False

ans = 0
for i in range(m):
    graph = [[] for _ in range(n + 1)]
    for j in range(m):
        if i == j:
            continue
        a, b = queries[j]
        graph[a].append(b)
        graph[b].append(a)
    if not dfs(graph, n):
        ans += 1
print(ans)

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

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


class Union:
    def __init__(self, val):
        self.val = val
        self.parent = self
        self.rank = 0

    def get_root(self):
        n = self
        while n.parent != n:
            n = n.parent
        return n

    def find_set(self):
        return self.get_root().val

ans = 0
for i in range(m):
    unions = []
    for val in range(n):
        unions.append(Union(val))
    for index, (a, b) in enumerate(brides):
        if i == index:
            continue
        x, y = unions[a - 1], unions[b - 1]
        x_root = x.get_root()
        y_root = y.get_root()
        if x_root.rank == y_root.rank:
            x_root.rank += 1
            y_root.parent = x_root
        elif x_root.rank > y_root.rank:
            y_root.parent = x_root
        else:
            x_root.parent = y_root

    groups = [None] * n
    for j, u in enumerate(unions):
        root = u.find_set()
        groups[j] = root
    for g in range(1, n):
        if groups[g - 1] != groups[g]:
            ans += 1
            break
print(ans)

Solution (Python):
import copy
N,M=[int(s) for s in input().split()]
TO=[set() for _ in range(N)]
Edges=[[int(s) for s in input().split()] for _ in range(M)]
for [a,b] in Edges:
  TO[a-1].add(b-1)
  TO[b-1].add(a-1)
ans=0
for [a,b] in Edges:
  to=copy.deepcopy(TO)
  to[a-1].remove(b-1)
  reach={a-1}
  while(reach):
    k=reach.pop()
    if k==b-1:
      break
    while(to[k]):
      m=to[k].pop()
      reach.add(m)
  else:
    ans+=1
print(ans)

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)

N, M = map(int,input().split())
uf = UnionFind(N)
l = []
count=0
for i in range(M):
    a, b = map(int,input().split())
    l.append([a, b])
    
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if i != j:
            uf.union(l[j][0], l[j][1])
    if not uf.same_check(l[i][0],l[i][1]):
        count+=1
print(count)

Solution (Python):


class UnionFind():
    def __init__(self, N):
        self._root = [-1 for _ in range(N)]

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

    def unite(self, x, y):
        gx = self.find(x)
        gy = self.find(y)
        if gx == gy: return False
        if self._root[gx] > self._root[gy]:
            gx, gy = gy, gx
        self._root[gx] += self._root[gy]
        self._root[gy] = gx
        return True

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

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

    def roots(self):
        return [i for i in self._root if i < 0]

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

cnt = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i != j:
            uf.unite(nodes[j][0]-1, nodes[j][1]-1)
    cnt += (len(uf.roots()) != 1)
print(cnt)

Solution (Python):

class UnionFind():
    def __init__(self, N):
        self._root = [-1 for _ in range(N)]

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

    def unite(self, x, y):
        gx = self.find(x)
        gy = self.find(y)
        if gx == gy: return False
        if self._root[gx] > self._root[gy]:
            gx, gy = gy, gx
        self._root[gx] += self._root[gy]
        self._root[gy] = gx
        return True

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

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

    def roots(self):
        return [i for i in self._root if i < 0]


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

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

cnt = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i != j:
          uf.unite(nodes[j][0]-1, nodes[j][1]-1)
    cnt += (len(uf.roots()) != 1)
print(cnt)

Solution (Python):
import sys

readline = sys.stdin.buffer.readline

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

es = []
for _ in range(m):
    a, b = map(int, readline().split())
    es.append((a, b))


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


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


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y


ans = 0
for i in range(m):
    par = [_ for _ in range(n + 1)]
    for j, k in enumerate(es):
        if i == j:
            continue
        a, b = k
        unite(a, b)
    a, b = es[i]
    if not same(a, b):
        ans += 1
print(ans)

Solution (Python):
'''
https://atcoder.jp/contests/abc075/tasks/abc075_c?lang=ja
深さ優先探索でも解ける
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    

    

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

if __name__ == '__main__':
    main()

Solution (Python):
'''
https://atcoder.jp/contests/abc075/tasks/abc075_c?lang=ja
深さ優先探索でも解ける
'''
def main():
    import sys
    
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    

    

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

if __name__ == '__main__':
    main()

Solution (Python):
import copy
n,m=map(int,input().split())
node=[[0 for _ in range(n)] for _ in range(n)]
aL=[0 for _ in range(m)]
bL=[0 for _ in range(m)]
for i in range(m):
    a,b=map(int,input().split())
    node[a-1][b-1]=1
    node[b-1][a-1]=1
    aL[i]=a
    bL[i]=b
    
tmp1=copy.deepcopy(node)
chk=[0 for _ in range(n)]
def DFS(x):
    chk[x]=1
    for i in range(n):
        if chk[i]!=1 and tmp1[x][i]==1:
            tmp1[x][i]=0
            tmp1[i][x]=0
            chk[i]=1
            DFS(i)
    return chk

cnt=0
for j in range(m):
    tmp1[aL[j]-1][bL[j]-1]=0
    tmp1[bL[j]-1][aL[j]-1]=0
    if sum(DFS(0))!=n:
        cnt+=1
    tmp1=copy.deepcopy(node)
    chk=[0 for _ in range(n)]
print(cnt)

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

s = 0

for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if j != i:
            uf.union(ab[j][0] - 1, ab[j][1] - 1)
    s += (len(uf.roots()) != 1)

print(s)

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

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 int_(num_str):
    return int(num_str) - 1

N, M = map(int, input().split())
ablist = [tuple(map(int_, input().split())) for _ in range(M)]
ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j, ab in enumerate(ablist):
        if i == j:
            continue
        uf.union(*ab)
    if uf.group_count() > 1:
        ans += 1
print(ans)

Solution (Python):

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


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

def same(a, b, par):
    return root(a, par) == root(b, par)

def union(a, b, par):
    if not same(a, b, par):
        ra = root(a, par)
        rb = root(b, par)
        
        par[rb] = a

edges = []
for _ in range(m):
    edges.append(tuple(map(lambda x : int(x)-1, input().split())))

ans = 0
for i in range(m):
    par = [k for k in range(n)]
    for j in range(m):
        if i == j:
            continue
        a, b = edges[j]
        if same(a, b, par):
            continue
        union(a, b, par)
    
    a, b = edges[i]
    if not same(a, b, par):
        ans += 1
print(ans)

Solution (Python):
from copy import deepcopy
from scipy.sparse.csgraph import floyd_warshall

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

cnt=0
for i in range(m):
  ll=deepcopy(l)
  del ll[i]

  d=[[float('inf')]*n for i in range(n)]
  for i in range(n):
    d[i][i]=0

  for a,b in ll:
    a-=1
    b-=1
    d[a][b]=1
    d[b][a]=1

  s=floyd_warshall(d)
  for i in s:
    if float('inf') in i:
      cnt+=1
      break

print(cnt)

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

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

cnt=0
for i in range(m):
  ll=deepcopy(l)
  del ll[i]

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

    dist=[-1 for i in range(n)]

    s=ll[0][0]-1
    dist[s]=0
    dq=deque()
    dq.append(s)

    while dq:
      x=dq.popleft()
      for i in tree[x]:
        if dist[i]==-1:
          dq.append(i)
          dist[i]=dist[x]+1

  if -1 in dist:
    cnt+=1
print(cnt)

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 roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

from copy import deepcopy

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

cnt=0
for i in range(m):
  uf=UnionFind(n)
  ll=deepcopy(l)
  del ll[i]
  for a,b in ll:
    a-=1
    b-=1
    uf.union(a,b)
  if uf.group_count()>=2:
    cnt+=1
print(cnt)

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

N, M = map(int, input().split())
ablist = [tuple(map(int, input().split())) for _ in range(M)]
ans = 0
for i in range(M):
    uf = UnionFind(N)
    for index, ab in enumerate(ablist):
        a, b = ab
        if index != i:
            uf.union(a-1, b-1)
    if uf.group_count() >= 2:
        ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
GRAPH = [[0]*n for _ in range(n)]
EDGES = []

for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    GRAPH[a][b] = GRAPH[b][a] = 1
    EDGES.append((a, b))


def make_dfs():
    visited = [0]*n

    def inner(v):
        visited[v] = 1
        for v2 in range(n):
            if not GRAPH[v][v2]:
                continue
            if visited[v2]:
                continue
            inner(v2)
        return visited
    return inner


ans = 0
for a, b in EDGES:
    GRAPH[a][b] = GRAPH[b][a] = 0
    dfs = make_dfs()
    if sum(dfs(0)) != n:
        ans += 1
    GRAPH[a][b] = GRAPH[b][a] = 1

print(ans)

Solution (Python):
def find_root(x):
    if parent[x] == x:
        return x
    else:
        return find_root(parent[x])


def unite(x, y):
    x = find_root(x)
    y = find_root(y)

    if x != y:
        if rank[x] < rank[y]:
            parent[x] = y
            size[y] += size[x]
        else:
            parent[y] = x
            size[x] += size[y]
            if rank[x] == rank[y]:
                rank[x] += 1


def roots():
    roots = []
    for i in range(N):
        roots.append(find_root(i))
    return roots


def group_count():
    return len(set(roots()))


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

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

edge = [[ab[M - 1 - i][0] - 1, ab[M - 1 - i][1] - 1] for i in range(M)]

for i in range(M):
    unite(edge[i][0], edge[i][1])
count = group_count()

ans = 0
for j in range(M):
    
    parent = [i for i in range(N)]
    rank = [1] * N
    size = [1] * N
    for i in range(M):
        if j == i:
            continue
        unite(edge[i][0], edge[i][1])
    if group_count() > count:
        ans += 1
print(ans)

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


class UnionFind:
  N=0
  parent=None
  size=None
  def __init__(self,N):
    self.N=N
    self.parent=[i for i in range(self.N)]
    self.size=[1]*self.N
    
  def root(self,x):
    while x!=self.parent[x]:
      self.parent[x]=self.parent[self.parent[x]]
      x=self.parent[x]
    return x
  
  def same(self,x,y):
    return self.root(x)==self.root(y)
  
  def unite(self,x,y):
    x=self.root(x)
    y=self.root(y)
    if x==y:
      return
    if self.size[x]>self.size[y]:
      
      self.parent[y]=x
      self.size[x]+=self.size[y]
    else:
      self.parent[x]=y
      self.size[y]+=self.size[x]
      
  def get_group_size(self,x):
    return self.size[self.root(x)]
  
  def get_roots(self):
    r=set()
    for i in range(self.N):
      r.add(root(i))
    return r
  
  def show_parent(self):
    print(self.parent)
    
  def show_size(self):
    print(self.size)
    
N,M=map(int,readline().split())
edges=[None]*M
for i in range(M):
  a,b=map(int,readline().split())
  edges[i]=[a-1,b-1]

ans=0

for i in range(M):
  
  UF=UnionFind(N)
  for m in range(M):
    if m==i:
      continue
    UF.unite(edges[m][0],edges[m][1])
  
  if UF.get_group_size(0)!=N:
    ans+=1
    
print(ans)

Solution (Python):

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

edges=[]
graph=[[False for _ in range(n)] for _ in range(n)]

for _ in range(m):
    a,b=map(int,input().split())
    edges.append((a-1,b-1))
    graph[a-1][b-1]=True
    graph[b-1][a-1]=True

def dfs(v):
    visit[v]=True
    for v2 in range(n):
        if visit[v2]==True: continue
        if graph[v][v2]==False: continue
        dfs(v2)

for x in edges:
    a,b=x
    graph[a][b]=False
    graph[b][a]=False
    visit=[False for _ in range(n)]
    
    dfs(0)
    ans+=any([visit[i]==False for i in range(n)])
    
    graph[a][b]=True
    graph[b][a]=True
    
print(ans)

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

E = [[] for i in range(N)]

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

visited = []


def search(pos):
    for n_pos in E[pos]:
        if n_pos not in visited:
            visited.append(n_pos)
            search(n_pos)

count = 0
for i in range(M):
    visited = []
    E = [[] for i in range(N)]
    for j in range(M):
        if j == i:
            continue
        E[ab[j][0]].append(ab[j][1])
        E[ab[j][1]].append(ab[j][0])
    search(0)
    if len(visited) < N:
        count += 1

print(count)

Solution (Python):
N,M=map(int,input().split())
def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]

def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
            siz[a]+=siz[b]
        else:
            par[a]=b
            siz[b]+=siz[a]
            if rank[a]==rank[b]:
                rank[b]+=1
            

def size(a):
    return siz[find(a)]

def same(a,b):
    return find(a)==find(b)

ab=[]
for i in range(M):
    A,B=map(int,input().split())
    A,B=A-1,B-1
    ab.append([A,B])
res=0

for i in range(M):
    par=[j for j in range(N)]
    siz=[1 for _ in range(N)]
    rank=[0 for _ in range(N)]
    for j in range(M):
        if(i==j):
            continue
        union(ab[j][0],ab[j][1])
    for i in range(1,N):
        if(not same(0,i)):
            res+=1
            break
print(res)

Solution (Python):
def dfs(v, matrix, visited):
    visited[v] = True
    for i in range(n):
        if visited[i]:
            continue
        if not matrix[v][i]:
            continue
        dfs(i, matrix, visited)


n, m = map(int, input().split())
ab = [tuple(map(lambda x: (int(x) - 1), input().split())) for _ in range(m)]
matrix = [[False] * n for _ in range(n)]
for a, b in ab:
    matrix[a][b] = True
    matrix[b][a] = True
visited = [False] * n
ans = 0

for a, b in ab:
    matrix[a][b] = False
    matrix[b][a] = False
    for i in range(n):
        visited[i] = False
    dfs(0, matrix, visited)
    if not all(visited):
        ans += 1
    matrix[a][b] = True
    matrix[b][a] = True
print(ans)

Solution (Python):
class UnionFind:
    
    
    def __init__(self, n):
        
        
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    
    """ノードxのrootノードを見つける"""
    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 Union(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        
        if (x==y):
            return 
        
        
        elif (self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            
            if self.rnk[x]==self.rnk[y]:
                self.rnk[y] += 1
    
    """xとyが同じグループに所属するか"""
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    
    """ノードxが属する木のサイズ"""
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


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

res = 0
for i in range(m):
    tmp_edge = edge[:i] + edge[i+1:]
    uf = UnionFind(n)
    for j in range(len(tmp_edge)):
        uf.Union(tmp_edge[j][0], tmp_edge[j][1])
    if not uf.isSameGroup(edge[i][0], edge[i][1]):
        res += 1
print(res)

Solution (Python):
class UnionFind:
    def __init__(self,N):
        self.par =[-1 for i in range(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 unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.par[x] > self.par[y]:
            x,y = y,x
        self.par[x] +=self.par[y]
        self.par[y] = x

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

N,M=map(int,input().split(' '))
q = [list(map(int,input().split(' '))) for i in range(M)]
ans = 0
for i in range(M):
    tmp = q[:i]+q[i+1:]
    uf = UnionFind(N)
    for j,k in tmp:
        uf.unite(j-1,k-1)
    for l in range(N):
        if uf.size(l) != N:
            ans += 1
            break
print(ans)

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


def dfs(u):
    if is_visited[u]:
        return
    is_visited[u] = 1
    for i in range(N):
        if G[u][i]:
            dfs(i)


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

ans = 0



for i in range(M):
    is_visited = [0] * N
    a, b = A[i], B[i]
    G[a][b] = 0
    G[b][a] = 0
    dfs(0)
    
    if is_visited.count(1) != N:
        ans += 1
    G[a][b] = 1
    G[b][a] = 1

print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n: int):
        self.__n = n
        self.__par = list(range(self.__n))
        self.__size = [1 for _ in range(self.__n)]

    def root(self, x: int) -> int:
        if self.__par[x] == x:
            return x
        self.__par[x] = self.root(self.__par[x])
        return self.__par[x]

    def merge(self, x: int, y: int) -> bool:
        rx, ry = self.root(x), self.root(y)
        if rx == ry: return False

        if self.__size[rx] < self.__size[ry]:
            rx, ry = ry, rx

        self.__size[rx] += self.__size[ry]
        self.__par[ry] = rx
        return True

    def check(self, x: int, y: int) -> bool:
        return self.root(x) == self.root(y)

    def size(self, x: int) -> int:
        return self.__size[self.root(x)]


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

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

    if uf.size(1) != N:
        ans += 1

print(ans)