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

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

adj_matrix = {} 
for i in range(1, N + 1):
    adj_lst = []
    for j in range(M):
        if edge_lst[j][0] == i:
            adj_lst.append(edge_lst[j][1])
        if edge_lst[j][1] == i:
            adj_lst.append(edge_lst[j][0])
    adj_matrix[i] = adj_lst







def dfs_bridge(graph, root, next, count, low, order, bridges): 
    count += 1
    order[next] = count
    low[next] = order[next]

    for w in graph[next]: 
        if order[w] == -1: 
            dfs_bridge(graph, next, w, count, low, order, bridges)

            low[next] = min(low[next], low[w])
            if low[w] == order[w]: 
                bridges.append((next, w))
        elif w != root: 
            low[next] = min(low[next], order[w])

def get_bridges(graph):
    bridges = []
    count = 0
    low = {n: -1 for n in graph.keys()}
    order = low.copy()

    for n in graph.keys():
        dfs_bridge(graph, n, n, count, low, order, bridges)
    
    return(bridges) 
            
ans = get_bridges(adj_matrix)
print(len(ans))

Solution (Python):
from collections import deque
N, M = map(int, input().split())
A = []
B = []
G = [[-1] * N for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a - 1][b - 1] = 1
    G[b - 1][a - 1] = 1
    A.append(a - 1)
    B.append(b - 1)


def BFS(G):  
    """
    >>> BFS([[-1, 1, 1], [1, -1, 1], [1, 1, -1]])
    True
    >>> BFS([[-1,1,-1], [1,-1,-1], [-1,-1,-1]])
    False
    >>> BFS([[-1,1,-1,-1], [1,-1,1,-1], [-1,1,-1,1], [-1,-1,1,-1]])
    True
    """
    q = deque()
    q.append(0)
    visited = [False] * len(G)
    while len(q) != 0:
        p = q.popleft()
        for j in range(len(G)):
            if G[p][j] == 1 and not visited[j]:
                q.append(j)
                visited[j] = True
    if False in visited:
        return False
    else:
        return True


count = 0
for i in range(M):
    G[A[i]][B[i]] = -1
    G[B[i]][A[i]] = -1
    if not BFS(G):
        count += 1
    G[A[i]][B[i]] = 1
    G[B[i]][A[i]] = 1
print(count)

Solution (Python):
from itertools import combinations
class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		while self.table[x] >= 0:
			x = self.table[x]
		return x

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
		return

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

ans = 0
for i in range(m):
	if i == 0:
		new_edges = edges[1:]
	elif i == m - 1:
		new_edges = edges[:m - 1]
	else:
		new_edges = edges[:i] + edges[i + 1:]
	uf = UnionFind(n)
	for e in new_edges:
		uf.union(e[0] - 1, e[1] - 1)
	for a, b in combinations(range(n), r=2):
		if uf.find(a) != uf.find(b):
			ans += 1
			break

print(ans)

Solution (Python):
n, m = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(m)]
count = 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:
        count += 1

print(count)

Solution (Python):
n, m = map(int, input().split())
edge = [[0]*n for _ in range(n)]
a = []
b = []
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    a.append(x)
    b.append(y)
    edge[x][y] = 1
    edge[y][x] = 1

def bfs():
    q = [0]
    visit = [False]*n
    visit[0] = True
    while q:
        x = q[0]
        q.pop(0)
        for i in range(n):
            if not visit[i] and edge[x][i] == 1:
                q.append(i)
                visit[i] = True
    return len(list(filter(lambda x:x, visit)))

ans = 0
for i in range(m):
    edge[a[i]][b[i]] = 0
    edge[b[i]][a[i]] = 0
    if bfs() < n:
        ans += 1
    edge[a[i]][b[i]] = 1
    edge[b[i]][a[i]] = 1

print(ans)

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

H = [[0 for _ in range(n)] for _ in range(n) ]
edge_list = []

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

def dfs(node):
    visited[node] = 1
    for node_,edge_ in enumerate(H[node]):
        if edge_ == 1:
            if visited[node_] == 1:
                continue
            dfs(node_)
