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

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


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)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    N, M = map(int, readline().split())
    edge = list(list(map(int, readline().split())) for _ in range(M))
    bridge = 0
    for i in range(M):
        uf = UnionFind(N)
        for j in range(M):
            if i==j:
                continue
            else:
                uf.union(edge[j][0]-1, edge[j][1]-1)
        if uf.group_count()>1:
            bridge += 1
    print(bridge)



if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.height = [0]*n

    def get_root(self, i):
        if self.parent[i] == i:
            return i
        else:
            self.parent[i] = self.get_root(self.parent[i])
            return self.parent[i]
        
    def unite(self, i, j):
        root_i = self.get_root(i)
        root_j = self.get_root(j)
        if root_i != root_j:
            if self.height[root_i] < self.height[root_j]:
                self.parent[root_i] = root_j
            else:
                self.parent[root_j] = root_i
                if self.height[root_i] == self.height[root_j]:
                    self.height[root_i] += 1
    
    def is_in_group(self, i, j):
        if self.get_root(i) == self.get_root(j):
            return True
        else:
            return False



def main():
    import sys

    def input(): return sys.stdin.readline().rstrip()

    n, m = map(int, input().split())
    edges = []
    for i in range(m):
        a, b = map(int, input().split())
        edges.append((a-1, b-1))
    
    cnt = 0
    for i in range(m):
        uf = UnionFind(n)
        for j in range(m):
            if i == j: continue
            a, b = edges[j]
            uf.unite(a, b)
        flag = 1
        for j in range(n):
            flag &= uf.is_in_group(0, j)
        if not flag: 
            cnt += 1
    print(cnt)
            
                
if __name__ == '__main__':
    main()

Solution (Python):
class Graph:
    
    def __init__(self,vertex=[]):
        self.vertex=list(vertex)
        self.edge_number=0
        self.adjacent={v:set() for v in vertex}
    
    
    def add_vertex(self,*adder):
        k=len(self.vertex)
        m=0
        
        for u in adder:
            if u not in self.adjacent:
                self.adjacent[u]=set()
                self.vertex.append(u)

    
    def add_edge(self,From,To):
        for w in [From,To]:
            if w not in self.adjacent:
                self.add_vertex(w)
        
        if To not in self.adjacent[From]:
            self.adjacent[From].add(To)
            self.adjacent[To].add(From)
            self.edge_number+=1

    
    def remove_edge(self,u,v):
        for w in [u,v]:
            if w not in self.adjacent:
                self.add_vertex(w)

        if u in self.adjacent[v]:
            self.adjacent[u].remove(v)
            self.adjacent[v].remove(u)
            self.edge_number-=1

    
    def remove_vertex(self,*v):
        for w in v:
            if w in self.adjacent:
                self.edge_number-=len(self.adjacent[w])
                for u in self.adjacent[w]:
                    self.adjacent[u].remove(w)
                del self.adjacent[w]
            

    
    def add_walk(self,*walk):
        n=len(walk)
        for i in range(n-1):
            self.add_edge(walk[i],walk[i+1])

    
    def add_cycle(self,*cycle):
        self.add_walk(*cycle)
        self.add_edge(cycle[-1],cycle[0])
        
    
    def __vertex_swap(self,p,q):
        self.vertex.sort()
            
    
    def vertex_exist(self,v):
        return v in self.adjacent

    
    def edge_exist(self,u,v):
        if not(self.vertex_exist(u) and self.vertex_exist(v)):
            return False
        return u in self.adjacent[v]

    
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent[v])

    
    def vertex_count(self):
        return len(self.vertex)

    
    def edge_count(self):
        return self.edge_number
    
    
    def connected_component(self,v):
        if v not in self.adjacent:
            return []

        from collections import deque
        T={u:False for u in self.adjacent}
        T[v]=True
        S=deque([v])

        while S:
            u=S.popleft()
            for w in self.adjacent[u]:
                if not T[w]:
                    T[w]=True
                    S.append(w)

        return [x for x in self.adjacent if T[x]]

    
    def distance(self,u,v):
        from collections import deque
        inf=float("inf")
        T={v:inf  for v in G.vertex}

        if u==v:
            return 0
        
        Q=deque([u])
        T[u]=0
        while Q:
            w=Q.popleft()
            for x in G.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)
                    if x==v:
                        return T[x]
        return inf

    
    def shortest_path(self,u,v):
        from collections import deque
        inf=float("inf")
        T={v:[] for v in G.vertex}

        if u==v:
            return 0
        
        Q=deque([u])
        T[u]=[u]
        while Q:
            w=Q.popleft()
            for x in G.adjacent[w]:
                if not T[x]:
                    T[x]=T[w]+[x]
                    Q.append(x)
                    if x==v:
                        return T[x]
        return None


