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):
class LowLink:
    def __init__(self, adj):
        self.n = len(adj)
        self.adj = adj
        self.used = [0] * n
        self.ord = [0] * n
        self.low = [0] * n
        self.bridge = []
        self.articulation = []

    def dfs(self, v, order, prev):
        order += 1
        self.used[v] = 1
        self.ord[v] = order
        self.low[v] = self.ord[v]

        is_articulation = False
        cnt = 0
        for to in self.adj[v]:
            if not self.used[to]:
                cnt += 1
                order = self.dfs(to, order, v)
                self.low[v] = min(self.low[v], self.low[to])
                if prev != -1:
                    is_articulation |= self.low[to] >= self.ord[v]
                if(self.ord[v] < self.low[to]):
                    if v < to:
                        self.bridge.append((v, to))
                    else:
                        self.bridge.append((to, v))
            elif to != prev:
                self.low[v] = min(self.low[v], self.low[to])
        if prev == -1:
            is_articulation |= cnt > 1
        if is_articulation:
            self.articulation.append(v)
        return order

    def build(self):
        order = 0
        for i in range(self.n):
            if not self.used[i]:
                order = self.dfs(i, order, -1)

if __name__ == "__main__":
    n, m = [int(item) for item in input().split()]
    edge = [[] for _ in range(n)]

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

    LL = LowLink(edge)
    LL.build()
    
    
    print(len(LL.bridge))

Solution (Python):

from sys import setrecursionlimit


def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j


setrecursionlimit(10 ** 5)

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

result = 0
for i in range(M):
    parent = [-1] * N
    for j in range(M):
        if j == i:
            continue
        unite(parent, ab[j][0], ab[j][1])
    if len([i for i in parent if i < 0]) != 1:
        result += 1
print(result)

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

ans = 0
for i in range(M):
    s, t  = E[i][0], E[i][1]
    V, queue = set([s]) | T[s] - set([t]), T[s] - set([t])
    Bridge = True
    while len(queue) > 0:
        v = queue.pop()
        for u in T[v]:
            if u == t:
                Bridge = False
                break
            if u not in V:
                queue.add(u)
                V.add(u)
        else:
            continue
        break
    if Bridge:
        ans += 1

print(ans)

Solution (Python):
from collections import deque

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

def make_dict(x,y):
    for i in ll:
        if i[x] in d.keys():
            d[i[x]]+=[i[y]]
        else:
            d[i[x]]=[i[y]]

cnt=0
for i in range(m):
    ll=l[:i]+l[i+1:]
    d={}
    make_dict(0,1)
    make_dict(1,0)
    k_l=list(d.keys())
    x=0
    sk=k_l[x]
    dq=deque()
    dq.append(sk)
    seen=[]
    while dq:
        k=dq.pop()
        k_ll=d[k]
        seen.append(k)
        for i in k_ll:
            if i not in seen:
                dq.append(i)
        x+=1
    if len(set(seen))!=n:
        cnt+=1
print(cnt)

Solution (Python):
from collections import deque

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

def make_dict(x,y):
    for i in ll:
        if i[x] in d.keys():
            d[i[x]]+=[i[y]]
        else:
            d[i[x]]=[i[y]]

cnt=0
for i in range(m):
    ll=l[:i]+l[i+1:]

    d={}
    make_dict(0,1)
    make_dict(1,0)

    k_l=list(d.keys())
    v_l=list(d.values())


    x=0
    sk=k_l[x]
    dq=deque()
    dq.append(sk)



    seen=[]
    while dq:

        k=dq.pop()
        k_ll=d[k]
        seen.append(k)

        for i in k_ll:
            if i not in seen:
                dq.append(i)


        x+=1

    if len(set(seen))!=n:
        cnt+=1
print(cnt)

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

def main():
    N,M = map(int,input().split())
    a = [list(map(int,input().split())) for _ in range(M)]
    count = 0
    def bridge(X):
        go = [False for _ in range(N)]
        queue = [0]
        while queue:
            a = queue.pop()
            for i in X[a]:
                if not go[i]:
                    go[i] = True
                    queue.append(i)
        if all(go):
            return 1
        else:
            return 0
    for i in range(M):
        b = a[:i]+a[i+1:]
        road = [[] for _ in range(N)]
        for j in range(M-1):
            road[b[j][0]-1].append(b[j][1]-1)
            road[b[j][1]-1].append(b[j][0]-1)
        count += bridge(road)

    print(M-count)

