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
import collections

input = sys.stdin.readline


def main():
    N, M = [int(x) for x in input().split()]
    AB = []
    V = [[] for _ in range(N + 1)]
    for _ in range(M):
        a, b = [int(x) for x in input().split()]
        AB.append([a, b])
        V[a].append(b)
        V[b].append(a)


    ans = 0
    for a, b in AB:
        visited = set()

        q = collections.deque()
        q.append(1)
        visited.add(1)

        while q:
            c = q.pop()
            for i in V[c]:
                if i in visited:
                    continue
                if (a == i and b == c) or (a == c and b == i):
                    continue
                else:
                    q.append(i)
                    visited.add(i)

        if len(visited) != N:
            ans += 1

    print(ans)









if __name__ == '__main__':
    main()

Solution (Python):
def solve(n,G):
    visited = [False] * n
    visited[0] = True
    stack = [0]
    while len(stack) != 0:
        x = stack.pop()
        visited[x] = True
        for i in G[x]:
            if visited[i] == True:
                continue
            stack.append(i)
    if not False in visited:
        return False
    return True

def main():
    n,m = map(int,input().split())
    G = [list() for i in range(n)]
    for i in range(m):
        a,b = map(int,input().split())
        a = a - 1
        b = b - 1
        G[a].append(b)
        G[b].append(a)
    ans = 0
    for i in range(n):
        for j in range(i + 1,n):
            if not j in G[i]:
                continue
            G[i].remove(j)
            G[j].remove(i)
            if solve(n,G):
                ans = ans + 1
            G[i].append(j)
            G[j].append(i)
    print(ans)
if __name__ == '__main__':
    main()

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

N, M = [int(x) for x in input().split()]
G = [[] for _ in range(N+1)]

for _ in range(M):
    a, b = [int(x) for x in input().split()]
    G[a].append(b)
    G[b].append(a)
    
ans = 0
for _ in range(M):
    for i in range(1, N + 1):
        if len(G[i]) == 1:
            tmp = G[i][0]
            G[i].remove(tmp)
            G[tmp].remove(i)
            ans += 1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
