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.



Sample input:
7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7


Sample output:
4

Submission status: Accepted

Solution code:
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)
    
    
N, M = map(int, input().split())
E = [list(map(int, input().split())) for i in range(M)]
ans = 0
for i in range(M):
    u = UnionFind(N)
    for j in range(M):
        if i != j:
            u.union(E[j][0]-1, E[j][1]-1)
    f = True
    g = u.find(0)
    for j in range(N):
        if g != u.find(j):
            f = False
            break
    if not f:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def int_(num_str):
    return int(num_str) - 1


N, M = map(int, input().split())
ablist = [list(map(int_, input().split())) for _ in range(M)]
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.group_count = 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

        self.group_count -= 1

        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 all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if i != j:
            uf.union(*ablist[j])
    if uf.group_count >= 2:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def int_(num_str):
    return int(num_str) - 1


N, M = map(int, input().split())
ablist = [list(map(int_, input().split())) for _ in range(M)]
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()}
ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if i != j:
            uf.union(*ablist[j])
    if uf.group_count() >= 2:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

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

def main():
    n, m = map(int, read().split())
    adj = [list() for _ in range(n)]
    for _ in range(m):
        a, b = map(int, read().split())
        adj[a - 1].append(b - 1)
        adj[b - 1].append(a - 1)
    loop = True
    bridge = 0
    while loop:
        loop = False
        for i, ai in enumerate(adj):
            if len(ai) == 1:
                adj[i] = []
                adj[ai[0]].remove(i)
                bridge += 1
                loop = True
    print(bridge)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class LowLink:
    def __init__(self, v):
        self.size = len(v)
        self.v = v
        self.pre = [None]*self.size
        self.low = [None]*self.size
        self.articulation = []
        self.bridge = []
        for x in range(self.size):
            if self.pre[x] is None:
                self.cnt = 0
                self.dfs(x,None)

    def dfs(self, x, par):
        self.pre[x] = self.low[x] = self.cnt
        self.cnt += 1
        is_articulation = False
        n = 0
        for y in self.v[x]:
            if self.pre[y] is None:
                n += 1
                lowy = self.dfs(y, x)
                if lowy < self.low[x]:
                    self.low[x] = lowy
                if self.pre[x] <= lowy:
                    if self.pre[x]:
                        is_articulation = True
                    if self.pre[x] < lowy:
                        self.bridge.append((x,y))
            else:
                if par != y and self.pre[y] < self.low[x]:
                    self.low[x] = self.pre[y]

        if par is None and n > 1:
            is_articulation = True

        if is_articulation:
            self.articulation.append(x)

        return self.low[x]


