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: Wrong Answer

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

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

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

        if x == y:
            return False
        else:
            if self.d[x] > self.d[y]:
                x, y = y, x
            self.d[x] += self.d[y]
            self.d[y] = x
            return True

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


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

n, m = map(int, input().split())
uf = UnionFind(n)
ans = 0
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if uf.same(a, b):
        ans -= 2
    else:
        uf.unite(a, b)
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

N, M = map(int,input().split())
uf = UnionFind(N)
l = []
count=0
for i in range(M):
    a, b = map(int,input().split())
    l.append([a, b])
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if i != j:
            uf.union(a, b)
    if not uf.same_check(a,b):
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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 int_(num_str):
    return int(num_str) - 1

N, M = map(int, input().split())
ablist = [tuple(map(int_, input().split())) for _ in range(M)]
ans = 0
for i in range(N):
    uf = UnionFind(N)
    for j, ab in enumerate(ablist):
        if i == j:
            continue
        uf.union(*ab)
    if uf.group_count() > 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
def find_root(x):
    if parent[x] == x:
        return x
    else:
        return find_root(parent[x])


def unite(x, y):
    x = find_root(x)
    y = find_root(y)

    if x != y:
        if rank[x] < rank[y]:
            parent[x] = y
            size[y] += size[x]
        else:
            parent[y] = x
            size[x] += size[y]
            if rank[x] == rank[y]:
                rank[x] += 1


def roots():
    roots = []
    for i in range(N):
        roots.append(find_root(i))
    return roots


def group_count():
    return len(set(roots()))


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

parent = [i for i in range(N)]  # 根
rank = [1] * N  # 深さ
size = [1] * N  # iを根とするグループのサイズ

edge = [[ab[M - 1 - i][0] - 1, ab[M - 1 - i][1] - 1] for i in range(M)]

for i in range(M):
    unite(edge[i][0], edge[i][1])
count = group_count()

ans = 0
for j in range(N):
    # 再構築するため、初期化し直す
    parent = [i for i in range(N)]
    rank = [1] * N
    size = [1] * N
    for i in range(M):
        if i == j:
            continue
        unite(edge[i][0], edge[i][1])
    if group_count() > count:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
E = [[] for i in range(N)]
visited = []
ab = []
for i in range(M):
    a, b = map(int, input().split())
    ab.append([a-1, b-1])
         
def search(pos):
    for n_pos in E[pos]:
        if n_pos not in visited:
            visited.append(n_pos)
            search(n_pos)
cnt = 0
for i in range(M):
    visited = []
    E = [[] for i in range(N)]
    for j in range(M):
        if j == 1:
            continue
        E[ab[j][0]].append(ab[j][1])
        E[ab[j][1]].append(ab[j][0])
    search(0)
    if(len(visited) < N):
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
E = [[] for i in range(N)]
visited = []
ab = []
for i in range(M):
    a, b = map(int, input().split())
    ab.append([a-1, b-1])
         
def DFS(pos):
    for n_pos in E[pos]:
        if n_pos not in visited:
            visited.append(n_pos)
            DFS(n_pos)
cnt = 0
for i in range(M):
    visited = []
    E = [[] for i in range(N)]
    for j in range(M):
        if j == 1:
            continue
        E[ab[j][0]].append(ab[j][1])
        E[ab[j][1]].append(ab[j][0])
    DFS(0)
    if(len(visited) < N):
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
lst = [[] for i in range(N)]
visited = []
ab = []
for i in range(M):
    a, b = map(int, input().split())
    ab.append([a-1, b-1])
         
def DFS(pos):
    for n_pos in lst[pos]:
        if n_pos not in visited:
            visited.append(n_pos)
            DFS(n_pos)
cnt = 0
for i in range(M):
    visited = []
    lst = [[] for i in range(N)]
    for j in range(M):
        if j == 1:
            continue
        lst[ab[j][0]].append(ab[j][1])
        lst[ab[j][1]].append(ab[j][0])
    DFS(0)
    if(len(visited) < N):
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
dict = {i+1:[] for i in range(N)}
for _ in range(M):
    a, b = map(int, input().split())
    dict[a].append(b)
    dict[b].append(a)
    
    
def DFS(graph, start, end):
    stack = [start]
    visited = []
    label = stack.pop(0)
    stack = graph.get(label, []+stack)
    while stack:
        label = stack.pop(0)
        if(len(visited) == end):
            return 1
        if(label not in visited):
            visited.append(label)
            stack = graph.get(label, [])+stack
    return 0

