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())
ab = [list(map(int, input().split())) for _ in range(m)]
edge = [[False for j in range(n)] for i in range(n)]
for i in range(m):
	edge[ab[i][0]-1][ab[i][1]-1] = edge[ab[i][1]-1][ab[i][0]-1] = True
visited = [False for j in range(n)]

def dfs(v):
	visited[v] = True
	for i in range(0, n):
		if edge[v][i]==True and visited[i]==False:
			dfs(i)

ans = 0
for i in range(m):
	edge[ab[i][0]-1][ab[i][1]-1] = edge[ab[i][1]-1][ab[i][0]-1] = False
	for j in range(n):
		visited[j] = False
	dfs(0)
	bridge = False
	for j in range(n):
		if visited[j]==False:
			bridge = True
			break
	if bridge:
		ans += 1
	edge[ab[i][0]-1][ab[i][1]-1] = edge[ab[i][1]-1][ab[i][0]-1] = True
print(ans)

Solution (Python):
def bfs(n, path):
    check = [0]*n
    check[0] = 1
    que = [0]
    while que:
        u = que.pop()
        for v in path[u]:
            if check[v] == 0:
                check[v] = 1
                que.append(v)
    if check != [1]*n:
        return 1
    else:
        return 0

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

A = []
B = []
for i in range(m):
    a, b = map(int, input().split())
    A += [a-1]
    B += [b-1]
ans = 0

for i in range(m):
    edges = [[] for _ in range(n)]
    for j in range(m):
        if j != i:
            edges[A[j]] += [B[j]]
            edges[B[j]] += [A[j]]
    ans += bfs(n, edges)
print(ans)

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

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


def find(a, x):
    if a[x] != x:
        a[x] = find(a, a[x])
    return a[x]


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


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

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

G = [[0] * N for _ in range(N)]
for ab in AB:
    G[ab[0]][ab[1]] = 1
    G[ab[1]][ab[0]] = 1


def dfs(Gn, a, x):
    a[x] = 1
    for i in range(N):
        if Gn[x][i] == 1 and a[i] == 0:
            a[i] = 1
            dfs(Gn, a, i)


count = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if G[i][j] == 1:
            Gn = copy.deepcopy(G)
            Gn[i][j] = 0
            Gn[j][i] = 0
            flag = False
            for k in range(N):
                a = [0] * N
                dfs(Gn, a, k)
                if all(a):
                    flag = True
                    break
            if not flag:
                count += 1
print(count)

Solution (Python):
def DFS(N, copyedge):
    matrix = [[] for i in range(N)]
    for a, b in copyedge:
        matrix[a].append(b)
        matrix[b].append(a) 
    check = [True]*N 
    check[0] = False
    Que = [0] 

    while len(Que) != 0:
        now = Que.pop() 
        for i in matrix[now]:
            if check[i] == True:
                check[i] = False
                Que.append(i) 
    if True not in check:
        return 0 
    else:
        return 1 


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

for i in range(m):
    edge.append([int(i) - 1 for i in input().split()])
for i in range(m):
    copyedge = edge[:i] + edge[i+1:]
    ans += DFS(n, copyedge)
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):
import copy

def DFS(start, G):
    stack = []
    check = []
    check.append(start)
    stack.append(start)
    while stack:
        node = stack.pop()
        for child in G[node]:    
            if child not in check:
                check.append(child)
                stack.append(child)
    return set(check)

N, M = (int(i) for i in input().split())
G = []
S = []
for i in range(N + 1):
    G.append([])

for i in range(M):
    a,b = (int(j) for j in input().split())
    G[a].append(b)
    G[b].append(a)
    S.append( (a,b) )

res = 0
for side in S:
    a, b = side 
    dashG = copy.deepcopy(G)
    dashG[a].remove(b)
    dashG[b].remove(a)
    if DFS(a, dashG) != DFS(b, dashG):
        res += 1

print(res)

Solution (Python):

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