n,m = map(int, input().split())
v = [[] for i in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
ans = LowLink(v)
print(len(ans.bridge))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

class LowLink:
    def __init__(self, v):
        self.size = len(v)
        self.v = v
        self.pre = [None]*self.size
        self.low = [None]*self.size
        self.par = [None]*self.size
        self.articulation = []
        self.bridge = []
        for x in range(self.size):
            if self.pre[x] is None:
                self.cnt = 0
                self.pre[x] = self.low[x] = self.cnt
                self.dfs(x)

    def dfs(self, x):
        is_articulation = False
        n = 0
        for y in self.v[x]:
            if self.pre[y] is None:
                self.cnt += 1
                n += 1
                self.pre[y] = self.low[y] = self.cnt
                self.par[y] = x
                py = self.dfs(y)
                if py < self.low[x]:
                    self.low[x] = py
            else:
                if self.par[x] != y and self.pre[y] < self.low[x]:
                    self.low[x] = self.pre[y]
            if self.pre[x] <= self.low[y]:
                if self.pre[x]:
                    is_articulation = True
                if self.pre[x] < self.low[y]:
                    self.bridge.append((x,y))

        if not self.pre[x] and n > 1:
            is_articulation = True
        if is_articulation:
            self.articulation.append(x)

        return self.low[x]


def solve():
    n,m = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    ans = LowLink(v)
    print(len(ans.bridge))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

class LowLink:
    def __init__(self, v):
        self.size = len(v)
        self.v = v
        self.pre = [None]*self.size
        self.low = [None]*self.size
        self.par = [None]*self.size
        self.articulation = []
        self.bridge = []
        for x in range(self.size):
            if self.pre[x] is None:
                self.cnt = 0
                self.pre[x] = self.low[x] = self.cnt
                self.dfs(x)

    def dfs(self, x):
        is_articulation = False
        n = 0
        for y in self.v[x]:
            if self.pre[y] is None:
                self.cnt += 1
                n += 1
                self.pre[y] = self.low[y] = self.cnt
                self.par[y] = x
                py = self.dfs(y)
                if py < self.low[x]:
                    self.low[x] = py
            else:
                if self.par[x] != y and self.pre[y] < self.low[x]:
                    self.low[x] = self.pre[y]
            if self.pre[x] <= self.low[y]:
                if self.pre[x]:
                    is_articulation = True
                if self.pre[x] < self.low[y]:
                    self.bridge.append((x,y))

        if self.pre[x] == 0 and n > 1:
            is_articulation = True
        if is_articulation:
            self.articulation.append(x)
        return self.low[x]


def solve():
    n,m = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    ans = LowLink(v)
    print(len(ans.bridge))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

class LowLink:
    def __init__(self, v):
        self.size = len(v)
        self.v = v
        self.cnt = 0
        self.pre = [None]*self.size
        self.low = [None]*self.size
        self.par = [None]*self.size
        self.bridge = []
        for x in range(self.size):
            if self.pre[x] is None:
                self.pre[x] = self.low[x] = self.cnt
                self.dfs(x)

    def dfs(self, x):
        for y in self.v[x]:
            if self.pre[y] is None:
                self.cnt += 1
                self.pre[y] = self.low[y] = self.cnt
                self.par[y] = x
                py = self.dfs(y)
                if py < self.low[x]:
                    self.low[x] = py
            else:
                if self.par[x] != y and self.pre[y] < self.low[x]:
                    self.low[x] = self.pre[y]
            if self.pre[x] < self.low[y]:
                self.bridge.append((x,y))

        return self.low[x]

    def bridge(self):
        return self.bridge

def solve():
    n,m = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    ans = LowLink(v)
    print(len(ans.bridge))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007
cnt = 0
def solve():
    def lowlink(v):
        global cnt
        def dfs(x):
            global cnt
            for y in v[x]:
                if pre[y] is None:
                    cnt += 1
                    pre[y] = low[y] = cnt
                    par[y] = x
                    py = dfs(y)
                    if py < low[x]:
                        low[x] = py
                else:
                    if par[x] != y and pre[y] < low[x]:
                        low[x] = pre[y]
                if pre[x] < low[y]:
                    res.append((x,y))
            return low[x]

        pre = [None]*n
        low = [None]*n
        par = [None]*n
        res = []
        for x in range(n):
            if pre[x] is None:
                pre[x] = low[x] = cnt
                dfs(x)
        return res

    n,m = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    ans = lowlink(v)
    print(len(ans))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]
    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
    n,m = LI()
    v = LIR(m)
    for i in range(m):
        v[i][0] -= 1
        v[i][1] -= 1
    ans = 0
    for i in range(m):
        par = [i for i in range(n)]
        rank = [0]*n
        s = 1
        for j in range(m):
            if i == j:
                continue
            a,b = v[j]
            if root(a) != root(b):
                s += 1
                if s >= n:
                    break
                unite(a,b)
        else:
            ans += 1
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
graph = [[False for i in range(60)] for _ in range(60)]
A, B = [], []
ans = 0

def dfs(v):
    if vis[v]:
        return
    vis[v] = True
    for i in range(n):
        if graph[v][i]:
            dfs(i)

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