ans = 0
for i in range(1, N+1):
    ans += DFS(dict, i, N)
print(M - ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations
    #from itertools import accumulate, product, permutations
    from math import floor, ceil

    #mod = 1000000007

    node,m =map(int, input().split())
    edge = [list(map(int, input().split())) for _ in range(m)]
    res = 0

    def dfs(num):
        for x, y in edge:
            if x==num:
                if flag[y-1]:
                    return
                else:
                    flag[y-1] = 1
                    dfs(y)
            if y==num:
                if flag[x-1]:
                    return
                else:
                    flag[x-1] = 1
                    dfs(x)
    
    for i in range(m):
        bridge = edge.pop(i)
        flag = [0]*node
        s = edge[0][0]
        flag[s-1]=1
        dfs(s)
        if not all(flag):
            res += 1
        edge.insert(i, bridge)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations
    #from itertools import accumulate, product, permutations
    from math import floor, ceil

    #mod = 1000000007

    node,m =map(int, input().split())
    edge = [list(map(int, input().split())) for _ in range(m)]
    res = 0

    def dfs(num):
        for x, y in edge:
            if x==num:
                if flag[y-1]:
                    return
                else:
                    flag[y-1] = 1
                    dfs(y)
            if y==num:
                if flag[x-1]:
                    return
                else:
                    flag[x-1] = 1
                    dfs(x)
    
    for i in range(m):
        bridge = edge.pop(i)
        for a,b in edge:
            flag = [0]*node
            flag[a-1]=1
            dfs(a)
            if all(flag):
                break
        else:
            res += 1
        edge.insert(i, bridge)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
ab=[]
adlist=[]
for i in range(m):
    ab.append(list(map(int,input().split())))
for i in range(n):    
    adlist.append([])
for i in range(m):
    x=ab[i][0]
    y=ab[i][1]
    adlist[x-1].append(y)
    adlist[y-1].append(x)
ans=0
#print(adlist)
def dfs(start,finish):
    global ans
    
    finish.add(start)#もう訪れたところ
    #print(finish)
    if len(finish)==n:#全部回ってたら終了
        ans+=1#橋じゃない数
        return 
    for i in adlist[start-1]:
        #print(i)
        if i not in finish:#通ったところに入っていないなら通れるということ
           
            dfs(i,finish)
finish=set()
finish.add(2)#いけないところ

dfs(2,finish)#引数がけすノード
for i in range(1,m):
  #  print("SDFG")
    finish=set()
    finish.add(i+1)#いけないところ
    dfs(1,finish)#引数がけすノード
print(n-ans)

"""
iのノードを消したときすべてのところを回れるかというう動作をn回繰り返す
"""

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
ab=[]
adlist=[]
for i in range(m):
    ab.append(list(map(int,input().split())))
for i in range(n):    
    adlist.append([])
for i in range(m):
    x=ab[i][0]
    y=ab[i][1]
    adlist[x-1].append(y)
    adlist[y-1].append(x)
ans=0
print(adlist)
def dfs(start,finish):
    global ans
    
    finish.add(start)#もう訪れたところ
    #print(finish)
    if len(finish)==n:#全部回ってたら終了
        ans+=1#橋じゃない数
        return 
    for i in adlist[start-1]:
        #print(i)
        if i not in finish:#通ったところに入っていないなら通れるということ
           
            dfs(i,finish)
finish=set()
finish.add(2)#いけないところ

dfs(2,finish)#引数がけすノード
for i in range(1,m):
    #print("SDFG")
    finish=set()
    finish.add(i+1)#いけないところ
    dfs(1,finish)#引数がけすノード
print(n-ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
ab=[]
adlist=[]
for i in range(m):
    ab.append(list(map(int,input().split())))
for i in range(n):    
    adlist.append([])
for i in range(m):
    x=ab[i][0]
    y=ab[i][1]
    adlist[x-1].append(y)
    adlist[y-1].append(x)
ans=0
#print(adlist)
def dfs(start,finish):
    global ans
    
    finish.add(start)#もう訪れたところ
        
    if len(finish)==n:#全部回ってたら終了
        ans+=1#橋じゃない数
        return 
    for i in adlist[start-1]:
        if i not in finish:#通ったところに入っていないなら通れるということ
            dfs(i,finish)



for i in range(m):
    finish=set()
    finish.add(i+1)#いけないところ
    dfs(1,finish)#引数がけすノード
print(n-ans)

"""
iのノードを消したときすべてのところを回れるかというう動作をn回繰り返す
"""

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
ab=[]
adlist=[]
for i in range(m):
    ab.append(list(map(int,input().split())))
for i in range(n):    
    adlist.append([])
for i in range(m):
    x=ab[i][0]
    y=ab[i][1]
    adlist[x-1].append(y)
    adlist[y-1].append(x)
ans=0
#print(adlist)
def dfs(not_node,start,finish):
    global ans
    
    finish.add(start)#もう訪れたところ
    finish.add(not_node)#いけないところ    
    if len(finish)==n:#全部回ってたら終了
        ans+=1#橋じゃない数
        return 
    for i in adlist[start-1]:
        if i not in finish:#通ったところに入っていないなら通れるということ
            dfs(not_node,i,finish)



for i in range(m):
    finish=set()
    dfs(i+1,1,finish)#引数がけすノード
print(n-ans)

"""
iのノードを消したときすべてのところを回れるかというう動作をn回繰り返す
"""

Submission status: Wrong Answer

Solution code:
def dfs(i,prohi,visited,cnt,edges,before=-1): #i番目の島を訪れるprohiの橋は使えない
    if visited[i]:
        cnt=1
        visited[i]=False
        for e in edges[i]:
            if e[1]!=prohi and e[0]!=before:
                cnt+=dfs(e[0],prohi,visited,cnt,edges,i)
        return cnt

    else:
        return cnt

def main():
    import sys
    input=sys.stdin.readline
    n,m=map(int,input().split())
    edges=[[] for i in range(n)]
    for i in range(m):
        a,b=map(int,input().split())
        a-=1
        b-=1
        edges[a].append([b,i])
        edges[b].append([a,i])
    
    ans=0
    for prohi in range(m):
        cnt=0
        visited=[True]*n
        if dfs(0,prohi,visited,cnt,edges)!=n:
            ans+=1
    print(ans)
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque,Counter
sys.setrecursionlimit(10**7)


def BFS(s):
    global bridge
    color=["white" for i in range(n)]
    D=[float("inf") for i in range(n)]

    color[s]="gray"
    D[s]=0
    queue=deque([s])

    while len(queue)!=0:
        u=queue.popleft()
        color[u]="gray"
        if len([i for i in M[u] if color[i]=="white"])==1:
            bridge +=1
        for i in M[u]:
            if color[i]=="white":
                color[i]="gray"
                D[i]=D[u]+1
                queue.append(i)
        color[u]="black"

    return bridge


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

bridge=0
print(BFS(0))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque,Counter
sys.setrecursionlimit(10**7)


def BFS(s):
    color=["white" for i in range(n)]
    D=[float("inf") for i in range(n)]

    color[s]="gray"
    D[s]=0
    queue=deque([s])

    while len(queue)!=0:
        u=queue.popleft()
        color[u]="gray"
        for i in M[u]:
            if color[i]=="white":
                color[i]="gray"
                D[i]=D[u]+1
                queue.append(i)
        color[u]="black"

    return D


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

cnt=0
for v,m in Counter(BFS(0)).items():
    if v!=0 and m==1:
        cnt +=1
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)


def BFS(s):
    global bridge
    color=["white" for i in range(n)]
    D=[float("inf") for i in range(n)]

    color[s]="gray"
    D[s]=0
    queue=deque([s])

    while len(queue)!=0:
        u=queue.popleft()
        color[u]="gray"
        cnt=0
        for i in M[u]:
            if color[i]=="white":
                color[i]="gray"
                D[i]=D[u]+1
                queue.append(i)
                cnt +=1
        if cnt==1:bridge +=1
        color[u]="black"

    return bridge


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

bridge=0
print(BFS(0))

Submission status: Wrong Answer

Solution code:
from collections import deque

def solve(n, m, AB):
    g = [[] for _ in range(n)]
    for a, b in AB:
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)

    q = deque(maxlen=m)
    q.append((-1, 0, [0]))
    used = {(-1, 0)}
    ng_edges = set()
    while len(q) > 0:
        prev, node, route = q.pop()
        for to in g[node]:
            if prev == to or (prev, to) in ng_edges:
                continue
            if (prev, to) in used:
                route = route + [to]
                i = len(route) - 1
                while route[i] != prev:
                    if route[i] < route[i - 1]:
                        ng_edges.add((route[i], route[i - 1]))
                    else:
                        ng_edges.add((route[i - 1], route[i]))
                    i -= 1
            else:
                q.append((node, to, route + [to]))
                used.add((node, to))

    return m - len(ng_edges)