ans = 0
for _ in edge_list:
    H[_[0] -1][_[1] - 1] = 0
    H[_[1] -1][_[0] - 1] = 0
    
    dfs(1)
    if 0 in visited:
        ans += 1
    H[_[0] -1][_[1] - 1] = 1
    H[_[1] -1][_[0] - 1] = 1
    visited = [0 for _ in range(n)]
print(ans)

Solution (Python):
def dfs(now):
    if vis[now]:
        return 0
    vis[now]=1
    for i in range(n):
        if graph[now][i]:
            dfs(i)
n,m=map(int,input().split())
edge=[[int(i) for i in input().split()]for i in range(m)]
graph=[[0 for i in range(n)]for i in range(n)]
for i in range(m):
    graph[edge[i][0]-1][edge[i][1]-1]=1
    graph[edge[i][1]-1][edge[i][0]-1]=1
vis=[0]*n
ans=0
for i in range(m):
    graph[edge[i][0]-1][edge[i][1]-1]=0
    graph[edge[i][1]-1][edge[i][0]-1]=0
    vis=[0]*n
    dfs(0)
    connect=False
    for j in range(n):
        if vis[j]==0:
            connect=True
    if connect:
        ans+=1
    graph[edge[i][0]-1][edge[i][1]-1]=1
    graph[edge[i][1]-1][edge[i][0]-1]=1
print(ans)

Solution (Python):



N,M = map(int, input().split())
g = [[False]*(N+1) for _ in range(N+1)] 
a = [0]*(M+1)
b = [0]*(M+1)
for i in range(1, M+1):
  a[i],b[i] = map(int, input().split())
  g[a[i]][b[i]] = g[b[i]][a[i]] = True

def dfs(v):
  visited[v] = True

  for v2 in range(1, N+1):
    if not g[v][v2]: continue
    
    if visited[v2]: continue
    dfs(v2)

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

print(count)

Solution (Python):
def dfs(now):
    if vis[now]==1:
        return 0
    vis[now]=1
    for i in range(n):
        if graph[now][i]==1:
            dfs(i)
n,m=map(int,input().split())
edge=[[int(i) for i in input().split()]for i in range(m)]
graph=[[0 for i in range(n)]for i in range(n)]
vis=[0]*n
for i in range(m):
    graph[edge[i][0]-1][edge[i][1]-1]=1
    graph[edge[i][1]-1][edge[i][0]-1]=1
ans=0
for i in range(m):
    graph[edge[i][0]-1][edge[i][1]-1]=0
    graph[edge[i][1]-1][edge[i][0]-1]=0
    vis=[0]*n
    dfs(0)
    connect=False
    for j in range(n):
        if vis[j]==0:
            connect=True
    if connect:
        ans+=1
    graph[edge[i][0]-1][edge[i][1]-1]=1
    graph[edge[i][1]-1][edge[i][0]-1]=1
print(ans)

Solution (Python):
def dfs(now):
    if vis[now]==1:
        return 0
    vis[now]=1
    for i in range(n):
        if graph[now][i]==1:
            dfs(i)
n,m=map(int,input().split())
edge=[[int(i) for i in input().split()]for i in range(m)]
graph=[[0 for i in range(n)]for i in range(n)]
vis=[0]*n
for i in range(m):
    graph[edge[i][0]-1][edge[i][1]-1]=1
    graph[edge[i][1]-1][edge[i][0]-1]=1
ans=0
for i in range(m):
    graph[edge[i][0]-1][edge[i][1]-1]=0
    graph[edge[i][1]-1][edge[i][0]-1]=0
    vis=[0]*n
    dfs(0)
    connect=False
    for j in range(n):
        if vis[j]==0:
            connect=True
    if connect:
        ans+=1
    graph[edge[i][0]-1][edge[i][1]-1]=1
    graph[edge[i][1]-1][edge[i][0]-1]=1
print(ans)

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

ans = 0
for i in range(M):
    visited = [0]*(N+1)
    p = [edges[i][0]]
    visited[p[0]] = 1
    p.extend(graph[edges[i][0]])
    p.remove(edges[i][1])
    for k in p:
        if visited[k]:
            continue
        visited[k] = 1
        p.extend(graph[k])
    if visited[edges[i][1]] == 0:
        ans += 1