n,m = map(int,input().split())
graph = [[]for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
pre = [0]+[-1]*(n-1)
low = [10**9]*n
def dfs(now,last,pre,low,cnt,bri):
    cnt+=1
    pre[now] = cnt
    low[now] = pre[now]
    for next in graph[now]:
        
        
    
        if pre[next] == -1:
            low[now] = min(low[now],dfs(next,now,pre,low,cnt,bri))
            if low[next] == pre[next]:
                bri.append((now,next))
        else:
            if next == last:continue
            low[now] = min(low[now],low[next])
    return low[now]        
          
      
bri = []
cnt = 0
dfs(0,-1,pre,low,cnt,bri)
print(len(bri))

Solution (Python):

def bridge(G, N):
    result = set()
    label = [None]*N
    gen = 0
    cost = [0]*N
    def dfs(u, p):
        nonlocal gen
        res = 0
        for v in G[u]:
            if v == p:
                continue
            if label[v] is not None:
                if label[v] < label[u]:
                    cost[v] += 1
                    res += 1
            else:
                label[v] = gen; gen += 1
                r = dfs(v, u)
                if r == 0:
                    result.add((u, v) if u < v else (v, u))
                res += r
        res -= cost[u]
        return res
    for v in range(N):
        if not label[v]:
            label[v] = gen; gen += 1
            r = dfs(v, -1)
            assert r == 0, r
    return result

N, M = [int(i) for i in input().split()]
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = [int(i)-1 for i in input().split()]
    G[a].append(b); G[b].append(a);

print(len(bridge(G, N)))

Solution (Python):
N,M = map(int,input().split())
ab = []
for i in range(M):
    a,b = list(map(int,input().split()))
    a -= 1
    b -= 1
    ab.append([a,b])
    
def bfs(ab):
    from collections import deque
    que = deque()
    alr = [0]
    que.append(0)
    while que:
        q = que.popleft()
        for i in ab[q]:
            if i not in alr:
                alr.append(i)
                que.append(i)
    if len(alr) < N:
        return 1
    else:
        return 0

count = 0
for i in range(M):
    ab2 = [[] for k in range(N)]
    for j in range(M):
        if j != i:
            a,b = ab[j]
            ab2[a].append(b)
            ab2[b].append(a)
    count += bfs(ab2)
print(count)

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

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

def dfs(v):
   visited[v] = 1
   for k in range(n):
      if (edge[v][k] == 0):
         continue
      if (visited[k] == 1):
         continue
      dfs(k)


ans = 0
for i in range(n):
   for j in range(i+1, n):
      if (edge[i][j] == 1):
         edge[i][j] = 0
         edge[j][i] = 0
         
         visited = [0 for _ in range(n)]
         dfs(0)
         if (sum(visited) < n):
            ans += 1
         edge[i][j] = 1
         edge[j][i] = 1
print(ans)

Solution (Python):
import sys

class graph:
  def __init__(self):
    nm = input().split()
    
    self.nv = int(nm[0])
    
    self.ne = int(nm[1])
    
    self.vertices = [i for i in range(self.nv)]
    
    self.edges = [[0, 0] for i in range(self.ne)]
    
    self.accessible_edge = [[] for i in range(self.nv)]
    for i in range(self.ne):
      e = list(map(lambda x: int(x)-1, input().split()))
      self.edges[i] = e
      self.accessible_edge[e[0]].append(e[1])
      self.accessible_edge[e[1]].append(e[0])
  
  def remove_edge(self, i):
    removed_accessible_edge = [[] for i in range(self.nv)]
    for j in range(self.ne):
      if j!=i:
        e = self.edges[j]
        removed_accessible_edge[e[0]].append(e[1])
        removed_accessible_edge[e[1]].append(e[0])
    return removed_accessible_edge

  def BFS(self, mod_edge):
    visited = [False for i in range(self.nv)]
    queue = []

    
    I = 0
    
    queue.append(I)
    visited[I] = True
    while len(queue)!=0:
      
      vid = queue.pop(0)
      
      v_edges = mod_edge[vid]
      
      for e in v_edges:
        if not visited[e]:
          visited[e] = True
          queue.append(e)
    return all(visited)
    

if __name__ == "__main__":
  g = graph()
  count = 0
  g.BFS(g.accessible_edge)
  for i in range(g.ne):
    mod_edge = g.remove_edge(i)
    
    count += 1 if not g.BFS(mod_edge) else 0
  print(count)

Solution (Python):
import sys

class graph:
  def __init__(self):
    nm = input().split()
    
    self.nv = int(nm[0])
    
    self.ne = int(nm[1])
    
    self.vertices = [i for i in range(self.nv)]
    
    self.edges = [[0, 0] for i in range(self.ne)]
    
    self.accessible_edge = [[] for i in range(self.nv)]
    for i in range(self.ne):
      e = list(map(lambda x: int(x)-1, input().split()))
      self.edges[i] = e
      self.accessible_edge[e[0]].append(e[1])
      self.accessible_edge[e[1]].append(e[0])
  
  def remove_edge(self, i):
    removed_accessible_edge = [[] for i in range(self.nv)]
    for j in range(self.ne):
      if j!=i:
        e = self.edges[j]
        removed_accessible_edge[e[0]].append(e[1])
        removed_accessible_edge[e[1]].append(e[0])
    return removed_accessible_edge

  def DFS(self, mod_edge):
    visited = [False for i in range(self.nv)]
    stack  = []

    
    I = 0
    
    stack.append(I)
    visited[I] = True
    while len(stack)!=0:
      
      vid = stack.pop(0)
      
      v_edges = mod_edge[vid]
      
      for e in v_edges:
        if not visited[e]:
          visited[e] = True
          stack.append(e)
    return all(visited)
    

if __name__ == "__main__":
  g = graph()
  count = 0
  for i in range(g.ne):
    mod_edge = g.remove_edge(i)
    
    count += 1 if not g.DFS(mod_edge) else 0
  print(count)

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

ans = M
for a, b in AB:
    a -= 1
    b -= 1
    T[a].remove(b)
    T[b].remove(a)
    visited = [False] * N
    def rec(x):
        visited[x] = True
        for y in T[x]:
            if not visited[y]:
                rec(y)
    rec(0)
    ans -= all(visited)
    T[a].append(b)
    T[b].append(a)
print(ans)

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

def size0find():
    global x,n
    next=[]
    for i in range(n):
        if len(x[i])==1:
            next.append(i)
            k=x[i][0]
            x[i].remove(k)
            x[k].remove(i)
    return next

cnt=0
while True:
    y=size0find()
    l=len(y)
    if l==0:
        break
    cnt+=l
print(cnt)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, AB):
    g = defaultdict(set)
    for a, b in AB:
        g[a].add(b)
        g[b].add(a)

    def f(a, b):
        ab = set([a, b])
        stack = [a]
        done = set()
        while stack:
            u = stack.pop()
            for v in g[u]:
                if u in ab and v in ab:
                    continue
                if v not in done:
                    done.add(v)
                    stack.append(v)
        return b not in done

    c = 0
    for a, b in AB:
        if f(a, b):
            c += 1

    return c


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    print(slv(N, M, AB))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