_n, _m = map(int, input().split())
_AB = [map(int, input().split()) for _ in range(_m)]
print(solve(_n, _m, _AB))

Submission status: Wrong Answer

Solution code:
from queue import LifoQueue
from collections import defaultdict

def solve(n, m, AB):
    g = defaultdict(lambda: [])
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)
    q = LifoQueue(maxsize = m)
    q.put((0, 1, []))
    s = {1}

    total = m
    ng_edges = set()
    while not q.empty():
        p, c, l = q.get()
        cands = [n for n in g[c] if n != p]
        size = len(cands)
        for n in cands:
            if n not in s:
                nl = [e for e in l]
                if len(l) > 0 and size == 1:
                    # 分岐後の一本道の場合はエッジを追加
                    nl.append((c, n) if c < n else (n, c))
                if size >= 2:
                    # 分岐の場合はエッジをリセット
                    nl = [(c, n) if c < n else (n, c)]
                q.put((c, n, nl))
                s.add(n)
            else:
                # 既出の点が発見されたら登録
                for e in l:
                    ng_edges.add(e)
                ng_edges.add((c, n) if c < n else (n, c))
    return total - len(ng_edges)

_n, _m = map(int, input().split())
_AB = [map(int, input().split()) for _ in range(_m)]
print(solve(_n, _m, _AB))