if __name__ == "__main__":
    main()

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

ans = 0

for i in ab:
    vertex = list(range(N))
    for j in ab:
        if i != j:
            vertex = [vertex[j[0] - 1] if vertex[k] == vertex[j[1] - 1] else vertex[k] for k in range(N)]
    if len(set(vertex)) != 1:
        ans += 1

print(ans)

Solution (Python):

def dfs(x):
    if visited[x]:
        return
    visited[x] = True
    for i in range(N):
        
        if graph[x][i]:
            dfs(i)


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

edge = []
graph = [[False]*N for _ in range(N)]   
visited = [False]*N

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

ans = 0
for i, e in enumerate(edge):
    
    graph[e[0]-1][e[1]-1] = False
    graph[e[1]-1][e[0]-1] = False

    
    for j in range(N):
        visited[j] = False

    
    dfs(0)

    
    bridge = False
    for j in range(N):
        
        if not all(visited):
            bridge = True
    if bridge:
        ans += 1

    
    graph[e[0]-1][e[1]-1] = True
    graph[e[1]-1][e[0]-1] = True

print(ans)

Solution (Python):

def dfs(x):
    if visited[x]:
        return
    visited[x] = True
    for i in range(N):
        
        if graph[x][i]:
            dfs(i)


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

edge = []
graph = [[False]*N for _ in range(N)]   
visited = [False]*N

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

ans = 0
for i, e in enumerate(edge):
    
    graph[e[0]-1][e[1]-1] = False
    graph[e[1]-1][e[0]-1] = False

    
    for j in range(N):
        visited[j] = False

    
    dfs(0)

    
    bridge = False
    for j in range(N):
        if not visited[j]:
            bridge = True
    if bridge:
        ans += 1

    
    graph[e[0]-1][e[1]-1] = True
    graph[e[1]-1][e[0]-1] = True

print(ans)

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

answer=0

for some  in range(m):
    ans=0
    for i in range(1,n+1):
        cnt=0
        for _ in lists:
            if _[0]==i or _[1]==i:
                cnt+=1
                index=lists.index(_) 
        if cnt==1:
            ans+=1
            del lists[index]
        else:
            ans+=0
            continue
    answer+=ans
print(answer)

Solution (Python):

def dfs(x):
    if visited[x]:
        return
    visited[x] = True
    for i in range(N):
        
        if graph[x][i]:
            dfs(i)


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

edge = []
graph = [[False for _ in range(N)] for _ in range(N)]   
visited = [False for _ in range(N)]

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

ans = 0
for i, e in enumerate(edge):
    
    graph[e[0]-1][e[1]-1] = False
    graph[e[1]-1][e[0]-1] = False

    
    for j in range(N):
        visited[j] = False

    
    dfs(0)

    
    bridge = False
    for j in range(N):
        if not visited[j]:
            bridge = True
    if bridge:
        ans += 1

    
    graph[e[0]-1][e[1]-1] = True
    graph[e[1]-1][e[0]-1] = True

print(ans)

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

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

cnt = 0

from collections import deque

for i in a:
    b = a[:]
    start = i[0]
    goal = i[1]
    b.remove(i)
    q = deque()
    q.append(start)

    searched = {start}
    while q:
        current = q.popleft()
        if current == goal:
            break
        for j in b:
            if current == j[0] and j[1] not in searched:
                q.append(j[1])
                searched.add(j[1])
            elif current == j[1] and j[0] not in searched:
                q.append(j[0])
                searched.add(j[0])
    else:
        cnt += 1


print(cnt)

Solution (Python):
from collections import deque
def BFS(n, graph): 
  q = deque()
  q.append(0)
  searched = {0}
  while q:
    current = q.popleft()
    for v in graph[current]: 
      if v not in searched:
        searched.add(v)
        q.append(v)
  
  if len(searched) != n:
    return 1
  else:
    return 0
  
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
edges = []
ans = 0

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

import copy
for edge in edges:
  g = copy.deepcopy(graph) 
  
  g[edge[0]].remove(edge[1])
  g[edge[1]].remove(edge[0])
  ans += BFS(n, g) 