for i in range(m): #どれが橋か
    graph[A[i]][B[i]] = graph[B[i]][A[i]] = False
    vis = [False] * n
    
    dfs(0)

    f = 0
    for j in range(n):
        if not vis[j]: f = 1
    if f: ans += 1
    
    graph[A[i]][B[i]] = graph[B[i]][A[i]] = True

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
g=[[] for _  in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
def dfs(g,res):
    for i in range(n):
        if len(g[i])==1:
            g[g[i][0]].remove(i)
            g[i]=[]
            res=dfs(g,res+1)
    return res
print(dfs(g,0))

Submission status: Accepted

Solution code:
# 各辺をグラフから取り除いて、グラフが連結であるかを判定する
# DFSを使っての解法
n, m = map(int, input().split())

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

def dfs(v):
    visited[v] = True
    for v2 in range(n):
        if graph[v][v2] == False: continue
        if visited[v2] == True: continue
        dfs(v2)

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

ans = 0

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

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

    dfs(0)

    brige = False
    for j in range(n):
        if visited[j] == False: brige = True
    if brige: ans += 1

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

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()


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())
ans = 0
ab = [list(map(int, input().split())) for _ in range(M)]
for i in range(M):
    uf = UnionFind(N)
    for l in ab[:i] + ab[i + 1:]:
        uf.union(l[0] - 1, l[1] - 1)
    if uf.group_count() == 2:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
paths=[]
graph={}
for n in range(1,N+1):
    graph[n]=set()
for m in range(M):
    a,b=map(int,input().split())
    paths.append((a,b))
    graph[a].add(b)
    graph[b].add(a)

ans=0
for m in range(M):
    a,b=paths[m]
    graph[a].remove(b)
    graph[b].remove(a)
    
    land={1}
    connected={1}|graph[1]
    while land!=connected:
        land=connected.copy()
        for n in land:
            connected|=graph[n]
    if len(land)!=N:
        ans+=1

    graph[a].add(b)
    graph[b].add(a)

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
def main():
    #入力
    readline=stdin.readline
    N,M=map(int,readline().split())
    G=[[] for _ in range(N)]
    A=[0]*M
    B=[0]*M
    for i in range(M):
        a,b=map(lambda x:int(x)-1,readline().split())
        A[i]=a
        B[i]=b
        G[a].append(b)
        G[b].append(a)

    count=0
    for a,b in zip(A,B):
        is_searched=[False]*N
        is_searched[0]=True
        d=deque([0])
        while len(d)>=1:
            now=d.popleft()
            for x in G[now]:
                if (now==a and x==b) or (now==b and x==a):
                    continue
                if is_searched[x]==False:
                    d.append(x)
                    is_searched[x]=True

        if False in is_searched:
            count+=1
    
    print(count)
        
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,m=map(int,input().split())
def find(x):
  if par[x]<0:
    return x
  else:
    par[x]=find(par[x])
    return par[x]

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

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

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

AB=[]
for i in range(m):
  AB.append(tuple(int(i) for i in input().split()))
ans=0
for i in range(m):
  par=[-1]*n
  for j in range(m):
    if j==i:
      continue
    else:
      a,b=AB[j]
      unite(a-1,b-1)
  for i in range(n):
    find(i)
  if -min(par)<n:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,numpy as np,scipy as sc
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in input().split()]
N,M = LI()
E = [LI() for _ in range(M)]
ans = 0
for i in range(M):
    g = [i for i in range(N+1)]

    def root(x):
        if g[x] != x:
            g[x] = root(g[x])
        return g[x]

    for j in range(M):
        if i != j: g[root(E[j][0])] = root(E[j][1])

    ans += (root(E[i][0]) != root(E[i][1]))

print (ans)

Submission status: Accepted

Solution code:
import sys,queue,math,numpy as np,scipy as sc
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in input().split()]
N,M = LI()
E = [LI() for _ in range(M)]
ans = 0
for i in range(M):
    g = np.array([i for i in range(N+1)])

    def root(x):
        if g[x] != x:
            g[x] = root(g[x])
        return g[x]

    for j in range(M):
        if i != j: g[root(E[j][0])] = root(E[j][1])

    ans += (root(E[i][0]) != root(E[i][1]))