Submission status: Wrong Answer

Solution code:
from queue import LifoQueue
from collections import defaultdict

def solve(n, m, AB):
    g = defaultdict(lambda: [])
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)
    q = LifoQueue(maxsize = m)
    q.put((0, 1, 0))
    s = {1}

    total = m
    ng_count = 0
    while not q.empty():
        p, c, l = q.get()
        cands = [n for n in g[c] if n != p]
        size = len(cands)
        count = 0
        for n in cands:
            if n not in s:
                nl = l
                if l > 0 and size == 1:
                    # 分岐後の一本道の場合は長さを+1
                    nl += 1
                if size >= 2:
                    # 分岐の場合は長さをリセット
                    nl = 1
                q.put((c, n, nl))
                s.add(n)
            else:
                # 既出の点が発見されたらそこまでの長さを引く
                ng_count += 1
                total -= l + 1
                count += 1
        if count > 0:
            # 同じ辺を複数削除してしまった場合に追加
            total += (count - 1) * l
    return total + ng_count // 2 # 重複削除のために追加

_n, _m = map(int, input().split())
_AB = [map(int, input().split()) for _ in range(_m)]
print(solve(_n, _m, _AB))

Submission status: Wrong Answer

Solution code:
from queue import LifoQueue
from collections import defaultdict

def solve(n, m, AB):
    g = defaultdict(lambda: [])
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)
    q = LifoQueue(maxsize = m)
    q.put((0, 1, 0))
    s = {1}

    total = m
    ng_count = 0
    while not q.empty():
        p, c, l = q.get()
        cands = [n for n in g[c] if n != p]
        size = len(cands)
        for n in cands:
            if n not in s:
                nl = l
                if l > 0 and size == 1:
                    # 分岐後の一本道の場合は長さを+1
                    nl += 1
                if size >= 2:
                    # 分岐の場合は長さをリセット
                    nl = 1
                q.put((c, n, nl))
                s.add(n)
            else:
                # 既出の点が発見されたらそこまでの長さを引く
                ng_count += 1
                total -= l + 1
    return total + ng_count // 2 # 重複削除のために追加

_n, _m = map(int, input().split())
_AB = [map(int, input().split()) for _ in range(_m)]
print(solve(_n, _m, _AB))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

Submission status: Wrong Answer

Solution code:
import sys
import copy

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

V = []
E = []

for i in range(N):
    V.append(set())

for i in range(M):
    *l,  = map(int, input().split())
    V[l[0]-1].add(l[1]-1)
    V[l[1]-1].add(l[0]-1)
    E.append([l[0], l[1]])

count = 0


E_copy = copy.deepcopy(E)
V_copy = copy.deepcopy(V)

for i in range(M):
    e = [E[i][0], E[i][1]]

    for v in V:
        if (e[0] in v):
            v.remove(e[0])
        elif (e[1] in v):
            v.remove(e[1])           
    
    #辺が存在しないノードがあるかをチェックする。
    for v in V:
        if len(v)==0:
            count = count + 1
            break
    
    E = copy.deepcopy(E_copy)
    V = copy.deepcopy(V_copy)
   
print(count)