def Connected_Component_Number(G):
    T={v:False for v in G.vertex}
    C=0
    for v in G.vertex:
        if not T[v]:
            X=G.connected_component(v)
            for x in X:
                T[x]=True
            C+=1
    return C

N,M=map(int,input().split())
G=Graph(list(range(1,N+1)))
E=[]
for _ in range(M):
    a,b=map(int,input().split())
    G.add_edge(a,b)
    E.append((a,b))

K=Connected_Component_Number(G)
X=0
for a,b in E:
    G.remove_edge(a,b)
    if Connected_Component_Number(G)!=K:
        X+=1
    G.add_edge(a,b)
print(X)

Solution (Python):
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.ranks=[0]*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.ranks[x]<self.ranks[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
        if self.ranks[x]==self.ranks[y]:
            self.ranks[x]+=1
    
    def number_of_class(self):
        return sum(x<0 for x in self.parents)
    
    def clear(self):
        self.parents=[-1]*n

n,m=map(int,input().split())
edge=[tuple(map(lambda x:int(x)-1,input().split())) for _ in range(m)]
g=Unionfind(n)
ans=0
for e in edge:
    g.clear()
    for f in edge:
        if f!=e:
            g.union(f[0],f[1])
    if g.number_of_class()>1:
        ans+=1
print(ans)

Solution (Python):
import sys

read=sys.stdin.read

n,m=map(int,input().split())
edge=[tuple(map(int,lst.split())) for lst in read().splitlines()]


def isconn(v,e0):
  clst=[1]*(n+1)
  clst[v]=0
  for _ in range(n):
    for e in edge:
      if e!=e0:
        tmp=clst[e[1]]&clst[e[0]]
        clst[e[1]]=tmp
        clst[e[0]]=tmp
  if sum(clst)>1:
    return False
  else:
    return True
ans=0
for e in edge:
  if not isconn(1,e):
    ans+=1
print(ans)

Solution (Python):
from collections import deque
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
data = []
for i in range(m):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
    data.append([a - 1, b - 1])

ans = 0

def dfs(queue, a, b):
    while len(queue) != 0:
        x = queue.popleft()
        for i in range(len(graph[x])):
            if (min(graph[x][i], x) != a or max(x, graph[x][i]) != b) and visited[graph[x][i]] == 0:
                queue.append(graph[x][i])
                visited[graph[x][i]] = 1

for i in range(m):
    visited = [0] * n
    visited[0] = 1
    queue = deque()
    queue.append(0)
    dfs(queue, data[i][0], data[i][1])
    if sum(visited) != n:
        ans += 1

print(ans)

Solution (Python):
from collections import deque
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
data = []
for i in range(m):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
    data.append([a - 1, b - 1])

ans = 0

def dfs(queue, a, b):
    while len(queue) != 0:
        x = queue.popleft()
        for i in range(len(graph[x])):
            if (min(graph[x][i], x) != a or max(x, graph[x][i]) != b) and visited[graph[x][i]] == 0:
                queue.append(graph[x][i])
                visited[graph[x][i]] = 1

for i in range(m):
    visited = [0] * n
    visited[0] = 1
    queue = deque()
    queue.append(0)
    dfs(queue, data[i][0], data[i][1])
    if sum(visited) != n:
        ans += 1

print(ans)

Solution (Python):
def dfs(cur):
    visited[cur] = 1
    for nx in range(n):
        if G[cur][nx] == 0:
            continue
        if visited[nx]:
            continue
        dfs(nx)


n, m = map(int, input().split())
G = [[0]*n for _ in range(n)]
ab = []
for i in range(m):
    a, b = map(int, input().split())
    ab.append((a-1, b-1))
    G[a-1][b-1] = G[b-1][a-1] = 1
ans = 0
for a, b in ab:
    G[a][b] = G[b][a] = 0
    visited = [0]*n
    dfs(0)
    if not all(visited):
        ans += 1
    G[a][b] = G[b][a] = 1

print(ans)

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


def main():
    n, m = map(int, input().split())
    edges = [[] for _ in range(n)]
    exceptions = []
    for _ in range(m):
        a, b = map(int, input().split())
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)
        exceptions.append((a-1, b-1))

    ans = 0
    for from_, to in exceptions:
        res = dfs(n, edges, exception={(from_, to), (to, from_)})
        if not res:
            ans += 1
    print(ans)


