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
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    def __init__(self, size):
        """
        size:頂点の数
        """
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]

    def find(self, x):
        """
        xのrootを返す
        """
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def union(self, x, y):
        """
        x,yを同じグループとしてまとめる
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        """
        xとyが同じグループならTrue
        """
        return self.find(x) == self.find(y)

    def component(self):
        """
        各連結成分のrootの集合を返す
        len()をとれば連結成分の数が求められる
        return-> set()
        """
        comp = set()
        for i in self.parent:
            p = self.find(i)
            comp.add(p)
        return comp

    def __str__(self):
        """
        for debug
        クラスのlistの情報を出力
        """
        ret = "parents\n"
        ret += " ".join(map(str, self.parent))
        ret += '\n'
        ret += " ".join(map(str, self.rank))
        return ret


N, M = map(int, input().split())
edges = []

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

ans = 0
for e in edges:
    Un = UnionFind(N)
    for g in edges:
        if e == g:
            continue
        else:
            Un.union(g[0], g[1])
    if not Un.same(e[0], e[1]):
        ans += 1
print(ans)

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

def bfs(i, edges, r):
    if all(r):
        return True
    if r[i]:
        return False
    r[i] = True
    if any([bfs(e, edges, r) for e in edges[i]]):
        return True
    return False

ans = 0
for i in range(m):
    edges = [[] for _ in range(n)]
    for j in range(m):
        if i != j:
            edges[ab[j][0]-1].append(ab[j][1]-1)
            edges[ab[j][1]-1].append(ab[j][0]-1)
    reached = [False for _ in range(n)]
    if not bfs(0, edges, reached):
        ans += 1
print(ans)

Solution (Python):

def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

class UnionFind(object):
 
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
 
    def find(self, x):
  
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
  
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            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 same(self, x, y):
        return self.find(x) == self.find(y)
n,m=IL()
nl=[]
for i in range(m):
    f,t=IL()
    nl.append([f-1,t-1])
ans=0
for i in range(m):
    uf=UnionFind(n)
    flag=False
    for j in range(m):
        if i==j:
            continue
        uf.union(nl[j][0],nl[j][1])
    nl.append(t)
    for j in range(n):
        for k in range(n):
            if not uf.same(j,k):
                flag=True
    if flag:
        ans+=1
print(ans)

Solution (Python):
from collections import defaultdict

def dfs(graph, node_start, visited):
    if node_start in visited:
        return visited
    visited.append(node_start)
    for node_end in graph[node_start]:
        dfs(graph, node_end, visited)
    return visited

def main():
    N, M = map(int, input().split())

    graph = defaultdict(list)
    edges = []

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

    answer = 0
    for a, b in edges:
        
        graph[a].remove(b)
        graph[b].remove(a)

        visited = dfs(graph, 1, [])
        if len(visited)!= N:
            answer += 1

        
        graph[a].append(b)
        graph[b].append(a)

    print(answer)

if __name__ == '__main__':
    main()

Solution (Python):
def rootT(x, cnt):
  cnt += 1
  if x == T[x]:
    return x, cnt
  x = T[x]
  return rootT(x, cnt)

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

Ans = 0

for i in range(M):
  L = ab[:i] + ab[i + 1:]
  
  
  T = [i for i in range(N + 1)]
  for j in L:
    
    a = rootT(j[0], 0)
    b = rootT(j[1], 0)
    
    if a[0] != b[0]:
      
      if a[1] > b[1]:
        T[b[0]] = a[0]
      else:
        T[a[0]] = b[0]

  flag = False
  t = rootT(T[1], 0)[0]
  for j in range(2, N + 1):
    if rootT(T[j], 0)[0] != t:
      flag = True
      break
  if flag:
    Ans += 1

print(Ans)

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

ab = []
for i in range(m):
    a,b = map(int, input().split())
    ab.append((a,b))
    
def dfs(x):
    global flag
    flag[x] = True
    for k in range(n):
        if bridge[x][k] == True:
            bridge[x][k] = False
            dfs(k)
            
           
ans = 0
for i in range(m):
    bridge = [[False for i in range(n)] for i in range(n)]
    for j in ab[0:i] + ab[i+1:m]:
        bridge[j[0] - 1][j[1] - 1] = True
        bridge[j[1] - 1][j[0] - 1] = True   
    flag = [False for j in range(n)]
    dfs(0)
    if flag.count(False) > 0:
        ans += 1
        
print(ans)

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

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

def dfs(v, e):
  for num in v:
    if(len(e[num]) == 1):
      tmp_num = e[num][0]
      v.remove(num)
      e[num] = []
      e[tmp_num].remove(num)
      
      return dfs(v, e)+1
  return 0
print(dfs(v, e))

Solution (Python):

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


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


def same(x,y,par):
    return find(x,par) == find(y,par)
    
n, m = map(int, input().split())
a, b = [], []
ans = 0
for i in range(m):
    ta, tb = map(int,input().split())
    a.append(ta-1)
    b.append(tb-1)
    
for i in range(m):
    par = []
    rank = []
    diff = set()
    for j in range(n): 
        par.append(j)
        rank.append(0)
    for j in range(m):
        if j == i:
            continue
        else:
            unite(a[j],b[j],par,rank)
    for j in range(n):
        diff.add(find(j,par))
    if len(diff) == 1:
        continue
    else:
        ans += 1
print(ans)

Solution (Python):
import copy

n, m = map(int, input().split())
array = [[int(x) for x in input().split()] for y in range(m)]
t = copy.copy(array)


def solver(start, array, visited, cnt):
    if visited[start]:
        return cnt
    else:
        visited[start] = True

    for i in array[start]:
        if len(set(visited)) == 1:
            return 1
        else:
            cnt = solver(i, array, visited, cnt)

    return cnt


res2 = 0
for i in range(m):
    tmp = array[:i] + array[i + 1:]
    modify = [[] for x in range(n + 1)]
    for value1, value2 in tmp:
        modify[value1].append(value2)
        modify[value2].append(value1)

    visited = [False if x != 0 and x != 1 else True for x in range(n + 1)]
    if not modify[1]:
        continue

    res = 0
    for i in modify[1]:
        res += solver(i, modify, visited, 0)
    else:
        res2 += 1 if res > 0 else 0

print(m - res2)

Solution (Python):
n, m = map(int, input().split())
edge = [list(map(int, input().split())) for i in range(m)]
ans = 0
for i in edge:
    l = list(range(n))
    for j in edge:
        if j != i:
            l = [l[j[0] - 1] if l[k] == l[j[1] - 1] else l[k] for k in range(n)]
    if len(set(l)) != 1:
        ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
d = [[float("inf")] * n for i in range(n)]
edge = []
for i in range(m):
    a, b = map(int, input().split())
    edge.append((a, b))
    d[a - 1][b - 1] = 1
    d[b - 1][a - 1] = 1
ans = 0
for a in range(m):
    d_s = [x[:] for x in d]
    x, y = edge[a]
    d_s[x - 1][y - 1] = float("inf")
    d_s[y - 1][x - 1] = float("inf")
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d_s[i][j] = min(d_s[i][j], d_s[i][k] + d_s[k][j])
    flag = 0
    for i in range(n):
        if flag:
            break
        for j in range(n):
            if flag:
                break
            if d_s[i][j] == float("inf"):
                ans += 1
                flag = 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
graph = [[False for i in range(n)] for j in range(n)]
AB = []
for i in range(m):
    a,b = map(int, input().split())
    AB.append((a,b))
    graph[a-1][b-1] = True
    graph[b-1][a-1] = True
    
def dfs(x):
    if visited[x]:
        return
    visited[x] = True
    for i in range(n):
        if graph[x][i]:
            dfs(i)
            
ans = 0
for i in AB:
    graph[i[0]-1][i[1]-1] = graph[i[1]-1][i[0]-1] = False
    visited = [False for i in range(n)]
    dfs(0)
    check = True
    for j in range(n):
        if not visited[j]:
            check = False
    if not check:
        ans += 1
    graph[i[0]-1][i[1]-1] = graph[i[1]-1][i[0]-1] = True
print(ans)

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

cnt=0
def dfs(u):
  global cnt
  global visited
  visited[u]=True
  for v in edges[u]:
    if visited[v]==False:
      dfs(v)
  if all(visited):
    return 0
  else:
    return 1
ab=[]
for i in range(m):
  a,b=map(int,input().split())
  edges[a-1].append(b-1)
  edges[b-1].append(a-1)
  ab.append([a,b])
for i in range(m):
  visited=[False]*n
  a,b=ab[i]
  edges[a-1].remove(b-1)
  edges[b-1].remove(a-1)
  cnt+=dfs(0)
  edges[a-1].append(b-1)
  edges[b-1].append(a-1)
print(cnt)

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


class UnionFind(object):

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

  def find(self, x):
  
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
  
  
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x != y:
      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)

count = 0     
for i in range(m):
  uf = UnionFind(n)
  for j in range(m):
    if i!=j:
      uf.union(info[j][0],info[j][1])
  for k in range(n):
    for l in range(n): 
      if not uf.is_same(k,l):
        count =  count +1 
        break
      else:
        continue
      break
    else:
      continue
    break
print(count)

Solution (Python):
N,M=map(int,input().split())
edges=[list(map(int,input().split())) for i in range(M)]
ans=0
for x in edges:
    l=list(range(N))
    for y in edges:
        if y!=x:l=[l[y[0]-1] if l[i]==l[y[1]-1] else l[i] for i in range(N)]
    if len(set(l))!=1:ans+=1
print(ans)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.parent = [-1]*n
    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]
    def union(self, x,y):
        root_x = self.root(x)
        root_y = self.root(y)
        if root_x == root_y:
            return False
        if self.parent[root_x] < self.parent[root_y]:
            self.parent[root_x] += self.parent[root_y]
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] += self.parent[root_x]
            self.parent[root_x] = root_y
        return True

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
ans = 0
for i in range(m):
    UF = UnionFind(n)
    use = ab[::]
    use.pop(i)
    for a, b in use:
        UF.union(a-1, b-1)
    if sum([j<0 for j in UF.parent])!=1:
        ans += 1
print(ans)

Solution (Python):
N,M=map(int,input().split())
E = [list(map(int,input().split())) for _ in range(M)]
from collections import defaultdict

ans=0
for i in range(M):
    d = defaultdict(list)
    for j in range(M):
        if i!=j:
            d[E[j][0]].append(E[j][1])
            d[E[j][1]].append(E[j][0])
    f = defaultdict(lambda: 0)
    f[1]=1
    que=d[1]
    while len(que)>0:
        tmp=[]
        for q in que:
            if f[q]==0:
                f[q]=1
                tmp+=d[q]
        que=tmp
    if len(f.keys())<N:
        ans+=1
print(ans)

Solution (Python):
N, M = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(M)]
ans = 0
for bridge in range(M):
    E = edges[0:bridge] + edges[bridge + 1:M]
    wf = [[1 for _ in range(N + 1)] for _ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            if i == j:
                wf[i][j] = 0
            if (min(i, j), max(i, j)) in E:
                wf[i][j] = 0
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            for k in range(1, N + 1):
                if wf[j][k] > wf[j][i] + wf[i][k]:
                    wf[j][k] = wf[j][i] + wf[i][k]
    if wf[1][1:] != [0] * N:
        ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
E0 = [frozenset(map(int, input().split())) for _ in range(m)]
E = set(E0)
ans = 0

for e in E0:
    e = list(e)
    v0, v = e[0], e[1]

    now_path = [v0]
    branches = []
    history = {v0}

    for _ in range(n):
        branch_pts = [w for w in range(1, n+1) if
                      frozenset([now_path[-1], w]) in E and
                      frozenset([now_path[-1], w]) != frozenset(e) and
                      w not in history]
        if v in branch_pts:
            break
        branches.extend([(len(now_path)-1, w) for w in branch_pts])
        history |= set(branch_pts)
        if not branches:
            ans += 1
            break
        branch = branches.pop(-1)
        now_path = now_path[:branch[0]+1]
        now_path.append(branch[1])

print(ans)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.parent = [-1]*n
    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]
    def union(self, x,y):
        root_x = self.root(x)
        root_y = self.root(y)
        if root_x == root_y:
            return False
        if self.parent[root_x] < self.parent[root_y]:
            self.parent[root_x] += self.parent[root_y]
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] += self.parent[root_x]
            self.parent[root_x] = root_y
        return True

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
ans = 0
for i in range(m):
    UF = UnionFind(n)
    use = ab[::]
    use.pop(i)
    for a, b in use:
        UF.union(a-1, b-1)
    if sum([j<0 for j in UF.parent]) -1:
        ans += 1
print(ans)

Solution (Python):


from copy import deepcopy

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

def is_simply_connected(adj):
    n = len(adj)
    visited = [(i == 0) for i in range(n)]
    dfs(0, adj, visited)
    return False not in visited

def main():
    n, m = map(int, input().split())
    adj = [[(i == j) for i in range(n)] for j in range(n)]
    edges = set()
    for i in range(m):
        a1, b1 = map(int, input().split())
        a = a1 - 1
        b = b1 - 1
        edges.add((a, b))
        adj[a][b] = True
        adj[b][a] = True

    res = 0
    for a, b in edges:
        adj[a][b] = adj[b][a] = False
        if not is_simply_connected(adj):
            res += 1
        adj[a][b] = adj[b][a] = True
    print(res)

main()

Solution (Python):


from copy import deepcopy

def dfs(x, adj, visited):
    for y, flag in enumerate(adj[x]):
        if flag and y not in visited:
            visited.add(y)
            dfs(y, adj, visited)

def is_simply_connected(adj):
    n = len(adj)
    visited = {0}  
    dfs(0, adj, visited)
    return len(visited) == n

def main():
    n, m = map(int, input().split())
    adj = [[(i == j) for i in range(n)] for j in range(n)]
    edges = set()
    for i in range(m):
        a1, b1 = map(int, input().split())
        a = a1 - 1
        b = b1 - 1
        edges.add((a, b))
        adj[a][b] = True
        adj[b][a] = True

    res = 0
    for a, b in edges:
        adj[a][b] = adj[b][a] = False
        if not is_simply_connected(adj):
            res += 1
        adj[a][b] = adj[b][a] = True
    print(res)

main()

Solution (Python):


from copy import deepcopy

def dfs(x, adj, visited):
    for y, flag in enumerate(adj[x]):
        if flag and y not in visited:
            visited.add(y)
            dfs(y, adj, visited)

def is_simply_connected(adj):
    n = len(adj)
    visited = {0}
    dfs(0, adj, visited)
    return len(visited) == n

def main():
    n, m = map(int, input().split())
    adj = [[(i == j) for i in range(n)] for j in range(n)]
    edges = set()
    for i in range(m):
        a1, b1 = map(int, input().split())
        a = a1 - 1
        b = b1 - 1
        edges.add((a, b))
        adj[a][b] = True
        adj[b][a] = True

    res = 0
    for a, b in edges:
        adjc = deepcopy(adj)
        adjc[a][b] = False
        adjc[b][a] = False
        if not is_simply_connected(adjc):
            res += 1
    print(res)

main()

Solution (Python):


from copy import deepcopy

def dfs(x, adj, visited):
    for y, flag in enumerate(adj[x]):
        if flag and y not in visited:
            visited.add(y)
            dfs(y, adj, visited)

def main():
    n, m = map(int, input().split())
    adj = [[(i == j) for i in range(n)] for j in range(n)]
    edges = set()
    for i in range(m):
        a1, b1 = map(int, input().split())
        a = a1 - 1
        b = b1 - 1
        edges.add((a, b))
        adj[a][b] = True
        adj[b][a] = True

    res = 0
    for e in edges:
        adjc = deepcopy(adj)
        adjc[e[0]][e[1]] = False
        adjc[e[1]][e[0]] = False
        visited = {0}
        dfs(0, adjc, visited)
        if len(visited) < n:
            res += 1
    print(res)

main()

Solution (Python):
class UnionFind:

    def __init__(self, size):
        self.table = [i for i in range(size)]

    def find(self, x):
        return self.table[x]

    def union(self, x, y):
        x1 = self.find(x)
        y1 = self.find(y)
        if x1 == y1: return False
        
        for i in range(len(self.table)):
            if self.table[i] == y1:
                self.table[i] = x1
        return True


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

    edges = []
    g = [[False] * N for _ in range(N)]
    for i in range(M):
        a, b = [int(x) for x in input().split()]
        edges.append((a-1, b-1))
        g[a-1][b-1] = g[b-1][a-1] = True

    ans = 0
    for i in range(len(edges)):
        uf = UnionFind(N)

        for j in range(len(edges)):
            e = edges[j]
            if i == j:
                
                continue
            uf.union(*e)

        n = len(set(uf.table))
        ans += n != 1

        
        
        
    return ans


def main():
    print(solve())


if __name__ == '__main__':
    main()

Solution (Python):
def dfs(u, g, visited):
    visited[u] = True

    for v in range(len(g)):
        if visited[v]:
            continue
        if g[u][v]:
            dfs(v, g, visited)


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

    import collections

    edges = []
    g = [[False] * N for _ in range(N)]
    for i in range(M):
        a, b = [int(x) for x in input().split()]
        edges.append((a-1, b-1))
        g[a-1][b-1] = g[b-1][a-1] = True

    ans = 0
    for e in edges:
        g[e[0]][e[1]] = g[e[1]][e[0]] = False

        
        visited = [False] * N

        dfs(0, g, visited)
        
        ans += not all(visited)

        g[e[0]][e[1]] = g[e[1]][e[0]] = True
    return ans


def main():
    print(solve())


if __name__ == '__main__':
    main()

Solution (Python):
def f(v,e):
  for x in v:
    if len(e[x]) == 1:
      y = e[x][0]
      v.remove(x)
      e[x] = []
      e[y].remove(x)
      return f(v,e)+1
  return 0 

  
n,m = map(int,input().split())
v = list(range(1,n+1))
e = [[]]*(n+1)
for _ in [0]*m:
  x,y = map(int,input().split())
  e[x] = e[x] + [y]
  e[y] = e[y] + [x]
print(f(v,e))

Solution (Python):
import Queue
def is_bridge(_a, _b, neighbors, N, M):
    q = Queue.Queue()
    q.put(_a)
    used = {_a}
    for _ in range(M):
        if q.empty():
            break
        fr = q.get()
        for to, is_nei in enumerate(neighbors[fr]):
            if  is_nei and (fr != _a or to != _b) and to not in used:
                q.put(to)
                used.add(to)
    return len(used) < N


N, M = map(int, raw_input().split())
neighbors = [[False] * N for _ in range(N)]
ab = []
for _ in range(M):
    _a, _b = map(int, raw_input().split())
    _a -= 1
    _b -= 1
    neighbors[_a][_b] = True
    neighbors[_b][_a] = True
    ab.append((_a, _b))

res = 0
for _a, _b in ab:
    if is_bridge(_a, _b, neighbors, N, M):
        res += 1
print res

Solution (Python):
import Queue
def is_bridge(_a, _b, neighbors, M):
    q = Queue.Queue()
    q.put(_a)
    used = {_a}
    for _ in range(M):
        if q.empty():
            break
        fr = q.get()
        for to, is_nei in enumerate(neighbors[fr]):
            if  is_nei and (fr != _a or to != _b) and to not in used:
                q.put(to)
                used.add(to)
    return len(used) < N


N, M = map(int, raw_input().split())
neighbors = [[False] * N for _ in range(N)]
ab = []
for _ in range(M):
    _a, _b = map(int, raw_input().split())
    _a -= 1
    _b -= 1
    neighbors[_a][_b] = True
    neighbors[_b][_a] = True
    ab.append((_a, _b))

res = 0
for _a, _b in ab:
    if is_bridge(_a, _b, neighbors, N):
        res += 1
print res

Solution (Python):
def multival(): return map(int,input().split())
def data(N=1): return [list(map(int,input().split())) for _ in range(N)]
mod = 10**9 + 7
inf = float("inf")


N,M = multival()
nemat = [[0]*N for _ in range(N)]
ans = M
info = []
for _ in range(M):
    a,b = multival()
    a -= 1; b-= 1
    nemat[a][b] = 1
    nemat[b][a] = 1
    info.append([a,b])

def dfs(now,visited):
    visited[now] = True
    if all(visited):
        global ans
        ans -= 1
        return
    for ne in range(N):
        if nemat[now][ne] == 1 and visited[ne] is False:
            dfs(ne,visited)
    
for i,j in info:
    nemat[i][j] = 0
    nemat[j][i] = 0
    dfs(0,[False]*N)
    nemat[i][j] = 1
    nemat[j][i] = 1

print(ans)

Solution (Python):
from collections import deque

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

ans = 0
for k in range(len(li)):
    li0 = li[:k] + li[k + 1:]
    
    edges = [[] for _ in range(n)]
    for i, j in li0:
        i -= 1
        j -= 1
        edges[i].append(j)
        edges[j].append(i)
    
    S = deque()
    S.append(0)
    visited = set()
    while len(S) > 0:
        u = S.pop()
        visited.add(u)
        for v in edges[u]:
            if v not in visited:
                S.append(v)
    if len(visited) < n:
        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 = (int(i) for i in input().split())
a = []
for i in range(m):
 tmp = list(int(i) for i in input().split())
 a.append(tmp)
ct = 0
for i in range(m):
  uf = UnionFind(n)
  for j in range(m):
    if i == j:
      nanban = j
    else:
      tmp1= a[j][0]
      tmp2= a[j][1]
      uf.union(tmp1,tmp2)
  c = a[nanban][0]
  d = a[nanban][1]
  if not uf.same_check(c,d):
   ct +=1
print(ct)

Solution (Python):
N, M = map(int, input().split())
E = {i:[] for i in range(N)}
mat = [[False for i in range(N)] for j in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)
    mat[a][b] = True
    mat[b][a] = True
cnt = 0
for i in range(N):
    if sum(mat[i]) == 1:
        while True:
            if len(E[i]) != 1:
                break
            j = E[i][0]
            E[i].remove(j)
            E[j].remove(i)
            cnt += 1
            i = j
print(cnt)

Solution (Python):

from copy import deepcopy
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
GM = [[False]*N for _ in range(N)]
GL = []
for _ in range(M):
  a, b = list(map(int, input().split()))
  GM[a-1][b-1], GM[b-1][a-1] = True, True
  GL.append([a-1,b-1])
  
def DFS(v,g):
  visited[v] = True
  for i in range(N):
    if g[v][i] and not visited[i]:
      DFS(i,g)

ans = 0

for i in range(M):
  G = deepcopy(GM)
  G[GL[i][0]][GL[i][1]], G[GL[i][1]][GL[i][0]] = False, False
  visited = [False] * N
  DFS(0,G)
  
  flg = False
  for j in range(N):
    if not visited[j]:
      flg = True
      break
      
  if flg:
    ans += 1

print(ans)

Solution (Python):

class UnionFind:
    def __init__(self, size):
        self.table = [i for i in range(size)]

    def find(self, x):
        return self.table[x]

    def union(self, x, y):
        x1 = self.find(x)
        y1 = self.find(y)

        if x1 == y1:
            return False

        for i in range(len(self.table)):
            if self.table[i] == y1:
                self.table[i] = x1
        return True


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

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

mat = [[0]*N for _ in range(N)]
for s, g in edges:
    mat[s][g] = 1
    mat[g][s] = 1

ans = 0

for i in range(M):
    uni = UnionFind(N)

    for j in range(M):
        if i != j:
            uni.union(edges[j][0], edges[j][1])

    if not all(uni.find(0) == uni.find(x) for x in range(N)):
        ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())
edges = []
for _ in range(M):
    a, b = list(map(int, input().split()))
    edges.append([a-1, b-1])

nodes = [0]*N

mat = [[0]*N for _ in range(N)]

for s, g in edges:
    nodes[s] += 1
    nodes[g] += 1
    mat[s][g] = 1
    mat[g][s] = 1

ans = 0


def check(nodes):
    return all(n != 1 for n in nodes)


ans = 0
while not check(nodes):
    for i in range(N):
        if nodes[i] == 1:
            for j in range(N):
                if mat[i][j]:
                    mat[i][j] = 0
                    mat[j][i] = 0
                    ans += 1
                    nodes[i] -= 1
                    nodes[j] -= 1
                    break
print(ans)

Solution (Python):
N, M = map(int, input().split())
edges = []
for _ in range(M):
    a, b = list(map(int, input().split()))
    edges.append([a-1, b-1])

nodes = [0]*N

mat = [[0]*N for _ in range(N)]

for s, g in edges:
    nodes[s] += 1
    nodes[g] += 1
    mat[s][g] = 1
    mat[g][s] = 1

ans = 0


def check(nodes):
    return all(n != 1 for n in nodes)


ans = 0
while not check(nodes):
    for i in range(N):
        if nodes[i] == 1:
            for j in range(N):
                if mat[i][j]:
                    mat[i][j] = 0
                    mat[j][i] = 0
                    ans += 1
                    nodes[i] -= 1
                    nodes[j] -= 1
                    break
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
G = [[False]*(N+1) for _ in range(N+1)]

for elem in AB:
    a, b = elem
    G[a][b] = True
    G[b][a] = True

used = [False] * (N+1)


def dfs(v):
    ret = 1
    used[v] = True
    for nv in range(1, N+1):
        if G[v][nv] and not used[nv]:
            ret += dfs(nv)
    return ret


ans = 0
for elem in AB:
    a, b = elem
    G[a][b] = False
    G[b][a] = False
    for j in range(1, N+1):
        used[j] = False
    if dfs(1) != N:
        ans += 1
    G[a][b] = True
    G[b][a] = True
print(ans)