print(ans)

Solution (Python):
N, M = map(int, input().split())
edgelist = []
edgelistappend = edgelist.append
for i in range(M):
    edgelistappend(set(map(int, input().split())))
bridge = set()
S = set()

for e in edgelist:
    if tuple(e) not in S:
        flag = True
        E = list(e)
        start = E[0]
        goal = E[1]
        n = [start]
        R = [e]
        L = [[i for i in edgelist if (n[-1] in i) and (i not in bridge) and (i != e)]]
        while n != []:
            if n[-1] == goal:
                for x in R:
                    S.add(tuple(x))
                R.pop()
                L.pop()
                n.pop()
                flag = False
            elif L[-1] == []:
                R.pop()
                L.pop()
                n.pop()
            else:
                p = L[-1].pop()
                R.append(p)
                lp = list(p)
                if lp[0]==n[-1]:
                    n.append(lp[1])
                else:
                    n.append(lp[0])
                L.append([i for i in edgelist if (n[-1] in i) and (i not in bridge) and ((list(i)[0] not in n) or (list(i)[1] not in n))])
        if flag:
            bridge.add(tuple(e))
print(len(bridge))

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



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


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


    def is_same(self, x, y):
        if self.root(x) == self.root(y):
            return True
        else:
            return False


    def union(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2




n, m = LI()
L = LIR(m)
cnt = 0
for i in range(m):
    U = UnionFind(n)
    for j in range(m):
        if j == i:
            continue
        a, b = L[j]
        U.union(a - 1, b - 1)
    if all([U.is_same(0, k) for k in range(n)]):
        continue
    else:
        cnt += 1



print(cnt)

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


C=[[0 for _ in range(N)] for _ in range(N)]
for ab in AB:
  C[ab[0]-1][ab[1]-1]=1
  C[ab[1]-1][ab[0]-1]=1


ans=0
D=[0]*N

def dfs(n):
  if D[n]==0:
    D[n]=1
    for i in range(N):
      if C[n][i]==1:
        dfs(i)
      
for i,ab in enumerate(AB):
  C[ab[0]-1][ab[1]-1]=0
  C[ab[1]-1][ab[0]-1]=0

  if i<M-1:
    dfs(AB[i+1][0]-1)
  else:
    dfs(AB[i-1][0]-1)
  if sum(D)!=N:
    ans+=1  

  D=[0]*N
  C[ab[0]-1][ab[1]-1]=1
  C[ab[1]-1][ab[0]-1]=1
  
print(ans)

Solution (Python):
n, m = map(int, input().split())
dic = {}
ab = []
for i in range(m):
  a, b = map(int, input().split())
  if a in dic.keys():
    dic[a] += [b]
  else:
    dic[a] = [b]
  if b in dic.keys():
    dic[b] += [a]
  else:
    dic[b] = [a]
  ab.append([a, b])
  
ans = 0
for pair in ab:
  a = pair[0]
  b = pair[1]
  dic[a] = [num for num in dic[a] if num != b]
  dic[b] = [num for num in dic[b] if num != a]

  serch_spot = [a]
  visited = []
  while len(serch_spot) != 0:
    spot = serch_spot.pop(0)
    visited.append(spot)
    Next_cands = dic[spot]
    for cand in Next_cands:
      if cand in visited:
        continue
      elif cand in serch_spot:
        continue
      else:
        serch_spot.append(cand)
  if len(visited) != n:
    ans += 1
  dic[a] += [b] 
  dic[b] += [a]

print(ans)

Solution (Python):
a, b = map(int,input().split())
l = [[0]*50 for i in range(50)]
m = [0]*50
L = []
def cal(v):
    m[v] = 1
    for i in range(a):
        if l[v][i] == 0:continue
        if m[i]==1 : continue
        cal(i)
for i in range(b):
    ta , tb = map(int,input().split())
    ta-=1
    tb-=1
    L.append([ta,tb])
    l[ta][tb]+=1
    l[tb][ta]+=1
c = 0

for x,y in L:
    l[x][y] = 0
    l[y][x] = 0
    m = [0]*50

    cal(0)

    flag = 0
    for i in range(a): 
        if m[i] == 0:flag=1
    c+=flag
    
    l[x][y] = 1
    l[y][x] = 1
print(c)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = list(range(n + 1))
        self.ranks = [0 for _ in range(n + 1)]

    def get_root(self, x):
        if self.parents[x] == x:
            return x
        self.parents[x] = self.get_root(self.parents[x])
        return self.parents[x]

    def merge(self, x, y):
        x = self.get_root(x)
        y = self.get_root(y)
        if x != y:
            if self.ranks[x] < self.ranks[y]:
                self.parents[x] = y
            else:
                self.parents[y] = x
                if self.ranks[x] == self.ranks[y]:
                    self.ranks[x] += 1


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

count = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if j == i:
            continue
        uf.merge(*ls[j])
    for i in range(n + 1):
        uf.get_root(i)
    if len(set(uf.parents[1:])) > 1:
        count += 1
print(count)

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

answer = 0
for x in edges:
    l = 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: answer += 1
print(answer)

Solution (Python):
import sys
from heapq import heappop, heappush
input = sys.stdin.readline

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

    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            rx = self.root(self.parent[x])
            self.parent[x] = rx
            return rx

    def size(self, x):
        return -self.parent[self.root(x)]
    
    def same(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        return ra == rb
    
    def merge(self, a, b):
        a = self.root(a)
        b = self.root(b)
        if a == b:
            return False
        if self.parent[a] > self.parent[b]:
            a, b = b, a
        self.parent[a] += self.parent[b]
        self.parent[b] = a
        return True

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

ans = 0
for i in range(0, M):
    uf = UnionFind(N)
    for j in range(0, M):
        if i == j:
            continue
        uf.merge(edges[j][0], edges[j][1])
    same = True
    ans = ans + (uf.same(edges[i][0], edges[i][1]) == False)


print(ans)

Solution (Python):



import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(v: int) -> None:
    seen[v] = 1  
    for u in g[v]:
        if not seen[u]:
            dfs(u)


def main():  
    global g, seen
    N, M, *E = map(int, open(0).read().split())
    G = [[] for _ in range(N + 1)]
    for v, u in zip(*[iter(E)] * 2):
        G[v].append(u), G[u].append(v)
    bridges = 0
    for v, u in zip(*[iter(E)] * 2):
        g = [v.copy() for v in G]  
        g[v].remove(u), g[u].remove(v)
        seen = [0] * (N + 1)
        dfs(1)  
        bridges += 1 if 0 in seen[1:] else 0
    print(bridges)


if __name__ == "__main__":
    main()

Solution (Python):



def dfs(start: int) -> None:
    seen[start] = 1  
    stack = [start]
    while stack:
        v = stack.pop()
        for u in g[v]:
            if not seen[u]:
                seen[u] = 1
                stack.append(u)


def main():  
    global g, seen
    N, M, *E = map(int, open(0).read().split())
    G = [[] for _ in range(N + 1)]
    for v, u in zip(*[iter(E)] * 2):
        G[v].append(u), G[u].append(v)
    bridges = 0
    for v, u in zip(*[iter(E)] * 2):
        g = [v.copy() for v in G]  
        g[v].remove(u), g[u].remove(v)
        seen = [0] * (N + 1)
        dfs(1)  
        bridges += 1 if 0 in seen[1:] else 0
    print(bridges)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    class Lowlink(object):
        """
        construct: O(V+E)
        """
        def __init__(self,edges,root=0):
            """
            edges: list of list of int (adjacency list)
            root: int
            """
            
            self.__n=len(edges)
            self.__edges=edges
            self.__count=0
            self.__ord=[-1]*self.__n
            self.__low=[-1]*self.__n
            self.__bridge=[]
            self.__articulation=[]
            
            self.__dfs(root,-1)

        def __dfs(self,v,p): 
            self.__ord[v]=self.__count
            self.__low[v]=self.__count
            self.__count+=1
            isArticulation=False
            count=0 
            for u in self.__edges[v]:
                if self.__ord[u]==-1: 
                    count+=1
                    self.__dfs(u,v)
                    self.__low[v]=min(self.__low[v],self.__low[u])
                    if (self.__ord[v]<self.__low[u]): self.__bridge.append([min(u,v),max(u,v)])
                    if (p!=-1 and self.__ord[v]<=self.__low[u]): isArticulation=True
                elif u!=p: 
                    self.__low[v]=min(self.__low[v],self.__low[u])
            if (p==-1 and count>=2): isArticulation=True
            if isArticulation: self.__articulation.append(v)

        @property
        def bridge(self):
            return self.__bridge

        @property
        def articulation(self):
            return self.__articulation

    
    n,m=map(int,input().split())
    edges=[[] for _ in range(n)]
    for _ in range(m):
        u,v=map(lambda x:int(x)-1,input().split())
        edges[u].append(v)
        edges[v].append(u)
    low=Lowlink(edges)
    print(len(low.bridge))

resolve()

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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


def root(x):
    if(tree[x] == x):
        return x
    tree[x] = root(tree[x])
    return tree[x]  


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


def unite(x, y):
    x = root(x)
    y = root(y)
    if(x == y):
        return
    tree[x] = y


ans = 0
for i in range(m):
    
    tree = []
    for k in range(n+1):
        tree.append(k)
    for j in range(m):
        if (i == j):
            continue
        
        unite(a[j][0], a[j][1])
    flag = True
    for j in range(1, n+1):
        for k in range(j + 1, n+1):
            if (not same(j, k)):
                flag = False
    if (not flag):
        ans += 1
print(ans)

Solution (Python):
import sys
import math
from fractions import gcd
from copy import deepcopy





def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""


 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())


 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

class Node():
    def __init__(self, ch):
        self.ch_list = [ch]
        self.visited = False

N, M = map(int, sys.stdin.readline().split())
node_list = [0] * N

edge_list =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(M)]
for edge in edge_list:
    
    edge[0] -= 1
    edge[1] -= 1