def dfs(nodes, edges, exception):
    seen = [False] * nodes
    todo = [0]
    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)

    return sum(seen) == nodes


if __name__ == "__main__":
    main()

Solution (Python):

from collections import defaultdict

def dfs(x):
  if f[x] == 1: return
  f[x]=1
  for nex in dd[x]:
    if x==a and nex==b: continue
    dfs(nex)

n,m=map(int,input().split())
dd=defaultdict(list)
lst=[]
ans=0
for i in range(m):
  a,b=map(int,input().split())
  lst.append((a,b,))
  dd[a].append(b)
  dd[b].append(a)
for a,b in lst:
  f=[0]*(n+1)
  dfs(a)
  if f[b]!=1:
    ans+=1
print(ans)

Solution (Python):


from collections import defaultdict

def remove_checked():
  global check_nodes,dd
  for n in check_nodes:
    if n in dd:
      dd.pop(n)
    for k in dd:
      if n in dd[k]:
        dd[k].remove(n)
  check_nodes=set()        

n,m=map(int,input().split())
dd=defaultdict(list)
check_nodes=set()
for i in range(m):
  a,b=map(int,input().split())
  dd[a].append(b)
  dd[b].append(a)

cnt=0
while True:
  for k in dd.keys():
    if k in check_nodes:
      continue
    nodes=dd[k]
    if len(nodes) == 1:
      nxt=k
      while len(nodes) <= 2:
        check_nodes.add(nxt)
        cnt+=1
        nxt=nodes[0]
        if nxt in check_nodes:
            nxt = nodes[1]
        nodes=dd[nxt]
        if len(nodes) == 1:
          check_nodes.add(nxt)
          break
  if check_nodes==set():
    break
  remove_checked()

print(cnt)

Solution (Python):
f=lambda:map(int,input().split())
n,m=f()
d=[[]for _ in range(n+1)]
c=[]
for _ in range(m):
    a,b=f()
    d[a]+=[b]
    d[b]+=[a]
    c+=[[a,b]]
ans=0
for i,j in c:
    a=[0]*(n+1)
    b=list(d[i])
    b.remove(j)
    now=0
    while b:
        now=b.pop(0)
        if a[now]==0:
            a[now]+=1
            for k in d[now]:
                if a[k]==0 and k!=i:
                    b+=[k]
    if a[j]==0:
        ans+=1
print(ans)

Solution (Python):


from pprint import pprint
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


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

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








def root(v):
    if parents[v] == v:
        return v
    parents[v] = root(parents[v])
    return parents[v]


def unite(u, v):
    u_root = root(u)
    v_root = root(v)
    if u_root == v_root:
        return
    parents[u_root] = v_root


def same(u, v):
    return root(u) == root(v)


ans = 0
for e_i in edges:
    parents = [i for i in range(N)]
    for e_j in edges:
        if e_i == e_j:
            continue
        u, v = e_j
        if not same(u, v):
            unite(u, v)
    count = 0
    for v in range(N):
        if parents[v] == v:
            count += 1
    if count > 1:
        ans += 1

print(ans)

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    
    
    def lowlink(adj, root=1):
        N = len(adj) - 1
        order = [N + 1] * (N + 1)
        low = [N + 1] * (N + 1)
        AP = []
        bridge = []

        st = [root]
        cnt = 1
        par = [0] * (N + 1)
        seq = []
        while st:
            v = st.pop()
            if order[v] != N+1:
                continue
            order[v] = cnt
            seq.append(v)
            low[v] = cnt
            cnt += 1
            for u in adj[v]:
                if order[u] < cnt:
                    if par[v] != u:
                        low[v] = min(low[v], order[u])
                        continue
                else:
                    par[u] = v
                    st.append(u)

        child = [[] for _ in range(N + 1)]
        for v in range(1, N + 1):
            child[par[v]].append(v)

        seq.reverse()
        for v in seq:
            for u in child[v]:
                low[v] = min(low[v], low[u])

        
        for p in range(1, N+1):
            for c in child[p]:
                if order[p] < low[c]:
                    bridge.append((p, c))

        
        for v in range(1, N + 1):
            if v == root:
                if len(child[v]) > 1:
                    AP.append(v)
            else:
                for c in child[v]:
                    if order[v] <= low[c]:
                        AP.append(v)
                        break

        return AP, bridge

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

    AP, bridge = lowlink(adj)
    print(len(bridge))