print(ans)

Solution (Python):
class UnionFind(object):
  def __init__(self,n):
    self.table=[-1]*n
 
  def find(self,x):
    parent=self.table[x]
    if parent<0:
      return x
    else:
      root=self.find(parent)
      self.table[x]=root
      return root
 
  def union(self,a,b):
    root1=self.find(a)
    root2=self.find(b)
    if root1 != root2:
      if self.table[root1] != self.table[root2]:
        if self.table[root1] < self.table[root2]:
          self.table[root2]=root1
        else:
          self.table[root1]=root2
      else:
        self.table[root1]+=(-1)
        self.table[root2]=root1
      
N,M=map(int,input().split())
B=[]
for i in range(M):
  a,b=map(int,input().split())
  B.append((a,b))

def solve(x):
  a,b=B[x]
  uf=UnionFind(N+1)
  for i in range(M):
    if i!=x:
      uf.union(B[i][0],B[i][1])
  if uf.find(a)==uf.find(b):
    return False
  else:
    return True

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

Solution (Python):
import copy
N, M = map(int, input().split())
connectdic = {}
for i in range(1,N+1):
    connectdic[i] = set()

for _ in range(M):
    a, b = map(int, input().split())
    connectdic[a].add(b)
    connectdic[b].add(a)

count = 0
for i in range(1,N+1):
    for j in range(i+1,N+1):
        if j not in connectdic[i]:
            continue
        tempdic = copy.deepcopy(connectdic)
        tempdic[i].remove(j)
        tempdic[j].remove(i)
        startset = set([1])
        check = set([1])
        while len(startset) > 0:
            nextset = set()
            for k in startset:
                for l in tempdic[k]:
                    if l not in check:
                        check.add(l)
                        nextset.add(l)
            startset = nextset
        if len(check) != N:
            count += 1
print(count)

Solution (Python):

def DFS( graph, bridge, node, count, parent, low, pre):
    pre[node] = count
    count+= 1
    low[node] = pre[node]
    for n in graph[node]:
        if pre[n] == -1:
            low[node] = min( low[node], DFS( graph, bridge, n, count, node, low, pre))
            if low[n] == pre[n]:
                bridge.append( (node, n))
        else:
            if n == parent:
                continue
            low[node] = min( low[node], low[n])
    return low[node]

N, M = [int(x) for x in input().split()]
graph = [ [] for i in range(N)]
for i in range(M):
    a, b = [int(x) for x in input().split()]
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
bridge = []
low = [-1]*N
pre = [-1]*N
DFS( graph, bridge, 0, 0, -1, low, pre)
print( len(bridge))

Solution (Python):
def dfs(v):
    visited[v]=1
    for i in range(n):
        if connect[v][i]==0:
            continue
        if visited[i]==1:
            continue
        dfs(i)
n,m=map(int,input().split())
edge=[[int(i)for i in input().split()]for i in range(m)]
connect=[[0 for i in range(n)]for i in range(n)]
for i in range(m):
    connect[edge[i][0]-1][edge[i][1]-1]=1
    connect[edge[i][1]-1][edge[i][0]-1]=1
visited=[0]*n
ans=0
for i in range(m):
    connect[edge[i][0]-1][edge[i][1]-1]=0
    connect[edge[i][1]-1][edge[i][0]-1]=0
    for j in range(n):
        visited[j]=0
    dfs(0)
    brdge=False
    for j in range(n):
        if visited[j]==0:
            brdge=True
    if brdge:
        ans+=1
    connect[edge[i][0]-1][edge[i][1]-1]=1
    connect[edge[i][1]-1][edge[i][0]-1]=1
print(ans)

Solution (Python):
def dfs(v):
    visited[v]=1
    for i in range(n):
        if connect[v][i]==0:
            continue
        if visited[i]==1:
            continue
        dfs(i)
n,m=map(int,input().split())
edge=[[int(i)for i in input().split()]for i in range(m)]
connect=[[0 for i in range(n)]for i in range(n)]
for i in range(m):
    connect[edge[i][0]-1][edge[i][1]-1]=1
    connect[edge[i][1]-1][edge[i][0]-1]=1