for edge in edge_list:
    a, b = edge
    if node_list[a] == 0:
        node_list[a] = Node(b)
    else:
        if b not in node_list[a].ch_list:
            node_list[a].ch_list.append(b)

    if node_list[b] == 0:
        node_list[b] = Node(a)
    else:
        if a not in node_list[b].ch_list:
            node_list[b].ch_list.append(a)

def dfs(current_idx, ch_num, n_list):
    current = n_list[current_idx]
    if current == 0:
        return ch_num
    if current.visited:
        return ch_num
    ch_num += 1
    current.visited = True
    
    for idx in current.ch_list:
        
        ch_num = dfs(idx, ch_num, n_list)
        
    return ch_num

base_num = dfs(0, 0, deepcopy(node_list))

cnt = 0
for edge in edge_list:
    nl = deepcopy(node_list)
    a, b = edge
    nl[a].ch_list.remove((b))
    nl[b].ch_list.remove((a))
    num = dfs(0, 0, nl)
    
    if num != base_num:
        cnt += 1

print(cnt)

Solution (Python):
from collections import deque
N, M = map(int, input().split())  

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



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


ans = 0

for a, b in edges:
    graph[a].remove(b)
    graph[b].remove(a)
    q = deque([0])  
    flag = [False] * N

    while len(q):
        v = q.pop()

        flag[v] = True  
        for e in graph[v]:  
            
            
            
            if flag[e]:  
                continue

            
            q.append(e)

    graph[a].append(b)
    graph[b].append(a)
    if not all(flag):
        ans += 1