if __name__ == '__main__':
    main()

Solution (Python):


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

    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return 
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

N, M = map(int,input().split())
glaph = []
for i in range(M):
    A, B = map(int,input().split())
    glaph.append((A,B))

cnt = 0
for i in range(M):
    unionfind = UnionFind(N)
    for j,v in enumerate(glaph):
        x,y = v
        if i==j:
            continue
        unionfind.Unite(x,y)
    if unionfind.Count(1) < N:
        cnt += 1
print(cnt)

Solution (Python):
def main():
  from collections import deque
  n,m=map(int,input().split())
  g=[[] for _ in range(n)]
  for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1;
    g[a].append((b,i))
    g[b].append((a,i))
  
  bfs=deque([])
  def check(j):
    res=1
    used=[False]*n
    used[0]=True
    bfs.append(0)
    while bfs:
      cur=bfs.popleft()
      for to,num in g[cur]:
        if num!=j and not used[to]:
          used[to]=True
          res+=1
          bfs.append(to)
    return res!=n
  
  ans=0
  for i in range(m):
    if check(i):
      ans+=1
  
  print(ans)
  
if __name__=='__main__':
  main()

Solution (Python):



def root(a):
    if parent[a] == -1:
        return a
    parent[a] = root(parent[a])
    return parent[a]


def unite(x, y):
    if same(x, y):
        return False

    x = root(x)
    y = root(y)
    parent[x] = y
    return True


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


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

result = 0
for i in range(m):
    parent = [-1 for _ in range(n)]
    for j in range(m):
        if j == i:
            continue
        a, b = edge[j]
        unite(a, b)
    a, b = edge[i]
    if not same(a, b):
        result += 1

print(result)

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

for i in range(M):
    AB.append(list(map(int,input().split())))


out = 0
for remove in range(M):
    G = [[] for i in range(N)]
    for i in range(M):
        if i==remove:
            continue
        else:
            A,B=AB[i]
            G[A-1].append(B-1)
            G[B-1].append(A-1)
    s = 0
    visit = [0]*N
    que = deque([s])
    visit[s] = 1
    while que:
        v = que.popleft()
        for w in G[v]:
            if visit[w] == 1:
                continue
            visit[w] =  1
            que.append(w)
    if sum(visit)!=N:
        out+=1
print(out)

Solution (Python):
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)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int, input().split())
AB = [list(map(lambda x: int(x)-1, input().split())) for _ in range(M)]

ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        a, b = AB[j][0], AB[j][1]
        if i == j:
            continue
        uf.union(a, b)
    if uf.group_count() > 1:
        ans += 1
print(ans)

Solution (Python):
def dfs(f):
    if vis[f] == 1:
        return
    vis[f] = 1 
    for t in v[f]: 
        if f != a or t != b: 
            dfs(t)

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

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

ans = 0

for a, b in e:
    vis = [0]*n
    dfs(a)
    if vis[b] == 0: 
        ans += 1

print(ans)

Solution (Python):


from collections import defaultdict

N, M = map(int, input().split())
par = [-1] * N
G = defaultdict(list)


class UnionFind(object):
    def __init__(self, n):
        self.par = [-1] * n
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return False
        else:
            if self.par[x] > self.par[y]:
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x
            return True

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

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


edges = []
ufG = UnionFind(N)
for _ in range(M):
    ai, bi = map(int, input().split())
    ai, bi = ai - 1, bi - 1
    edges.append((ai, bi))
    G[ai].append(bi)
    G[bi].append(ai)
    ufG.unite(ai, bi)


count = 0
for m in range(M):
    ufGm = UnionFind(N)
    for k in range(M):
        if k == m:
            continue
        ai, bi = edges[k]
        ufGm.unite(ai, bi)

    flag = False
    for k in range(N):
        if ufGm.size(k) != ufG.size(k):
            flag = True
            break
    if flag:
        count += 1
print(count)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()