visited=[0]*n
ans=0
for i in range(m):
    connect[edge[i][0]-1][edge[i][1]-1]=0
    connect[edge[i][1]-1][edge[i][0]-1]=0
    for j in range(n):
        visited[j]=0
    dfs(0)
    brdge=False
    for j in range(n):
        if visited[j]==0:
            brdge=True
    if brdge:
        ans+=1
    connect[edge[i][0]-1][edge[i][1]-1]=1
    connect[edge[i][1]-1][edge[i][0]-1]=1
print(ans)

Solution (Python):
import copy


def m():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    E = []
    visited = []
    for i in range(M):
        a, b = map(int, input().split())
        E.append((a, b))

    for m in range(M):
        a, b = E[m]
        graph[a].append(b)
        graph[b].append(a)

    def dfs(v, g):
        if visited[v] == True:
            return
        visited[v] = True
        for i in g[v]:
            dfs(i, g)

    def is_all_visited(v):
        for i in range(1, N + 1):
            if v[i]:
                pass
            else:
                return False
        return True

    ans = 0
    for j in range(M):
        y, z = E[j]
        visited = [False] * (N + 1)
        tmp = copy.deepcopy(graph)
        tmp[y].remove(z)
        tmp[z].remove(y)
        dfs(1, tmp)
        if is_all_visited(visited):
            pass
        else:
            ans += 1

    return ans


print(m())

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


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

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

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

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if j == i:
            continue
        uf.union(AB[j][0], AB[j][1])
    for k in range(N):
        uf.find(k+1)
    if len(set(uf.par)) != 2:
        ans += 1

print(ans)

Solution (Python):
N,M = map(int,input().split())
A,B,Ans = [[] for _ in range(N)],[],0
def s(v,a,b):
    visited[v] = True
    for n in A[v]:
        if not visited[n] and set([v,n]) != set([a,b]):
            s(n,a,b)

for i in range(M):
    a,b = map(int,input().split())
    A[a-1].append(b-1)
    A[b-1].append(a-1)
    B.append((a-1,b-1))
for i in range(M):
    visited = [True]+[False]*(N-1)
    a,b = B[i]
    s(0,a,b)
    if visited != [True]*N:
        Ans += 1
print(Ans)

Solution (Python):
N,M = map(int,input().split())
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]