n,m = map(int,input().split())
G = [[0]*n for _ in range(n)]
E = []
for i in range(m):
    a,b = map(int,input().split())
    a,b = a-1, b-1
    G[a][b] = 1
    G[b][a] = 1
    E.append((a,b))

ans = 0
for e in E:
    del_a, del_b = e
    
    
    G[del_a][del_b] = 0
    G[del_b][del_a] = 0
    
    que = ([0])
    visited = [False]*n
    while que:
        node = que.pop()
        if visited[node] == True:
            continue
        visited[node] = True
        for j in range(n):
            if G[node][j] == 1:
                que.append(j)
    if False in visited:
        ans += 1
    
    
    G[del_a][del_b] = 1
    G[del_b][del_a] = 1
print(ans)

Solution (Python):

N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
path=[set() for i in range(N+1)]
for a,b in AB:
    path[a].add(b)
    path[b].add(a)
path=[list(i) for i in path]

stack=[[1,[1]]]
itta=set([1])

notBridge=set()
while stack:
    ten,totyuu=stack[-1]
    
    if not path[ten]:
        stack.pop()
        continue
    miti=path[ten].pop()
    if not miti in itta:
        stack.append([miti,totyuu+[miti]])
        itta.add(miti)
    elif len(totyuu)>1 and totyuu[-2]==miti:
        pass
    else:
        flag=0
        Z=totyuu+[miti]
        
        for i in range(len(Z)-1):
            if miti==Z[i]:
                flag=1
            if flag:
                notBridge.add(Z[i]*100+Z[i+1] if Z[i]<Z[i+1] else Z[i]+Z[i+1]*100)
print(M-len(notBridge))

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

ans = 0
for i in range(M):
    graph = [[] * N for _ in range(N)]
    for k in range(M):
        if k == i:
            continue
        u = uv[k][0] - 1
        v = uv[k][1] - 1
        graph[u].append(v)
        graph[v].append(u)
    
    
    dist = [False for _ in range(N)]
    que = deque()

    
    dist[0] = True
    que.append(0)

    
    while que:
        v = que[0]
        que.popleft()
        for new_v in graph[v]:
            if dist[new_v]:
                continue
            
            dist[new_v] = True
            que.append(new_v)
    
    if False in dist:
        ans += 1

print(ans)

Solution (Python):

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

edges = [[] for i in range(N + 1)]
bridges = []

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


ans = 0

for i in range(M):
  colors = ["white"] * (N + 1)
  u = bridges[0][0]
  stack = [u]
  a, b = map(int, bridges[i])

  while stack:
    u = stack.pop()
    colors[u] = "black"

    for v in edges[u]:
      if a == u and b == v:
        continue
      if b == u and a == v:
        continue
      if colors[v] != "black":
        stack.append(v)
  
  if len(list(filter(lambda x: x == "white" ,colors))) >= 2:
    ans += 1

print(ans)

Solution (Python):

N, M = map(int, input().split())
graph = [[False for i in range(N)] for j in range(N)]
visited = [False for i in range(N)]
def dfs(v):
    visited[v] = True
    for k in range(N):
        
        if not graph[v][k]:
            continue
        
        if visited[k]:
            continue
        dfs(k)
A, B = [], []
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    A.append(a)
    B.append(b)
    
    graph[a][b] = True
    graph[b][a] = True 

ans = 0