print(ans)

Solution (Python):
from collections import deque
N, M = map(int, input().split())  

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



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


ans = 0

for a, b in edges:
    graph[a].remove(b)
    graph[b].remove(a)
    q = deque([0])  
    flag = [False] * N
    
    while len(q):
        v = q.pop()

        flag[v] = True  
        for e in graph[v]:  
            
            
            
            if flag[e]:  
                continue

            
            q.append(e)

    graph[a].append(b)
    graph[b].append(a)
    if not all(flag):
        ans += 1

print(ans)

Solution (Python):
n,m=map(int,input().split())
e=[list(map(int,input().split())) for _ in range(m)]
c=0
for x in e:
  l=list(range(n))
  for y in e:
    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:c+=1
print(c)

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

cnt=0
for x in e:
  l=list(range(n))
  for y in e:
    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:cnt+=1
print(cnt)

Solution (Python):
def isHashi(a,b):
    visited = {}
    visited[a] = 1
    go = G[a]
    path = []
    for i in go:
        if i != b:
            path.append(i)
    flag = 0
    while path != []:
        to = path.pop()
        visited[to] = 1
        for i in G[to]:
            if not i in visited:
                visited[i] = 1
                if i == b:
                    flag = 1
                path.append(i)
    if flag == 0:
        return 1
    else:
        return 0
        
    