parent = [i for i in range(N)]
rank = [0] * N
def root(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = root(parent[a])
        return parent[a]
def is_same(a,b):
    return root(a) == root(b)
def unite(a,b):
    ra = root(a)
    rb = root(b)
    if ra == rb: return
    if rank[ra] < rank[rb]:
        parent[ra] = rb
    else:
        parent[rb] = ra
        if rank[ra] == rank[rb]: rank[ra] += 1

ans = 0
for i in range(M):
    parent = [i for i in range(N)]
    rank = [0] * N
    for j,(a,b) in enumerate(src):
        if i == j: continue
        unite(a,b)
    if len(set([root(i) for i in range(N)])) > 1:
        ans += 1
print(ans)

Solution (Python):


import numpy as np

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

adjacent = np.zeros((N, N))
for l in L:
    adjacent[l[0] - 1, l[1] - 1] = 1
    adjacent[l[1] - 1, l[0] - 1] = 1


pre = [-1 for _ in range(N)]
low = [-1 for _ in range(N)]
v = k = 0
ans = 0


def dfs(v, pre, low, k, parent):
    global ans
    pre[v] = k
    k += 1
    low[v] = pre[v]
    for to, n in enumerate(adjacent[v, :]):
        if n == 1:
            if pre[to] == -1:
                
                
                
                
                low[v] = min(low[v], dfs(to, pre, low, k, v))
                if low[to] == pre[to]:
                    ans += 1
                    
            else:
                
                if to == parent:
                    pass
                else:
                    low[v] = min(low[v], low[to])

    return low[v]


dfs(v, pre, low, k, -1)

print(ans)

Solution (Python):
n, m = map(int, input().split())
t, d = {}, []

if n > m:
    print(m)
else:
    for i in range(m):
        a, b = map(int, input().split())
        t[a] = t.get(a, 0) + 1
        t[b] = t.get(b, 0) + 1
        d.append((a, b))

    while True:
        b = 0
        for i in t:
            if t[i] == 1:
                for j in d:
                    if j[0] == i or j[1] == i:
                        for k in j:
                            if k != i and t[k] > 1:
                                t[k] -= 1
                                t[i] = 0
                                b += 1

        if b == 0:
            break

    b = 0
    for i in t:
        if t[i] == 0:
            b += 1
    print(b)

Solution (Python):






def is_visited(graph):
    visited = [False] * len(graph[0])

    def dfs(x: int):
        if visited[x]:
            return

        visited[x] = True

        for i in range(n):
            if graph[x][i]:
                dfs(i)

    dfs(0)
    return visited


if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    a = [0 for _ in range(m)]
    b = [0 for _ in range(m)]
    graph = [[0 for i in range(n)] for j in range(n)]

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

    bridge_count = 0

    for j in range(m):
        graph[a[j]][b[j]] = False
        graph[b[j]][a[j]] = False

        if False in is_visited(graph):
            bridge_count += 1

        graph[a[j]][b[j]] = True
        graph[b[j]][a[j]] = True

    print(bridge_count)

Solution (Python):






def dfs(x: int):
    global visited, graph

    if visited[x]:
        return

    visited[x] = True

    for i in range(n):
        if graph[x][i]:
            dfs(i)


if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    a = [0 for _ in range(m)]
    b = [0 for _ in range(m)]
    graph = [[0 for i in range(n)] for j in range(n)]

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

    bridge_count = 0

    for j in range(m):
        graph[a[j]][b[j]] = False
        graph[b[j]][a[j]] = False

        visited = [False] * len(graph[0])
        dfs(0)

        if False in visited:
            bridge_count += 1

        graph[a[j]][b[j]] = True
        graph[b[j]][a[j]] = True

    print(bridge_count)

Solution (Python):






def dfs(x: int):
    if visited[x]:
        return

    visited[x] = True

    for i in range(n):
        if graph[x][i]:
            dfs(i)


if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    a = [0 for _ in range(m)]
    b = [0 for _ in range(m)]
    graph = [[0 for i in range(n)] for j in range(n)]

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

    bridge_count = 0

    for j in range(m):
        graph[a[j]][b[j]] = False
        graph[b[j]][a[j]] = False

        visited = [False] * len(graph[0])
        dfs(0)

        if False in visited:
            bridge_count += 1

        graph[a[j]][b[j]] = True
        graph[b[j]][a[j]] = True

    print(bridge_count)

Solution (Python):
import collections as col

graph = col.defaultdict(set)
used = set()
ans = 0

def dfs(x,t):
    if x == t:
        return True
    used.add(x)
    ret = False
    for y in graph[x]:
        if y not in used:
            ret = ret or dfs(y,t)
    return ret

def solve():
    n,m = map(int,input().split())
    global used,ans
    for i in range(0,m):
        a,b = map(int,input().split())
        graph[a].add(b)
        graph[b].add(a)
    for a in graph:
        for b in graph[a]:
            graph[a].remove(b)
            used = set()
            if not dfs(a,b):
                ans += 1
            graph[a].add(b)
    print(ans//2)
    return

if __name__ == "__main__":
    solve()

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

ans = 0
for k in range(M):
    F = E[:k]+E[k+1:]
    D = [[10**9+7 for l in range(N)] for m in range(N)]
    for p in range(N):
        D[p][p] = 0
    for n in F:
        D[n[0]-1][n[1]-1] = D[n[1]-1][n[0]-1] = 1
    for s in range(N):
        for t in range(N):
            for u in range(N):
                if D[t][u] > D[t][s] + D[s][u]:
                    D[t][u] = D[t][s] + D[s][u]
    f = 0
    for p in range(N):
        for q in range(N):
            if D[p][q] > N:
                f = 1
    ans += f
print(ans)

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

def dfs(v,a,b):
    visited[v] = True
    for n in E1[v]:
        if not visited[n] and set([v,n]) != set([a,b]):
            dfs(n,a,b)


E1 = [[] for _ in range(N)]
E2 = []
Ans = 0

for i in range(M):
    a,b = map(int,input().split())
    E1[a-1].append(b-1)
    E1[b-1].append(a-1)
    E2.append((a-1,b-1))
for i in range(M):
    visited = [True]+[False]*(N-1)
    a,b = E2[i]
    dfs(0,a,b)
    if visited != [True]*N:
        Ans += 1
print(Ans)

Solution (Python):
n,m = (int(i) for i in input().split())
a,b=[0 for i in range(m)],[0 for i in range(m)]
g = [[0 for i in range(n)] for j in range(n)]
ans = 0

def dfs(v,visited):
    if visited[v]:
        return
    visited[v] = True 
    for i in range(n):
        if g[v][i]:
            dfs(i,visited)

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

for i in range(m):
    visited = [False for i in range(n)]
    g[a[i]][b[i]], g[b[i]][a[i]] = False,False 

    dfs(0,visited)

    if not all(visited):
        ans += 1

    g[a[i]][b[i]], g[b[i]][a[i]] = True, True 
print(ans)

Solution (Python):
N,M=map(int,input().split())
s,t=[],[[] for j in range(N)]
for i in range(M):
    xx,yy=map(int,input().split())
    x,y=xx-1,yy-1
    s+=[[x,y]]
    t[x].append(y)
    t[y].append(x)
def loop(q,j,k):
    w.append(q)
    for kk in t[q]:
        if kk not in w and not (q==j and kk==k)and not(q==k and kk==j):
            loop(kk,j,k)
ans=0            
for ii in range(M):
    w=[]
    [j,k]=s[ii]
    loop(j,j,k)
    if len(w)!=N:
        ans+=1
print(ans)

Solution (Python):
def c_bridge(N, M, E):
    """
    N:頂点の数
    M:辺の数
    E:辺で結ばれる頂点の組
    """
    def dfs(v):
        
        visited[v] = True
        for v2 in range(N):
            
            if adjacent[v][v2] == False:
                continue
            
            if visited[v2] == True:
                continue
            dfs(v2)

    
    adjacent = [[0 for _ in range(N)] for _ in range(N)]
    for a, b in E:
        a, b = a - 1, b - 1
        adjacent[a][b] = True
        adjacent[b][a] = True

    
    
    ans = 0
    for a, b in E:
        a, b = a - 1, b - 1
        
        adjacent[a][b] = False
        adjacent[b][a] = False

        
        visited = [False for _ in range(N)]
        
        dfs(0)
        
        if not all(visited):
            ans += 1

        
        adjacent[a][b] = True
        adjacent[b][a] = True
    return ans

N,M = [int(i) for i in input().split()]
E = [[int(i) for i in input().split()] for j in range(M)]
print(c_bridge(N, M, E))

Solution (Python):
def dfs(g, s, u):
    s.add(u)
    if len(s) == len(g):
        return True
    for v in g[u]:
        if v not in s:
            if dfs(g, s, v):
                return True
    return False

n, m = map(int, input().split())
e = []
for _ in range(m):
    a, b = map(int, input().split())
    e.append((a - 1, b - 1))
c = 0
for i in range(m):
    g = [list() for _ in range(n)]
    for j in range(len(e)):
        if j == i: continue
        a, b = e[j]
        g[a].append(b)
        g[b].append(a)
    if not dfs(g, set(), 0): c += 1
print(c)

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

def connected(v,visited):
    visited[v]=1
    if sum(visited)==n:
        visited=[0]*n
        return 1
    count=0
    for i in range(n):
        if path[v][i]==1 and visited[i]==0:
            visited[i]=1
            count+=connected(i,visited)
    visited=[0]*n
    return count
bridge=0

for x in range(n):
    for y in range(x+1,n):
        if path[x][y]==1:
            visited=[0]*n
            path[x][y]=0
            if not connected(x,visited):
                bridge+=1
            path[x][y]=1
print(bridge)

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

def check(p):
    used[p] = 1
    for i in range(n):
        if p != i and table[p][i] == 1 and used[i] != 1:
            check(i)

ans = 0
for i in range(m):
    table[v[i][0]][v[i][1]] = 0
    table[v[i][1]][v[i][0]] = 0
    used = [0 for i in range(n)]
    check(0)
    if(sum(used) != n): ans += 1
    table[v[i][0]][v[i][1]] = 1
    table[v[i][1]][v[i][0]] = 1

print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(20000000)
def check(p):
    global used
    used[p]=1
    for i in range(n):
        if(p!=i and table[p][i]==1 and used[i]!=1):
            check(i)

n,m=map(int,input().split())
v=[]
table=[[0 for i in range(n)] for i in range(n)]
for i in range(m):
    a,b=(map(int,input().split()))
    table[a-1][b-1]=1
    table[b-1][a-1]=1
    v.append((a-1,b-1))
ans=0
for i in range(m):
    table[v[i][0]][v[i][1]]=0
    table[v[i][1]][v[i][0]]=0
    used=[0 for i in range(n)]
    check(0)
    if(sum(used)!=n):
        ans+=1
    table[v[i][0]][v[i][1]]=1
    table[v[i][1]][v[i][0]]=1
print(ans)

Solution (Python):
N,M=map(int,input().split())
graph = []
for i in range(M):
  l,r = map(int,input().split())
  graph.append((l,r))
count = 0
for j in range(M):
  queue = [graph[j][0]]
  check = [graph[j][0]]
  while len(queue) > 0:
    for k in range(M): 
      if graph[k][0] == queue[0] and graph[k][1] not in check and k != j:
        queue.append(graph[k][1])
        check.append(graph[k][1])
      elif graph[k][1] == queue[0] and graph[k][0] not in check and k != j:
        queue.append(graph[k][0])
        check.append(graph[k][0])
    queue.pop(0)
  if len(check) == N:
    count += 1
print(M - count)

Solution (Python):
def connect(blist, a):
	x = []
	for i in range(len(blist)):
		if blist[i][0]==a:
			x.append(blist[i][1])
	for j in range(len(blist)):
		if blist[j][1]==a:
			x.append(blist[j][0])
	return(x)

n,m = (int(i) for i in input().split())
y = [[int(i) for i in input().split()] for i in range(m)]
answer = m
for j in range(len(y)):
	y2,z = [],set()
	for k in range(1,n+1):
		y2.append(connect(y[:j]+y[min(j+1,len(y)):],k))
	for j2 in y2[y[j][0]-1]:
		z.add(j2)
	num = 0
	while y[j][1] not in z and len(z) != num:
		num,z2 = len(z),list(z)
		for k in z2:
			for k2 in y2[k-1]:
				z.add(k2)
	if y[j][1] in z:
		answer -= 1
print(answer)

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

ret = 0

for i in range(M):
    visited = [False for _ in range(N + 1)]

    queue = [1]
    visited[1] = True

    while queue:

        p = queue[0]
        queue.pop(0)

        for j, e in enumerate(edge):
            if i == j:
                continue
            if e[0] != p and e[1] != p:
                continue

            if not visited[e[0]]:
                visited[e[0]] = True
                queue.append(e[0])
            if not visited[e[1]]:
                visited[e[1]] = True
                queue.append(e[1])

    if sum(visited) != N:
        ret += 1

print(ret)

Solution (Python):
V, E = map(int, input().split())
a = [0 for i in range(E)]
b = [0 for i in range(E)]
m = [[0 for i in range(V)] for i in range(V)]
for i in range(E):
    a[i], b[i]=map(int, input().split())
    m[a[i]-1][b[i]-1]+=1
    m[b[i]-1][a[i]-1]+=1
S=0
for n in range(E):
    m[a[n]-1][b[n]-1]-=1
    m[b[n]-1][a[n]-1]-=1
    U=[[] for i in range(V)]
    for i in range(V):
        for j in range(V):
            if m[i][j]!=0:
                U[i].append(j)
    P=[set() for i in range(E+1)]
    P[0].add(0)
    Q=set()
    R=[False for i in range(V)]
    for i in range(1,E+1):
        for u in P[i-1]:
            for v in U[u]:
                if not(R[v]):
                    R[v]=True
                    P[i].add(v)
                    Q.add(v)
        if len(P[i])==0:
            break
    if len(Q)!=V:
        S+=1
    m[a[n]-1][b[n]-1]+=1
    m[b[n]-1][a[n]-1]+=1
print(S)