for a, b in zip(A, B):
    graph[a][b] = False
    graph[b][a] = False
    visited = [False for i in range(N)]
    dfs(0)
    bridge = False
    for j in range(N):
        if not visited[j]:
            bridge = True
    
    if bridge:
        ans += 1
    graph[a][b] = True
    graph[b][a] = True
print(ans)

Solution (Python):

N, M = map(int, input().split())
graph = [[False for i in range(N)] for j in range(N)]
visited = [False for i in range(N)]
def dfs(v):
    visited[v] = True
    for k in range(N):
        if not graph[v][k]:
            continue
        if visited[k]:
            continue
        dfs(k)
A, B = [], []
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    A.append(a)
    B.append(b)
    graph[a][b] = True
    graph[b][a] = True 

ans = 0
for a, b in zip(A, B):
    graph[a][b] = False
    graph[b][a] = False
    visited = [False for i in range(N)]
    dfs(0)
    bridge = False
    for j in range(N):
        if not visited[j]:
            bridge = True
    if bridge:
        ans += 1
    graph[a][b] = True
    graph[b][a] = True
print(ans)

Solution (Python):
"""import sys
input = sys.stdin.readline()"""
n,m=map(int,input().split())
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

    def same(self, x, y):
        return self.find(x) == self.find(y)
ab=[]
for i in range(m):
    a,b=map(int,input().split())
    ab.append([a,b])
cnt=0
for i in range(m):
    uf=UnionFind(n+1)
    for j in range(m):
        a=ab[j][0]
        b=ab[j][1]
        if i==j:continue
        uf.union(a,b)
    if not uf.same(ab[i][0],ab[i][1]):
        cnt+=1
print(cnt)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
from heapq import heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist

N, M = MAP()
ab = [LIST() for _ in range(M)]

graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append((b-1, 1))
	graph[b-1].append((a-1, 1))

ans = 0
for a, b in ab:
	E = deepcopy(graph)
	E[a-1].remove((b-1, 1))
	d = dijkstra(E, a-1)
	if d[b-1] == INF:
		ans += 1
print(ans)

Solution (Python):
import queue

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

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

def jdg(a,b,ans):
    li[a][b] = 0
    li[b][a] = 0

    srch = [0 for i in range(n)]
    q = queue.Queue()
    q.put(0)
    while(not q.empty()):
        memo = q.get()
        if srch[memo]==1:
            continue

        for i in range(n):
            if li[memo][i]==1:
                q.put(i)
        srch[memo] = 1

    
    if 0 in srch:
        ans += 1
    
    li[a][b] = 1
    li[b][a] = 1

    return ans

ans = 0
for i in range(len(edge)):
    ans = jdg(edge[i][0],edge[i][1],ans)
    

print(ans)

Solution (Python):

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

ans = 0

def dfs(x):
    visited[x] = True
    for i in range(len(graph[x])):
        if visited[graph[x][i]]:
            continue
        else:
            dfs(graph[x][i])

for i in range(M):
    visited = [False for k in range(N + 1)]
    visited[0] = True
    graph = [[] for k in range(N + 1)]
    for j in range(M):
        if j != i:
            graph[ab[j][0]].append(ab[j][1])
            graph[ab[j][1]].append(ab[j][0])
    dfs(1)

    for j in range(N + 1):
        if visited[j]:
            continue
        else:
            ans += 1
            break

print(ans)

Solution (Python):


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

ans=0

def dfs(x):
    flg[x]=True
    for i in range(len(G[x])):
        
        if flg[G[x][i]]:
            continue
        else:
            dfs(G[x][i])

for i in range(M):
    flg=[False for k in range(N+1)]
    flg[0]=True
    G=[[] for k in range(N+1)]
    for j in range(M):
        if j!=i:
            G[ab[j][0]].append(ab[j][1])
            G[ab[j][1]].append(ab[j][0])
    dfs(1)
    
    for j in range(N+1):
        if flg[j]:
            continue
        else:
            ans+=1
            break

print(ans)

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

def search(remove_edge):
    Q = [(-1,0)]
    visited = [False for j in range(N)]
    visited[0] = True
    while Q:
        a,b = Q.pop()
        for e in edges[b]:
            if remove_edge[0] == b and remove_edge[1] == e:
                pass
            elif remove_edge[1] == b and remove_edge[0] == e:
                pass
            elif e == a:
                pass
            elif visited[e]:
                pass
            else:
                visited[e] = True
                Q.append((b,e))
    if False in visited:
        return True
    else:
        return False