N,M = map(int,input().split())

G = [[0]*(N+1) for i in range(N+1)]
E = []

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

ans = 0
for i in range(M):
    a,b = E[i]
    if isHashi(a,b) == 1:
        ans += 1
print(ans)

Solution (Python):

"""
Created on Thu Sep 12 10:38:04 2019
C - Bridge
実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 
300
 点
@author: justwah
use union find
"""

import sys
read = sys.stdin.readline

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

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

def root(x): 
    if parent[x] < 0: 
        return x
    else:
        parent[x] = root(parent[x])  
        return parent[x]
    
def merge(a, b):
    a = root(a)
    b = root(b)
    if rank[a] < rank[b]: 
        parent[a] = b
    else:
        parent[b] = a
        if rank[a] == rank[b]: 
            rank[a] +=1    
    return

score = 0

for i in range(m):
    parent = [-1]*(n+1)
    rank = [0]*(n+1)
    for j, (a, b) in enumerate(l[i:]+l[:i]): 
        a = root(a)
        b = root(b)
        if a != b:
            merge(a, b)
        else:
            if j == (len(l)-1):
                score += 1 

print(m-score)

Solution (Python):

"""
Created on Thu Sep 12 10:38:04 2019
C - Bridge
実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 
300
 点
@author: justwah
"""

import sys
read = sys.stdin.readline

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

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

def root(x): 
    if parent[x] < 0: 
        return x
    else:
        parent[x] = root(parent[x])  
        return parent[x]
    
def merge(a, b):
    a = root(a)
    b = root(b)
    if rank[a] < rank[b]: 
        parent[a] = b
    else:
        parent[b] = a
        if rank[a] == rank[b]: 
            rank[a] +=1    
    return

score = 0

for i in range(m):
    parent = [-1]*(n+1)
    rank = [0]*(n+1)
    first = l[0]
    l = l[1:]
    l.append(first)
    for i, (a, b) in enumerate(l):
        a = root(a)
        b = root(b)
        if a != b:
            merge(a, b)
        else:
            if i == (len(l)-1):
                score += 1

print(m-score)

Solution (Python):
N,M = map(int,input().split())
list_a = []
list_b = []
g = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    list_a.append(a-1)
    list_b.append(b-1)
    g[a-1][b-1] = 1
    g[b-1][a-1] = 1


def dfs(v):
    seen[v] = 1 
    ret = 1
    for v2 in range(N):
        if g[v][v2] == 1 and seen[v2] == 0:
           
            dfs(v2)
    if seen == [1] * N: 
        ret = 0

    return ret

ans = 0
for i in range(M):
    seen = [0] * N
    g[list_a[i]][list_b[i]] = 0
    g[list_b[i]][list_a[i]] = 0
    ans += dfs(0)
    g[list_a[i]][list_b[i]] = 1
    g[list_b[i]][list_a[i]] = 1
print(ans)

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

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

flg = True
count = 0
while flg:
    flg = False
    for i in range(n):
        if node_list[i].count(1) == 1:
            count += 1
            j = node_list[i].index(1)
            node_list[i][j] = 0
            node_list[j][i] = 0
            flg = True

print(count)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

def dfs(v, end):
    if visited[v]:
        return False
    visited[v] = True
    
    for e in graph[v]:
        res = dfs(e, end)
        if res:
            return True
    if v == end:
        return True
    else:
        return False
        

if __name__ == '__main__':
    N, M = map(int, input().split())
    A = [None]*M
    graph = [[] for _ in range(N)]
    
    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        A[i] = [a, b]
        graph[a].append(b)
        graph[b].append(a)
    
    
    count = 0
    for a, b in A:
        graph[a].remove(b)
        graph[b].remove(a)
        visited = [False]*N
        if not dfs(a, b):
            count += 1
        graph[a].append(b)
        graph[b].append(a)
    print(count)