def check(a,b):
    visited = [False for _ in range(n)]
    stack = [0]
    while len(stack)>0:
        e = stack.pop()
        visited[e] = True
        for v in edge[e]:
            if (e==a and v==b) or (e==b and v==a):
                continue
            if not visited[v]:
                stack.append(v)
    return all(visited)

res = 0
for a,b in ab:
    if not check(a,b):
        res += 1
print(res)

Solution (Python):
graph = 0
node_visited = 0
num_node = 0

def search_route(current_node):
    global node_visited
    node_visited[current_node] = True
    for next_node in range(num_node):
        if graph[current_node][next_node] == False:
            continue
        if node_visited[next_node] == True:
            continue
        search_route(next_node)
    
def main():
    global graph, node_visited, num_node
    num_node, num_edge = map(int, input().split())
    all_edges = [list(map(int, input().split())) for i in range(num_edge)]
    graph = [[False for j in range(num_node)] for i in range(num_node)]
    for edge_s, edge_g in all_edges:
        graph[edge_s - 1][edge_g - 1] = graph[edge_g - 1][edge_s - 1] = True
        
    num_bridge = 0
    for edge_s, edge_g in all_edges:
        graph[edge_s - 1][edge_g - 1] = graph[edge_g - 1][edge_s - 1] = False
        node_visited = [False for i in range(num_node)]
        search_route(current_node = 0)
        for node in node_visited:
            if node == False:
                num_bridge += 1
                break
        graph[edge_s - 1][edge_g - 1] = graph[edge_g - 1][edge_s - 1] = True
    print(num_bridge)

if __name__ == '__main__':
    main()

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

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

tmp = []

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

def DFS(now_V, now_Log, ans):
    
    if sum(now_Log)==N:
        return 1
    
    for i in V[now_V]:
        if now_Log[i]<1:
            now_Log[i]=1
            ans = DFS(i, now_Log, ans)
    
    return ans

count = 0
          
for i in range(M):
    
    Log = [0]*N
    Log[0] = 1
    
    V[tmp[i][0]-1].remove(tmp[i][1]-1)
    V[tmp[i][1]-1].remove(tmp[i][0]-1)
    if DFS(0, Log, 0)<1:
        count = count+1
    V[tmp[i][0]-1].append(tmp[i][1]-1)
    V[tmp[i][1]-1].append(tmp[i][0]-1)
    
print(count)

Solution (Python):
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]:  
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                
                
                self.table[s1] += -1
                self.table[s2] = s1
        return


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

count = 0
for i in range(m):
    
    union = UnionFind(n)
    for j in range(m):
        if j != i:
            union.union(a[j], b[j])
    root = union.find(0)
    for j in range(1, n):
        if union.find(j) != root:
            count += 1
            break
print(count)

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

for _ in range(m):
    ab = list(map(int, input().split()))
    bridge[ab[0]][ab[1]] = 1
    bridge[ab[1]][ab[0]] = 1

polygon = []
def search(before, nowi, route):
    global bridge
    for i in range(1, n + 1):
        if before == i or nowi == i :
            continue
        if bridge[nowi][i] == 1:
            if i in route:
                for j in range(len(route)):
                    if route[j] == i:
                        polygon.append(route[j:len(route) + 1])
                        break
                continue
            else:
                search(nowi, i, route + [i])
search(1, 1, [1])

for i in polygon:
    for j in range(1, len(i)):
        bridge[i[j-1]][i[j]] = 0
        bridge[i[j]][i[j-1]] = 0