ans = 0
for e in edges_2:
    if search(e):
        ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
edges = [[] for i in range(n)]
check = [[]]
for _ in range(m):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    check.append([[a-1, b-1], [b-1, a-1]])



def dfs(start, edges, exception):
    seen = [False] * n
    seen[start] = True
    todo = []
    for to in edges[start]:
        if [start, to] in exception:
            continue
        todo.append(to)

    while todo:
        node = todo.pop()
        if seen[node]:
            continue

        seen[node] = True
        for to in edges[node]:
            if [node, to] in exception:
                continue
            todo.append(to)

    if sum(seen) == n:
        return False
    else:
        return True


ans = 0
for exception in check:
    ans += dfs(0, edges, exception)

print(ans)

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


def dfs(G,v):
    seen[v] = True
    
    for nv in G[v]:
        
        if seen[nv]:
            continue
        dfs(G,nv)

ans = 0
for edge in edges:
    seen = [False] * N
    copied_graph = copy.deepcopy(graph)
    copied_graph[edge[0]].remove(edge[1])
    copied_graph[edge[1]].remove(edge[0])
    dfs(copied_graph,0)
    if not all(seen):
        ans += 1

print(ans)

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

def dfs(A,n):
    for a in A[n]:
        if visited[a-1] == -1:
            visited[a-1] = 1
            dfs(A,a-1)
    if -1 in visited:
        return True
    else:
        return False

ans = 0 
for i in range(M):
    A = [[] for _ in range(N)]
    edges_new = edges[:i] + edges[i+1:]
    for a,b in edges_new:
        A[a-1].append(b)
        A[b-1].append(a)
    visited = [-1]*N
    visited[0] = 1
    if dfs(A,0):
        ans += 1
print(ans)

Solution (Python):
class UnionFind():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        
        self.parent = [n for n in range(0, N)]
        
        self.depth = [1] * N
 
    def find(self, x):
        """ 木の根(どのグループか)を求める """
        if self.parent[x] == x: return x
        self.parent[x] = self.find(self.parent[x]) 
        return self.parent[x]
 
    def unite(self, x, y):
        """ xとyの属する集合を併合する """
        gx = self.find(x)
        gy = self.find(y)
        if gx == gy: return
 
        
        if self.depth[gx] < self.depth[gy]:
            self.parent[gx] = gy
        else:
            self.parent[gy] = gx
            if self.depth[gx] == self.depth[gy]: self.depth[gx] += 1
 
    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find(x) == self.find(y)
      
N, M = list(map(int, input().split()))
E = [[int(x)-1 for x in input().split()] for _ in range(M)]


ans = 0
for i in range(M):
  uf = UnionFind(N)
  for j, e in enumerate(E):
    if i==j: continue
        
    a, b = e
    uf.unite(a, b)
      
  
  
  a, b = E[i]
  if not uf.is_same_group(a, b):
    ans += 1

print(ans)

Solution (Python):



import numpy as np
from scipy.sparse.csgraph import dijkstra

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

graph = np.zeros((N+1, N+1))

for a, b in edge:
  graph[a, b] = 1
  
ans = 0
for a, b in edge:
  graph[a, b] = np.inf 
  
  dist = dijkstra(graph, indices=a, directed=False)
  if dist[b] == np.inf:
    ans += 1
  graph[a, b] = 1 
  
print(ans)

Solution (Python):





import sys
sys.setrecursionlimit(2**16 - 1)
from collections import defaultdict

INF = 10**9
N, M = list(map(int, input().split()))
G = defaultdict(list)
for _ in range(M):
    a, b = list(map(int, input().split()))
    G[a].append(b)
    G[b].append(a)



prenum = defaultdict(lambda: None)
parent = defaultdict(lambda: None)
lowest = defaultdict(lambda: None)
timer = 0  
is_visited = defaultdict(lambda: False)  
root = 0




def dfs(cur, prev):  
    
    global timer
    prenum[cur] = lowest[cur] = timer  
    timer += 1
    parent[cur] = prev
    is_visited[cur] = True

    
    for nx in G[cur]:  
        if (not is_visited[nx]):
            dfs(nx, cur)
            lowest[cur] = min(lowest[cur], lowest[nx]
                              )  
        elif nx != prev:  
            
            lowest[cur] = min(lowest[cur], prenum[nx])