print (ans)

Submission status: Accepted

Solution code:
def get_root(s):
    if s != root[s]:
        root[s] = get_root(root[s])
        return root[s]
    return s

def unite(s, t):
    root_s = get_root(s)
    root_t = get_root(t)
    if not root_s == root_t:
        if rank[s] == rank[t]:
            root[root_t] = root_s
            rank[root_s] += 1
        elif rank[s] > rank[t]:
            root[root_t] = root_s
        else:
            root[root_s] = root_t

def same(s, t):
    if get_root(s) == get_root(t):
        return True
    else:
        return False

n, m = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]
ans = 0
for i in range(m):
    root = [i for i in range(n)]
    rank = [1 for _ in range(n)]
    for j in range(m):
        if not i == j:
            unite(l[j][0] - 1, l[j][1] - 1)
    c = 0
    for j in range(n - 1):
        if not same(j, j + 1):
            c = 1
            break
    if c == 1:
        ans += 1
print(ans)

Submission status: Accepted

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

  def find(self, x):
    if self.parents[x] < 0:
      return x
    
    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)]
  

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

ab = []
for i in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  
  ab.append((a,b))
  
ans = 0
for i in range(len(ab)):
  uf = UnionFind(n)
  
  for j in range(len(ab)):
    if i == j:
      continue
      
    uf.union(ab[j][0], ab[j][1])
    
  if uf.size(0) != n:
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
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 sample():
    uf = UnionFind(6)
    print(uf.parents)
    uf.union(0, 2)
    print(uf.parents)
    uf.union(1, 3)
    print(uf.parents)
    uf.union(4, 5)
    print(uf.parents)

def atc001():
    n, q = map(int, input().split())
    uf = UnionFind(n)
    for i in range(q):
        p, a, b = map(int, input().split())
        if p == 0:
            uf.union(a, b)
        else:
            if uf.same(a, b):
                print("Yes")
            else:
                print("No")

def abc049():
    n, k, l = map(int, input().split())
    road = UnionFind(n)
    train = UnionFind(n)
    for i in range(k):
        p, q = map(int, input().split())
        road.union(p - 1, q - 1)
    for i in range(l):
        p, q = map(int, input().split())
        train.union(p - 1, q - 1)

    pair = []
    pair_cnt = {}
    for i in range(n):
        t, r = road.find(i), train.find(i)
        pair.append([t, r])
        key = t * (10 ** 6) + r
        if key in pair_cnt:
            pair_cnt[key] += 1
        else:
            pair_cnt[key] = 1

    for i in range(n):
        [t, r] = pair[i]
        key = t * (10 ** 6) + r
        print(pair_cnt[key], end = " ")

def arc097():
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    pair = UnionFind(n)
    for i in range(m):
        x, y = map(int, input().split())
        pair.union(x - 1, y - 1)

    cnt = 0
    for i in range(n):
        if pair.same(i, p[i] - 1):
            cnt += 1
    print(cnt)

def arc032():
    n, m = map(int, input().split())
    road = UnionFind(n)
    for i in range(m):
        a, b = map(int, input().split())
        road.union(a - 1, b - 1)

    print(road.group_count() - 1)

def abc075():
    n, m = map(int, input().split())
    input_list = [list(map(int, input().split())) for _ in range(m)]
    cnt = 0
    for i in range(m):
        road = UnionFind(n)
        for j in range(m):
            p1 = input_list[j][0] - 1
            p2 = input_list[j][1] - 1
            if i != j:
                road.union(p1, p2)
        if road.group_count() >= 2:
            cnt += 1

    print(cnt)
abc075()

Submission status: Accepted

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

    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())
ab=[]
for _ in range(m):
  a,b=map(int,input().split())
  ab.append((a-1,b-1))
ans=0
uf=UnionFind(n)
for i in range(m):
  uf.__init__(n)
  for j in range(m):
    if j==i:
      continue
    a,b=ab[j]
    uf.union(a,b)
  if uf.group_count()==2:
    ans+=1
print(ans)