Submission status: Wrong Answer

Solution code:
# class UnionFind:

#     def __init__(self, n):
#         self.n = n
#         self.parents = [i for i in range(n)]
#         self.ranks = [0] * n
#         self.count = n

#     def union(self, x, y):
#         self.link(x, y)

#     def link(self, x, y):
#         x_root = self.parents[x]
#         y_root = self.parents[y]
#         if x_root == y_root:
#             return
#         if self.ranks[x] < self.ranks[y]:
#             self.parents[x] = y_root
#         else:
#             self.parents[y] = x_root
#             if self.ranks[x] == self.ranks[y]:
#                 self.ranks[y] += 1
#         self.count -= 1

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

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.ranks = [0 for i in range(n)]
        self.count = n

    def link(self, x, y):
        self.union(x, y)

    def unite(self, x, y):
        self.link(x, y)

    def union(self, x, y):
        x_root = self.parents[x]
        y_root = self.parents[y]
        if x_root == y_root:
            return
        if self.ranks[x] < self.ranks[y]:
            # xをyグループにunion
            self.parents[x] = y_root
        else:
            # yをxグループにunion
            self.parents[y] = x_root
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
        self.count -= 1

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

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

n, m = map(int, input().split())
lis = []
count = 0
for i in range(m):
    lis.append(list(map(int, input().split())))
for i in range(m):
    u = UnionFind(n)
    for j in range(m):
        if i == j:
            continue
        u.unite(lis[j][0]-1, lis[j][1]-1)
    if not u.same(lis[i][0]-1, lis[i][1]-1):
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
# class UnionFind:

#     def __init__(self, n):
#         self.n = n
#         self.parents = [i for i in range(n)]
#         self.ranks = [0] * n
#         self.count = n

#     def union(self, x, y):
#         self.link(x, y)

#     def link(self, x, y):
#         x_root = self.parents[x]
#         y_root = self.parents[y]
#         if x_root == y_root:
#             return
#         if self.ranks[x] < self.ranks[y]:
#             self.parents[x] = y_root
#         else:
#             self.parents[y] = x_root
#             if self.ranks[x] == self.ranks[y]:
#                 self.ranks[y] += 1
#         self.count -= 1

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

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.ranks = [0 for i in range(n)]
        self.count = n

    def link(self, x, y):
        self.union(x, y)

    def union(self, x, y):
        x_root = self.parents[x]
        y_root = self.parents[y]
        if x_root == y_root:
            return
        if self.ranks[x] < self.ranks[y]:
            # xをyグループにunion
            self.parents[x] = y_root
        else:
            # yをxグループにunion
            self.parents[y] = x_root
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
        self.count -= 1

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

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

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

count = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if j == i:
            continue
        x, y = bridges[j]
        uf.union(x, y)
    if uf.count > 1:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.ranks = [0] * n
        self.count = n

    def union(self, x, y):
        self.link(x, y)

    def link(self, x, y):
        x_root = self.parents[x]
        y_root = self.parents[y]
        if x_root == y_root:
            return
        if self.ranks[x] < self.ranks[y]:
            self.parents[x] = y_root
        else:
            self.parents[y] = x_root
            if self.ranks[x] == self.ranks[y]:
                self.ranks[y] += 1
        self.count -= 1

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

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

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


count = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if j == i:
            continue
        x, y = bridges[j]
        uf.union(x, y)
    if uf.count > 1:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.ranks = [0] * n
        self.count = n

    def union(self, x, y):
        self.link(x, y)

    def link(self, x, y):
        x_root = self.parents[x]
        y_root = self.parents[y]
        if x_root == y_root:
            return       
        self.parents[y] = x_root
        self.count -= 1

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

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

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


count = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if j == i:
            continue
        else:
            x, y = bridges[j]
            uf.union(x, y)
    if uf.count > 1:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.ranks = [0] * n
        self.count = n

    def union(self, x, y):
        self.link(x, y)

    def link(self, x, y):
        x_root = self.parents[x]
        y_root = self.parents[y]
        if x_root == y_root:
            return        
        self.parents[y] = x_root


        # if self.ranks[x] > self.ranks[y]:
        #     self.parents[y] = x_root
        # else:
        #     self.parents[x] = y_root
        #     if self.ranks[x] == self.ranks[y]:
        #         self.ranks[y] += 1
        self.count -= 1

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

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

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


count = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if j == i:
            continue
        else:
            x, y = bridges[j]
            uf.union(x, y)
    if uf.count > 1:
        count += 1
print(count)