dfs(1, None)



ans = 0
for u, p in parent.items():
    if p is None:
        continue
    if prenum[p] < lowest[u]:
        ans += 1
print(ans)

Solution (Python):





import sys
sys.setrecursionlimit(2**16 - 1)
from collections import defaultdict

INF = 10**9
N, M = list(map(int, input().split()))
G = defaultdict(list)
for _ in range(M):
    a, b = list(map(int, input().split()))
    G[a].append(b)
    G[b].append(a)



prenum = defaultdict(lambda: None)
parent = defaultdict(lambda: None)
lowest = defaultdict(lambda: None)
timer = 0  
is_visited = defaultdict(lambda: False)  
root = 0




def dfs(cur, prev):  
    
    global timer
    prenum[cur] = lowest[cur] = timer  
    timer += 1
    parent[cur] = prev
    is_visited[cur] = True

    
    for nx in G[cur]:  
        if (not is_visited[nx]):
            dfs(nx, cur)
            lowest[cur] = min(lowest[cur], lowest[nx]
                              )  
        elif nx != prev:  
            
            lowest[cur] = min(lowest[cur], prenum[nx])


dfs(1, None)



ans = 0
for u, p in parent.items():
    if p is None:
        continue
    if prenum[p] < lowest[u]:
        ans += 1
print(ans)

Solution (Python):


import copy
import itertools


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



graph_list = [[] for i in range(N)]
a_b_list = []

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


def dfs(i, current, graph_list, visited):

    for j in graph_list[current]:
        if visited[j] == False:
            
            visited[j] = True
            
            dfs(i + 1, j, graph_list, visited)

    
    if all(visited):
        return True
    else:
        return False



count_bridge = 0

for m in range(M):
    graph_list_tmp = copy.deepcopy(graph_list)

    a = a_b_list[m][0]
    b = a_b_list[m][1]

    graph_list_tmp[a].pop(graph_list_tmp[a].index(b))
    graph_list_tmp[b].pop(graph_list_tmp[b].index(a))

    
    visited = [False] * N
    visited[0] = True
    
    is_visited_all = False
    result = dfs(0, 0, graph_list_tmp, visited)

    if result != True:
        count_bridge += 1

print(count_bridge)

Solution (Python):
from collections import deque

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

vertex = [[] for i in range(N)]
for side in sides:
    vertex[side[0]-1].append(side[1])
    vertex[side[1]-1].append(side[0])



ans = 0

for side in sides:
    vertex[side[0]-1].remove(side[1])
    vertex[side[1]-1].remove(side[0])
    
    for i in range(1,N+1):
        a = 1
        check = deque([i])
        fromcheck = {j:0 for j in range(1,N+1)}
        visit = {i}
        while len(check) != 0:
            v = check.popleft()
            for ver in vertex[v-1]:
                if fromcheck[ver] == 0:
                    fromcheck[ver] = 1
                    check.append(ver)
                    visit.add(ver)
            fromcheck[v] = 1
        if visit != {i for i in range(1,N+1)}:
            a = 0
            break
    if a == 0:
        ans += 1
    vertex[side[0]-1].append(side[1])
    vertex[side[1]-1].append(side[0])

print(ans)

Solution (Python):
from collections import deque

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

vertex = [[] for i in range(N)]
for side in sides:
    vertex[side[0]-1].append(side[1])
    vertex[side[1]-1].append(side[0])



ans = 0

for side in sides:
    vertex[side[0]-1].remove(side[1])
    vertex[side[1]-1].remove(side[0])
    
    for i in range(1,N+1):
        a = 1
        check = deque([i])
        fromcheck = {j:0 for j in range(1,N+1)}
        visit = {i}
        while len(check) != 0:
            v = check.popleft()
            for ver in vertex[v-1]:
                if fromcheck[ver] == 0:
                    fromcheck[ver] = 1
                    check.append(ver)
                    visit.add(ver)
            fromcheck[v] = 1
        if visit != {i for i in range(1,N+1)}:
            a = 0
            break
    if a == 1:
        ans += 1
    vertex[side[0]-1].append(side[1])
    vertex[side[1]-1].append(side[0])

print(M-ans)