print(sum(map(sum, bridge)) // 2)

Solution (Python):
n,m=map(int,input().split())
x=[]
d=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    d[a-1].append(b-1)
    d[b-1].append(a-1)
    x.append((a-1,b-1))
ans=0
for i in x:
    t=set([i[0]])
    r=set()
    while len(t):
        o=t.pop()
        for j in d[o]:
            if j not in r and len(set([o,j])&set([i[0],i[1]]))!=2:
                r.add(j)
                t.add(j)
    if len(r)!=n: ans+=1
print(ans)

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

s = []
for i in range(m):
    s.append([int(w) for w in input().split()])
s.sort(key=lambda x:(x[0], x[1]))
adj = []
for i in range(n):
    adj.append([])
for i in range(n):
    for j in range(n):
        adj[i].append(0)

for i in range(m):
    adj[s[i][0] - 1][s[i][1] - 1] = 1
    adj[s[i][1] - 1][s[i][0] - 1] = 1


labelli = [-1]*n
label = 0
v = 0
labelli[0] = label
p = 0
back = []
backnumber = []
q = 0
count = 0
for h in range(m):
    if h == 0:
        adj[s[h][0] - 1][s[h][1] - 1] = 0
        adj[s[h][1] - 1][s[h][0] - 1] = 0
    else:
        adj[s[h - 1][0] - 1][s[h - 1][1] - 1] = 1
        adj[s[h - 1][1] - 1][s[h - 1][0] - 1] = 1
        adj[s[h][0] - 1][s[h][1] - 1] = 0
        adj[s[h][1] - 1][s[h][0] - 1] = 0
        q = 0
        labelli = [-1] * n
        label = 0
        labelli[0] = label
    while q == 0:
        for j in range(n):
            if adj[v][j] == 1 and labelli[j] == -1:
                label += 1
                v = j
                labelli[j] = label
                p = 1
                break
        if v == 0:
            for l in range(n):
                if adj[v][j] == 1 and labelli[j] == -1:
                    break
                if l == n - 1:
                    q = 1
                    p = 1
                    if min(labelli) == -1:
                        count += 1
        if p == 0:
            for k in range(n):
                if adj[v][k] == 1:
                    if labelli[v] > labelli[k]:
                        back.append(abs(labelli[v] - labelli[k]))
                        backnumber.append(k)
            v = backnumber[back.index(min(back))]
            back = []
            backnumber = []
        p = 0

print(count)

Solution (Python):
def DFS(N, copyedge):
    matrix = [[] for i in range(N)]
    for a, b in copyedge:
        matrix[a].append(b)
        matrix[b].append(a)
        
    check = [True]*N
    check[0] = False
    Que = [0]

    while len(Que) != 0:
        now = Que.pop()
        for i in matrix[now]:
            if check[i] == True:
                check[i] = False
                Que.append(i)
    if True not in check:
        return 0
    else:
        return 1
            
        

ans = 0
N, M = map(int, input().split())
edge = []

for i in range(M):
    edge.append([int(i) - 1 for i in input().split()])
    
for i in range(M):
    copyedge = edge[:i] + edge[i+1:] 
    ans += DFS(N, copyedge)
print(ans)

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

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

  def unite(self,x,y):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      pass
    else:
      self.Tree[s1]=s2
      
N,M=map(int,input().split())
Uf=Unionfind(N)
Flag=0
B=0
A=[]
Edge=[[int(i) for i in input().split()] for i in range(M)]
for m in range(M):
  Edge_copy=list(Edge)
  del Edge_copy[m]
  for e in Edge_copy:
    Uf.unite(e[0]-1,e[1]-1)
  for a in range(N):
    A.append(Uf.find(a))
  for n in range(N-1):
    if Uf.find(n)!=Uf.find(n+1):
      Flag=1
      break
  if Flag==1:
    B+=1
  Flag=0
  Uf=Unionfind(N)
  A=[]
print(B)

Solution (Python):
N,M=map(int,input().split())
List=[[int(i) for i in input().split()] for i in range(M)]
S=0
for i in range(M):
  new_List=list(List)
  del new_List[i]
  islands=[1]
  for i in islands:
    for j in new_List:
      if i in j:
        j=[item for item in j if item not in islands]
        islands.extend(j)
  if len(islands)<N:
    S+=1
print(S)

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 copy
N,M=map(int,input().split())
A=[]
L=[[1000for i in range(N)]for j in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    A.append([a,b])
    L[a-1][b-1]=1
    L[b-1][a-1]=1
    
for j in range(N):
    L[j][j]=0


l=copy.deepcopy(L)

cnt=0
for k in range(M):
    L=copy.deepcopy(l)
    L[A[k][0]-1][A[k][1]-1]=1000
    L[A[k][1]-1][A[k][0]-1]=1000
    for x in range(N):
        for y in range(N):
            for z in range(N):
                if L[y][z]>L[y][x]+L[x][z]:
                    L[y][z]=L[y][x]+L[x][z]
    
    if L[A[k][0]-1][A[k][1]-1]>=1000:
        cnt+=1
    L[A[k][0]-1][A[k][1]-1]=1
    L[A[k][1]-1][A[k][0]-1]=1

print(cnt)

Solution (Python):
N, M = map(int, input().split())
ab = []
array1 = [[] for _ in range(N+1)]
result = 0

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

for i in ab:
    array2 = [j[:] for j in array1]
    array2[i[0]].remove(i[1])
    array2[i[1]].remove(i[0])
    L = []
    save = []
    x = 1
    
    while True:
        if not x in L:
            L.append(x)
            save.append(x)

        if len(L) == N:
            break

        flag = True
        for j in array2[x]:
            if not j in L:
                x = j
                flag = False
                break

        if flag:
            del save[-1]
            if not save:
                result += 1
                break

            x = save[-1]

print(result)

Solution (Python):
def DFS(start,e):
    global edge
    global g
    global visited
    visited[start]=1

    cant=None
    if(e[0]==start):
        cant=e[1]
    elif(e[1]==start):
        cant=e[0]
    for ed in g[start]:
        if(ed==cant):
            continue
        if(visited[ed]==None):
            DFS(ed,e)
            

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

for _ in range(m):
    v,w=map(int,input().split())
    g[v-1].append(w-1)
    g[w-1].append(v-1)
    edge.append((v-1,w-1))


ans=0
for e in edge:
    visited=[None]*n
    DFS(0,e)
    flag=True
    for i in range(n):
        if(visited[i]==None):
            flag=False
    if(not flag):
        ans+=1

print(ans)

Solution (Python):
import copy


N, M = list(map(int, input().split()))
G = dict()
paths = []
for i in range(0,M):
    a, b = list(map(int, input().split()))
    paths.append([a,b])
    if a in G:
        G[a] += [b]
    else:
        G[a] = [b]
    if b in G:
        G[b] += [a]
    else:
        G[b] = [a]


def dfs(s):
    visited[s-1] = True
    for p in _G[s]:
        if visited[p-1]:
            continue
        else:
            dfs(p)


ans = 0

for i in range(M):
    _G = copy.deepcopy(G)
    _G[paths[i][0]].remove(paths[i][1])
    _G[paths[i][1]].remove(paths[i][0])
    
    visited = [False for i in range(N)]
    dfs(1)
    if not all(visited):
        
        ans += 1
    
print(ans)

Solution (Python):
N, M = map(int, input().split())
sides = []
def dfs(now):
    history[now] = 1
    for i in List[now]:
        if history[i] == 0:
            dfs(i)
    flag = 0
    for i in range(1, N+1):
        if history[i] == 0:
            flag = 1
    if flag == 0:
        return 0
    else:
        return 1
for i in range(M):
    sides.append(list(map(int, input().split())))

ans = 0
for k in range(M):
    side = sides[:]
    del side[k]
    List = [[] for i in range(N+1)]
    for i in range(M-1):
        List[side[i][0]].append(side[i][1])
        List[side[i][1]].append(side[i][0])

    history = [0 for i in range(N+1)]
    ans += dfs(1)



print(ans)

Solution (Python):
from collections import deque
def dfs(v):
    global adjacency_mat, visited
    st = deque([]) 
    st.append(v)
    while st:
        
        h = st.pop()
        visited[h] = True
        for i in range(N):
            
            if adjacency_mat[h][i] == None:
                continue
            
            if visited[i] == True:
                continue
            
            st.append(i)

if __name__ == "__main__":
    N, M = map(int, input().split())
    list_ab = [[] for _ in range(M)]
    adjacency_mat = [[None]* N for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        list_ab[i].append(a-1)
        list_ab[i].append(b-1)
        adjacency_mat[a-1][b-1] = 1
        adjacency_mat[b-1][a-1] = 1
        
    ans = 0
    for a, b in list_ab:
        visited = [False] * N
        
        adjacency_mat[a][b] = None
        adjacency_mat[b][a] = None
        
        dfs(0)
        
        if sum(visited) < N:
            ans += 1
        
        adjacency_mat[a][b] = 1
        adjacency_mat[b][a] = 1
    print(ans)

Solution (Python):
def dfs(v):
    global adjacency_mat, visited
    st = [] 
    st.append(v)
    while st:
        
        h = st.pop()
        visited[h] = True
        for i in range(N):
            
            if adjacency_mat[h][i] == None:
                continue
            
            if visited[i] == True:
                continue
            
            st.append(i)

if __name__ == "__main__":
    N, M = map(int, input().split())
    list_ab = [[] for _ in range(M)]
    adjacency_mat = [[None]* N for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        list_ab[i].append(a-1)
        list_ab[i].append(b-1)
        adjacency_mat[a-1][b-1] = 1
        adjacency_mat[b-1][a-1] = 1
        
    ans = 0
    for a, b in list_ab:
        visited = [False] * N
        
        adjacency_mat[a][b] = None
        adjacency_mat[b][a] = None
        
        dfs(0)
        
        if sum(visited) < N:
            ans += 1
        
        adjacency_mat[a][b] = 1
        adjacency_mat[b][a] = 1
    print(ans)

Solution (Python):
def search(s, m, n, bridge):
    c = [1]
    d = [1]
    for k in range(n):
        cc = []
        for i, ci in enumerate(c):
            tmp = []
            for j in range(m):
                if j == bridge:
                    continue
                elif s[j][0] == ci and s[j][1] not in d:
                    tmp.append(s[j][1])
                elif s[j][1] == ci and s[j][0] not in d:
                    tmp.append(s[j][0])
            cc += tmp
            d += tmp
        if cc == []:
            break
        else:
            c = cc
    if len(d) == n:
        return 0
    else:
        return 1

n, m = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(m)]
ans = 0
for i in range(m):
    ans += search(s, m, n, i)
print(ans)

Solution (Python):
import queue
from heapq import heappush, heappop

class Graph:

    INF = float('inf')
    
    def __init__(self,v_num,is_directed = False):
        self.is_directed = is_directed
        self.v_num = v_num
        self.E = []
        self.v_s_list = [[] for i in range(self.v_num)]
        
    def appendEdge(self,v1,v2,weight=1):
        if max(v1,v2,self.v_num-1)>=self.v_num or min(v1,v2)<0:
            print("ERROR: The vertex ID is wrong.")
            return False

        self.E.append([v1,v2,weight])
        
        if self.is_directed:
            self.v_s_list[v1].append([v2,weight])
        else:
            self.v_s_list[v1].append([v2,weight])
            self.v_s_list[v2].append([v1,weight])
        
        
    def BFS(self,v,usage="SSSP"):
        is_processed = [False for i in range(self.v_num)]
        distance_list = [Graph.INF for i in range(self.v_num)]
        Q = queue.Queue()
        Q.put(v)
        is_processed[v]=True
        distance_list[v] = 0
        while not Q.empty():
            v1 = Q.get()
            for v2 in self.v_s_list[v1]:
                if not is_processed[v2[0]]:
                    is_processed[v2[0]] = True
                    distance_list[v2[0]] = min(distance_list[v1]+1,distance_list[v2[0]])
                    Q.put(v2[0])
        if usage=="SSSP":
            return distance_list
        elif usage=="ConnectedComponent":
            cc_list = []
            for i in range(self.v_num):
                if is_processed[i]:
                    cc_list.append(i)
            return cc_list

    def getSSSPwithBFS(self,v):
        return self.BFS(v,"SSSP")
        
    def getConnectedComponent(self,v):
        return self.BFS(v,"ConnectedComponent")
        
    def getSSSPwithBellmanFord(self,v):
        distance_list = [Graph.INF for i in range(self.v_num)]
        distance_list[v] = 0
        pre_list = [None for i in range(self.v_num)]

        for i in range(self.v_num-1):
            for e in self.E:
                v1 = e[0]
                v2 = e[1]
                d = e[2]
                if distance_list[v2] > distance_list[v1] + d:
                    distance_list[v2] = distance_list[v1] + d
                    pre_list[v2] = v1
                    
        negative_loop_list = [False for i in range(self.v_num)]
        
        for i in range(self.v_num):
            for e in self.E:
                v1 = e[0]
                v2 = e[1]
                d = e[2]
                if d + distance_list[v1] < distance_list[v2]:
                    distance_list[v2] = d + distance_list[v1]
                    pre_list[v2] = v1
                    negative_loop_list[v2] = True
        
        return distance_list, pre_list, negative_loop_list

    def getSSSPwithDijkstra(self,v):
        distance_list = [Graph.INF for i in range(self.v_num)]
        distance_list[v] = 0
        pre_list = [None for i in range(self.v_num)]
        
        PQ = []
        for i in range(self.v_num):
            heappush(PQ,(distance_list[i],i))
        while len(PQ)>0:
            d,v1 = heappop(PQ)
            for v2 in self.v_s_list[v1]:
                if distance_list[v2[0]] > d + v2[1]:
                    distance_list[v2[0]] = d + v2[1]
                    pre_list[v2[0]] = v1
                    heappush(PQ,(distance_list[v2[0]],v2[0]))
        return distance_list,pre_list
    

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

graph_buf = []
for i in range(M):
    a,b = list(map(int,input().split()))
    graph_buf.append([a,b])
count=0
for i in range(M):
    G = Graph(N)
    for j in range(M):
        if i!=j:
            G.appendEdge(graph_buf[j][0]-1,graph_buf[j][1]-1)
    if len(G.getConnectedComponent(0))!=N:
        count+=1

print(count)

Solution (Python):

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

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

for ai, bi in ab:
    route[ai - 1].append(bi - 1)
    route[bi - 1].append(ai - 1)

def walk(pos, pos_prev, footprint):
    
    footprint = (2 ** pos) | footprint
    ret = footprint
    for pos_next in route[pos]:
        
        if (2 ** pos_next) & footprint > 0: continue
        ret = ret | walk(pos_next, pos, footprint)
        if ret == (2 ** N - 1): return 2 ** N - 1 
    return ret

ans = 0
for ai, bi in ab:
    
    route[ai - 1].remove(bi - 1)
    route[bi - 1].remove(ai - 1)
    
    if walk(0, -1, 0) < (2 ** N - 1): ans += 1
    
    route[ai - 1].append(bi - 1)
    route[bi - 1].append(ai - 1)

print(ans)

Solution (Python):

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

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

for ai, bi in ab:
    route[ai - 1].append(bi - 1)
    route[bi - 1].append(ai - 1)

def walk(pos, pos_prev, footprint):
    
    footprint = (2 ** pos) | footprint
    ret = footprint
    for pos_next in route[pos]:
        
        if (2 ** pos_next) & footprint > 0: continue
        ret = ret | walk(pos_next, pos, footprint)
    return ret

ans = 0
for ai, bi in ab:
    
    route[ai - 1].remove(bi - 1)
    route[bi - 1].remove(ai - 1)
    
    if walk(0, -1, 0) < (2 ** N - 1): ans += 1
    
    route[ai - 1].append(bi - 1)
    route[bi - 1].append(ai - 1)

print(ans)

Solution (Python):
def solve(N, M, ABs):
    ans = 0
    for i in range(M):
        adjMat = [[0 for _ in range(N)] for _ in range(N)]
        for k, (a, b) in enumerate(ABs):
            if k != i:
                adjMat[a - 1][b - 1] = 1
                adjMat[b - 1][a - 1] = 1

        def dps(a, visited):
            n = [i for i, b in enumerate(adjMat[a]) if b == 1]
            for nn in n:
                if nn not in visited:
                    visited.append(nn)
                    dps(nn, visited)
            return visited

        visited = dps(0, [])
        if len(visited) != N:
            ans += 1
    return ans


if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, ABs))

Solution (Python):
import copy


class Line:
    def __init__(self, a, b):
        self.a = a
        self.b = b


def can_goal(start, end, line_map, memo):
    if start == end:
        return True
    _can_goal = False
    if start in line_map:
        for next_start in line_map[start]:
            if memo[start][next_start] or memo[next_start][start]:
                continue
            memo[start][next_start] = True
            memo[next_start][start] = True
            _can_goal = can_goal(next_start, end, line_map, memo)
            if _can_goal:
                break
    return _can_goal


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

line_map = {}
memo = {}
for line in lines:
    if line.a in line_map:
        line_map[line.a].append(line.b)
        memo[line.a][line.b] = False
    else:
        line_map[line.a] = [line.b]
        memo[line.a] = {}
        memo[line.a][line.b] = False
    if line.b in line_map:
        line_map[line.b].append(line.a)
        memo[line.b][line.a] = False
    else:
        line_map[line.b] = [line.a]
        memo[line.b] = {}
        memo[line.b][line.a] = False

cnt = 0
for line in lines:
    m = copy.deepcopy(memo)
    start = line.a
    end = line.b
    m[end][start] = True
    m[start][end] = True
    if not(can_goal(start, end, line_map, m)):
        cnt += 1
print(cnt)

Solution (Python):
def dfs(v):
    visited[v]=True
    for v2 in range(n):
        if graph[v][v2]==False:
            continue
        if visited[v2]==True:
            continue
        dfs(v2)
        
n, m = map(int, input().split())

alis=[]
blis=[]
graph=[[False] * n for i in range(n)]


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

for i in range(m):
    
    graph[alis[i]][blis[i]]=False
    graph[blis[i]][alis[i]]=False
    visited=[False]*n
    dfs(0)
    bridge=False
    for j in range(n):
        if visited[j]==False:
            bridge=True
    if bridge:
        ans+=1
    graph[alis[i]][blis[i]]=True
    graph[blis[i]][alis[i]]=True

print(ans)

Solution (Python):
import sys

def 解():
    iN,iM = [int(_) for _ in input().split()]
    aAB = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]
    def addSpan(d,a,b):
        if a in d:
            d[a].add(b)
        else:
            d[a]={b}
    dT ={}
    for a,b in aAB:
        addSpan(dT,a,b)
        addSpan(dT,b,a)
    
    iC = 0
    for a,b in aAB:
        iR = 1
        for i in dT[a] - {b}:
            aSt = [i]
            vP = {a}
            while aSt:
                iP = aSt.pop()
                vP.add(iP)
                if iP == b:
                    iR = 0
                    break
                else:
                    for nP in dT[iP] - vP:
                        aSt.append(nP)
            if iR == 0:
                break
        iC += iR
    print(iC)
解()

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


n, m = [int(v) for v in input().split()]
graph = [[False] * n for i in range(n)]
a = []
b = []
for i in range(m):
    v1, v2 = [int(v) for v in input().split()]
    v1 -= 1
    v2 -= 1
    a.append(v1)
    b.append(v2)
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True

ans = 0
for i in range(m):
    graph[a[i]][b[i]] = False
    graph[b[i]][a[i]] = False

    visited = [False] * n
    dfs(0, n, graph, visited)
    if False in visited:
        ans += 1

    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True

print(ans)