class UnionFind():
    """
    https://note.nkmk.me/python-union-find/
    DFSの上位互換と考えて良い
    ２要素x, yがpath-connectedかどうかをlogオーダーで判定する（螺旋本の14.1節参照）
    さらに連結成分の要素数がO(1)で取得可能なように改造してある
    """
    def __init__(self, n):
        """
        要素数をnとして、各ノードを0,1,...,(n-1)の番号で管理する
        parentsは各ノードの属する木の根を表す
        ただし根ノードのparentには(その木のノード数)*(-1)を格納する
        """
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """
        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, yのそれぞれ属する木Tx, Tyの根同士を繋ぐ
        このとき木の要素数が小さい方を大きい方に繋ぐ（rankではなくsizeを用いる）
        """
        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):
        """
        xの属する木の要素数を返す
        根の親を要素数の(-1)倍で定めておいたおかげでO(1)で取得可能
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """
        xとyがpath-connectedかを判定する
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """
        xの属する木の要素を列挙する
        """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """
        連結成分の代表元のリストを返す
        """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """
        連結成分の個数を返す
        """
        return len(self.roots())

    def all_group_members(self):
         """
         連結成分およびそれぞれの代表元をまとめた辞書を返す
         代表元がキーになってる
         """
         return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        """
        連結成分およびその代表元を出力
        """
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
 


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

    bridge = 0
    for i in range(M):
        tree = UnionFind(N)
        for j in range(M):
            if j == i: continue
            tree.union(edge[j][0], edge[j][1])
        if tree.group_count() != 1:
            bridge += 1
    print(bridge)

if __name__ == "__main__":
    main()

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


visited = [False] * (n+1)
parents = [None] * (n+1)
cycles = set()
count = 0
def dfs(u):
    for v in range(n+1):
        if adj[u][v]:
            if parents[u] == v:
                continue
            
            
            adj[u][v], adj[v][u] = 0, 0
            if parents[v] is not None:
                
                cycles.add(u)
                cycles.add(v)
                w = parents[u]
                while w != v:
                    cycles.add(w)
                    w = parents[w]
                
            if parents[v] == None: 
                parents[v] = u
                dfs(v)
parents[1] = 0
dfs(1)
ans = m

for i in range(m):
    a, b = edges[i]
    if a in cycles and b in cycles:
        ans -= 1
print (ans)

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

visit=[0 for i in range(n)]
side=[[False for i in range(n)] for j in range(n)]

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

def bfs(x,y):
    que=[0]
    visit=[0 for i in range(n)]
    done=[[0 for i in range(n)] for j in range(n)]
    visit[0]=1
    while(que):
        now=que.pop(0)
    
        for i in l[now]:
            if ((now==x and i==y) or (now==y and i==x)) or (done[now][i]==True or done[i][now]==True):
                continue
            else:
                que.append(i)
                done[now][i]=True
                visit[now]+=1
                visit[i]+=1

    flag=0

    for i in visit:
        if i!=0:
            continue                  
        else:
            flag=1
            break

    if flag==1:
        return 1
    else:
        return 0

ans=0
for i in range(n):
    for j in range(i+1,n):
        if side[i][j]==True:
            ans+=bfs(i,j)

print(ans)

Solution (Python):
from collections import deque

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

ans = 0
for i, j in e:
    used = {}
    q = deque([0])
    while q:
        u = q.popleft()
        for v in g[u]:
            if (v in used) or (i == u and j == v) or (i == v and j == u):
                continue
            else:
                q.append(v)
                used[v] = True
    if len(used) < N:
        ans += 1
print(ans)

Solution (Python):


from collections import deque

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



G=[[] for _ in range(n)]
for i in range(m):
    a,b=edge[i]
    G[a].append(b)
    G[b].append(a)

base=0
dist=[0]*n
for i in range(n):
    if dist[i]==0:
        base+=1
        
        dist[i]=1
        s=deque()
        s.append(i)
        while s:
            now=s.pop()
            for next in G[now]:
                if dist[next]>0:
                    continue
                s.append(next)
                dist[next]=1


ans=0

for i in range(m):
    
    G=[[] for _ in range(n)]
    for j in range(m):
        if j!=i:
            a,b=edge[j]
            G[a].append(b)
            G[b].append(a)
    
    
    temp=0
    dist=[0]*n
    for j in range(n):
        
        if dist[j]==0:
            temp+=1
            
            dist[j]=1
            s=deque()
            s.append(j)
            while s:
                now=s.pop()
                for next in G[now]:
                    if dist[next]>0:
                        continue
                    s.append(next)
                    dist[next]=1
    if temp>base:
        ans+=1

print(ans)