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:
# https://atcoder.jp/contests/abc075/tasks/abc075_c?lang=ja
# unionfind or 深さ優先探索


class UnionFind:
    def __init__(self, n):
        self.n = n
        # 各要素の親要素の番号を格納するリスト
        # 根がルートの時は、グループの要素数を格納　最初は全て根で要素数1
        self.parents = [-1] * n

    # 再帰 groupの根を返す
    # 経路圧縮あり
    def find(self, x):
        # 0より小さい場合は根
        if self.parents[x] < 0:
            # indexを返す
            return x
        else:
            # 根になるまで親を辿る
            # 経路圧縮 根のindexが全ての親に再帰的につく
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # groupを併合
    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
        # 根のグループ数を追加 xの方グループの要素数が多い前提なので多い方に寄せる
        self.parents[x] += self.parents[y]
        # 親(根)のindexを入れる
        self.parents[y] = x

    # 根が同じか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 全ての根の要素を返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

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


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

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

ans = 0
for i in range(n):
    uf = UnionFind(n)
    for j, (a, b) in enumerate(edge):
        if i == j:
            continue
        uf.union(a, b)
    if uf.group_count() == 1:
        ans += 1

print(n- ans)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc075/tasks/abc075_c?lang=ja
# unionfind or 深さ優先探索


class UnionFind:
    def __init__(self, n):
        self.n = n
        # 各要素の親要素の番号を格納するリスト
        # 根がルートの時は、グループの要素数を格納　最初は全て根で要素数1
        self.parents = [-1] * n

    # 再帰 groupの根を返す
    # 経路圧縮あり
    def find(self, x):
        # 0より小さい場合は根
        if self.parents[x] < 0:
            # indexを返す
            return x
        else:
            # 根になるまで親を辿る
            # 経路圧縮 根のindexが全ての親に再帰的につく
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # groupを併合
    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
        # 根のグループ数を追加 xの方グループの要素数が多い前提なので多い方に寄せる
        self.parents[x] += self.parents[y]
        # 親(根)のindexを入れる
        self.parents[y] = x

    # 根が同じか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 全ての根の要素を返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

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


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

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

ans = 0
for i in range(n):
    n_edge = (edge[:i] + edge[i + 1:])
    uf = UnionFind(n)
    for a, b in n_edge:
        uf.union(a, b)
    if uf.group_count() == 2:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc075/tasks/abc075_c?lang=ja
# unionfind or 深さ優先探索


class UnionFind:
    def __init__(self, n):
        self.n = n
        # 各要素の親要素の番号を格納するリスト
        # 根がルートの時は、グループの要素数を格納　最初は全て根で要素数1
        self.parents = [-1] * n

    # 再帰 groupの根を返す
    # 経路圧縮あり
    def find(self, x):
        # 0より小さい場合は根
        if self.parents[x] < 0:
            # indexを返す
            return x
        else:
            # 根になるまで親を辿る
            # 経路圧縮 根のindexが全ての親に再帰的につく
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # groupを併合
    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
        # 根のグループ数を追加 xの方グループの要素数が多い前提なので多い方に寄せる
        self.parents[x] += self.parents[y]
        # 親(根)のindexを入れる
        self.parents[y] = x

    # 根が同じか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 全ての根の要素を返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

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


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

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

ans = 0
for i in range(n):
    n_edge = (edge[:i] + edge[i + 1:])
    uf = UnionFind(n)
    for a, b in n_edge:
        uf.union(a, b)
    # 1本抜いても連結していた　→　橋でない
    if uf.group_count() == 1:
        ans += 1

print(n - ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
from copy import deepcopy
n, m = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    
ans = m

for goal in range(n):
    if len(edge[goal]) == 1: continue
    check = [0]*n
    check[goal] = 1
    que = deque([[goal, check, 0]])
    while que:
        now, c, cnt = que.popleft()
        for to in edge[now]:
            if cnt != 1 and to == goal:
                ans -= 1
                que = []
                break
            if c[to]: continue
            c_ = deepcopy(c)
            c_[to] = 1
            que.append([to, c_, cnt+1])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
from copy import deepcopy
n, m = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
ans = m
for st in range(n):
    check = [0]*n
    check[st] = 1
    que = deque([[st, check, -1]])
    while que:
        now, c, cnt = que.popleft()
        for to in edge[now]:
            if cnt and to == st:
                ans -= 1
                que = []
                break
            if c[to]: continue
            c_ = deepcopy(c)
            c_[to] = 1
            que.append([to, c_, cnt+1])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue
from decimal import Decimal

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


class UnionFind:
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, N):
        if self.tree[N] == N:
            return N
        else:
            self.tree[N] = self.root(self.tree[N])
            return self.tree[N]

    def same(self, x, y):
        return self.root(self.tree[x]) == self.root(self.tree[y])

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


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    XY = [il() for _ in range(M)]

    ret = 0
    for i in range(N):
        uf = UnionFind(N)
        for j in range(M):
            x, y = XY[j]
            if i != j and not uf.same(x-1, y-1):
                uf.unite(x-1, y-1)
        if sum([1 for n in range(N) if uf.tree[n] == n]) > 1: ret += 1
    print(ret)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue
from decimal import Decimal

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


class UnionFind:
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, N):
        if self.tree[N] == N:
            return N
        else:
            self.tree[N] = self.root(self.tree[N])
            return self.tree[N]

    def same(self, x, y):
        return self.root(self.tree[x]) == self.root(self.tree[y])

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


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    XY = [il() for _ in range(M)]

    ret = 0
    for i in range(N):
        uf = UnionFind(N)
        for j in range(M):
            if i != j:
                x, y = XY[j]
                uf.unite(x-1, y-1)
        if sum([1 for n in range(N) if uf.tree[n] == n]) > 1: ret += 1
    print(ret)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
l = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    l[a].append(b)
    l[b].append(a)
if m == n-1:
    print(m)
else:
    alone = []
    ans = 0
    for i in range(1, n+1):
        if len(l[i]) == 1:
            alone.append(i)
            ans += 1
    for i in range(1, n+1):
        flag = False
        for ll in l[i]:
            if ll in alone:
                flag = True
        if flag:
            ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
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

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]
n,m = map(int,input().split())
#初期化
#根なら-size,子なら親の頂点
par = [-1]*n
count = 0
graph = []
for i in range(m):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    graph.append([x,y])
for i in range(m):
    p = [j for j in range(n)]
    par = [-1]*n
    for j in range(m):
        if i != j:
            unite(graph[j][0],graph[j][1])
    if par[0] != (-1)*n:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import copy
n,m=map(int,input().split())
temp=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  temp[a].append(b)
  temp[b].append(a)
count=0
for i in range(n):
  if len(temp[i])==1:
    count=count+1
    l=temp[i][0]
    j=copy.copy(i)
    while True:
      if len(temp[l])==2:
        count=count+1
        if temp[l][0]==j:
          j=l
          l=temp[l][1]
        else:
          j=l
          l=temp[l][0]
      elif len(temp[l])==1:
        print(m)
        exit()
      else:
        break
print(count)

Submission status: Wrong Answer

Solution code:
import copy
n,m=map(int,input().split())
temp=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  temp[a].append(b)
  temp[b].append(a)
count=0
for i in range(n):
  if len(temp[i])==1:
    count=count+1
    l=temp[i][0]
    j=copy.copy(i)
    while True:
      if len(temp[l])==2:
        count=count+1
        if temp[l][0]==j:
          a=temp[l][1]
          j=l
          l=a
        else:
          a=temp[l][0]
          j=l
          l=a
      elif len(temp[l])==1:
        print(m)
        exit()
      else:
        break
print(count)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
temp=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  temp[a].append(b)
  temp[b].append(a)
count=0
for i in range(n):
  if len(temp[i])==1:
    count=count+1
    l=temp[i][0]
    j=i
    while True:
      if len(temp[l])==2:
        count=count+1
        if temp[l][0]==j:
          l=temp[l][1]
        else:
          l=temp[l][0]
        j=j+1
      elif len(temp[l])==1:
        print(m)
        exit()
      else:
        break
print(count)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
temp=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  temp[a].append(b)
  temp[b].append(a)
count=0
print(temp)
for i in range(n):
  if len(temp[i])==1:
    count=count+1
    l=temp[i][0]
    while True:
      if len(temp[l])==2:
        count=count+1
        for j in range(2):
          if temp[l][j]!=i:
            l=temp[l][j]
      else:
        break
print(count)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())

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

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

def dfs(v,w):
  l = [0 for _ in range(N)]
  l[v] = 1
  stack = [v]
  while stack:
    vv = stack.pop()
    for i in road[vv]:
      if i == w and v == vv or i == vv and v == w:
        continue
      else:
        if l[i] == 0:
          l[i] = 1
          stack.append(i)
  return sum(l)

ans = 0
check = [[0 for _ in range(N)] for _ in range(N)]

for n in range(N):
  for m in range(len(road[n])):
    if check[n][road[n][m]] == 0 or check[road[n][m]][n] == 0:
      check[n][road[n][m]] = 1
      check[road[n][m]][n] = 1
      d = dfs(n,road[n][m])
      if d != N:
        ans += 1

print(ans,road)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ls = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]

# Union Find Tree
def find(par, x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par, par[x])
        return par[x]

def unite(par, rank, x, y):
    rootx = find(par, x)
    rooty = find(par, y)

    if rootx == rooty:
        return False
    else:
        if rank[rootx] < rank[rooty]:
            par[rootx] = rooty
        else:
            par[rooty] = rootx
            if rank[rootx] == rank[rooty]: rank[rootx] += 1
        return True

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

c = 0
for i in range(M):
    par = [k for k in range(N)]
    rank = [0] * N
    for idx, (a, b) in enumerate(ls):
        if idx == i:
            continue
        unite(par, rank, a, b)
        unite(par, rank, b, a)
    
    if len(set(par)) >= 2:
        c += 1
print(c)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())

dist = { i:[] for i in range(1,N+1)}

for i in range(M):
  a,b = map(int,input().split())
  dist[a].append(b)
  dist[b].append(a)
  
cnt = 0  
for i in range(1,N+1):
  if len(dist[i]) == 1:
    cnt += 1
print(int(cnt))

Submission status: Wrong Answer

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

from collections import defaultdict
from collections import deque
d=defaultdict(list)
for l in L:
    d[l[0]-1].append(l[1]-1)
    d[l[1]-1].append(l[0]-1)

print(d)

# 辺を切断した状態で幅優先探索をしてすべての頂点に行けるか
def check_path(hen):
        
    visit=[False]*n
    q=deque([0])
    
#    print('L=',L)
#    print('hen=',hen)
    
    while q:
        node = q.popleft()
#        print('current->', node)
        visit[node]=True
        Nexts = d[node]
        for nxt in Nexts:
            if visit[nxt]:
#                print(nxt, ' is already visited.')
                continue
            
            if node+1 not in L[hen] or nxt+1 not in L[hen]:
#                print('next->', nxt)
                q.append(nxt)
    
#    print('visit=', visit)
    return all(visit)
    
cnt=0
for i in range(m):
    if not check_path(i):
        cnt+=1

print(cnt)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
edge=[[] for _ in range(n+1)]
eab=[]
for i in range(m):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
    eab.append([a,b])
 
def dfs(visited,count,node):
    visited[node]=True
    count+=1
    ev=edge[node]
    for node in ev:
        if visited[node]:
            continue
        else:
            count=dfs(visited,count,node)
    return count
  
ans=0
for i in range(m):
    a,b=eab[i]
    edge[a].remove(b)
    edge[b].remove(a)
    ci=dfs([False for _ in range(n+1)],0,0)
    if ci!=n:
        ans+=1
    edge[a].append(b)
    edge[b].append(a)
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parents[x] == x:
            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.rank[x] < self.rank[y]:
            self.parents[x] = y
        else:
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

n,m = map(int,input().split())
A = [0]*m
B = [0]*m
for i in range(m):
    A[i],B[i] = map(int,input().split())

ans = 0
for i in range(m):
    u = UnionFind(n)
    for j in range(m):
        if i==j:continue
        a,b = A[j]-1,B[j]-1
        u.union(a,b)
    for j in range(n):
        u.find(j)
    if sum(u.parents)!=0:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
    n,m = map(int,input().split())
    ab=[list(map(int,input().split())) for _ in range(m)]
    cnt=0
    for i in range(n):
        edge = [[] for i in range(n)]
        for j in range(m):
            if j==i:
                continue
            else:
                edge[ab[j][0]-1].append(ab[j][1]-1)
                edge[ab[j][1]-1].append(ab[j][0]-1)
        visit=[False]*n
        if i==0:
            chk=[1]
            visit[1]=True
        else:
            chk=[0]
            visit[0]=True
        while chk:
            x=chk.pop()
            visit[x]=True
            for i in edge[x]:
                if visit[i]==True:
                    continue
                chk.append(i)
        for i in visit:
            if i==False:
                cnt+=1
                break
    print(cnt)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
sys.setrecursionlimit(10**9)
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
#グラフの閉路検出だけ
def resolve():
    N,M=pin()
    gragh={(v+1):[] for v in range(N)}
    for i in range(M):
        a,b=pin()
        gragh[a].append(b)
        gragh[b].append(a)
    #print(gragh)#->ok
    heiro=dict()
    
    def dfs(v_from,travel,prev=None):
        tra=list(travel)    
        for v_to in gragh[v_from]:
            #stoper
            if v_to==prev:
                #print("a")
                continue
            if v_to in(tra):#closed 
                dicset=set()
                f=0
                kyori=0
                for n,t in enumerate(tra):
                    if v_to==t:
                        f=1
                    if f==1:
                        kyori+=1
                        dicset.add(t)
                if len(dicset)>2:
                    dicset=frozenset(dicset)
                    heiro.setdefault(dicset,kyori)
                    #print(gragh[v_from],(prev,v_from,v_to),dicset,tra)
                    break
                continue
            #caller
            prev=v_from
            tra2=tra[:]
            tra2.append(v_to)  
            #print(tra,v_to) 
            dfs(v_to,tra2,prev)

        return
        
    dfs(1,[1])
    print(M-sum(heiro.values()))
#%%submit!
resolve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
sys.setrecursionlimit(10**9)
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
#グラフの閉路検出だけ
def resolve():
    N,M=pin()
    gragh={(v+1):[] for v in range(N)}
    for i in range(M):
        a,b=pin()
        gragh[a].append(b)
        gragh[b].append(a)
    #print(gragh)#->ok
    heiro=dict()
    
    def dfs(v_from,travel,prev=None):
        tra=list(travel)    
        for v_to in gragh[v_from]:
            #stoper
            if v_to==prev:continue
            if v_to in(tra):#closed 
                dicset=set()
                f=0
                kyori=0
                for n,t in enumerate(tra):
                    if v_to==t:
                        f=1
                    if f==1:
                        kyori+=1
                        dicset.add(t)
                dicset=frozenset(dicset)
                heiro.setdefault(dicset,kyori)
                break
            #caller
            prev=v_from
            tra.append(v_to)        
            dfs(v_to,tra,prev)
    
    dfs(1,[1])
    (print(M-sum(filter(lambda x:x>2,heiro.values()))))
#%%submit!
resolve()

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m = tuple(map(int,input().split()))

edge = []

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

for a,b in edge:
  matrix[a][b] = 0
  matrix[a][b] = 0
  
  checked = [False]*n
  queue = deque([0])
  while(len(queue)>0):
    q = queue.pop()
    if checked[q]:
      continue
    else:
      checked[q] = True
      mat = matrix[q]
      for i in range(n):
        if matrix[i] == 1:
          queue.append(i)
          
  if not all(checked):
    ans+=1
  
  matrix[a][b] = 1
  matrix[b][a] = 1

print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def same(self, x, y):
        if self.find(x) == self.find(y):
            return True
        else:
            return False


N, M = map(int, input().split())
ab = [list(map(int, 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]
        if j != i:
            UF.unite(a-1, b-1)
    if UF.size[0] < N:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
#Nはノード数、Mはエッジ数
n,m = map(int, input().split())

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

cnt=0
j=0
for x in ab:
  ls=list(range(n))
  for y in ab:
    if y !=x:
      for i in range(n):
        if ls[i]==ls[y[1]-1]:
          ls[i]=ls[y[0]-1]
  if len(set(ls)) !=1:
    cnt+=1

print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np

def dfs(v1):
    visited[v1] = 1
    for v2 in range(n):
        if graph[v1][v2] == 0: continue
        if visited[v2] == 1: continue
        dfs(v2)
    if all(visited): return 1
    return 0
# nは頂点の数
n, m = map(int,input().split())
ab = np.array([list(map(int,input().split())) for i in range(m)])
a,b = ab.T[0]-1,ab.T[1]-1

#隣接行列
graph = [[0] * n for _ in range(n)]
ans = 0
for x,y in zip(a,b):
    for z,w in zip(a,b): graph[z][w],graph[w][z] = 1,1
    graph[x][y],graph[y][z] = 0,0
    visited = [0]*(n)
    if not dfs(0): ans += 1

print(ans)

Submission status: Wrong Answer

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

adj = [list() for _ in range(n)]

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

bridge = 0
while True:
    for i, ai in enumerate(adj):
        if len(ai) == 1:
            adj[i] = []
            adj[ai[0]].remove(i)
            bridge += 1
            continue
    else:
        break

print(bridge)

Submission status: Wrong Answer

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

adj = [list() for _ in range(n)]

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

bridge = 0
while True:
    for i, ai in enumerate(adj):
        if len(ai) == 1:
            adj[i] = []
            adj[ai[0]].remove(i)
            bridge += 1
    else:
        break

print(bridge)

Submission status: Wrong Answer

Solution code:
import numpy as np

def dfs(v1):
    visited[v1] = 1
    for v2 in range(n):
        if graph[v1][v2] == 0: continue
        if visited[v2] == 1: continue
        dfs(v2)
    if all(visited): return 1
    return 0
# nは頂点の数
n, m = map(int,input().split())
ab = np.array([list(map(int,input().split())) for i in range(m)])
a,b = ab.T[0]-1,ab.T[1]-1

#隣接行列
graph = [[0] * n for _ in range(n)]
ans = 0
for x,y in zip(a,b):
    for z,w in zip(a,b): graph[z][w],graph[w][z] = 1,1
    graph[x][y],graph[y][z] = 0,0
    visited = [0]*(n)
    if not dfs(0): print(visited); ans += 1

print(ans)

Submission status: Wrong Answer

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

edges = {}
node_count = 0
node_seen = set()
edge_list = []

def dfs(t_node, t_edge):
    global node_count, node_seen
    node_count += 1
    node_seen.add(t_node)
    next_nodes = set(edges[t_node]) - node_seen
    if len(next_nodes) == 0:
        return
    else:
        for nextn in next_nodes:
            if t_node in t_edge and nextn in t_edge:
                pass
            else:
                dfs(nextn, t_edge)

def main():
    global edges, node_count, node_seen, edge_list
    n, m = map(int, input().split())
    all_nodes = set([i for i in range(1, n + 1)])
    edges = {e: [] for e in range(1, n + 1)}
    for _ in range(m):
        s, g = map(int, input().split())
        edges[s].append(g)
        edges[g].append(s)
        edge_list.append((s, g))
        edge_list.append((g, s))
    # 処理
    r = 0
    for itry in range(m):
        node_seen = set()
        node_count = 0
        dfs(edge_list[itry][0], edge_list[itry])
        r += all_nodes != node_seen

    print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

edges = {}
node_count = 0
node_seen = set()
edge_list = []

def dfs(t_node, t_edge):
    global node_count, node_seen
    node_count += 1
    node_seen.add(t_node)
    next_nodes = set(edges[t_node]) - node_seen
    if len(next_nodes) == 0:
        return
    else:
        for nextn in next_nodes:
            if t_node in t_edge and nextn in t_edge:
                pass
            else:
                dfs(nextn, t_edge)

def main():
    global edges, node_count, node_seen, edge_list
    n, m = map(int, input().split())
    all_nodes = set([i for i in range(1, n + 1)])
    edges = {e: [] for e in range(1, n + 1)}
    for _ in range(m):
        s, g = map(int, input().split())
        edges[s].append(g)
        edges[g].append(s)
        edge_list.append((s, g))
        edge_list.append((g, s))
    # 処理
    r = 0
    for itry in range(m):
        node_seen = set()
        node_count = 0
        dfs(1, edge_list[itry])
        r += all_nodes != node_seen
    print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

edges = {}
node_count = 0
node_seen = set()
edge_list = []


def dfs(t_node, t_edge):
    global node_count, node_seen
    node_count += 1
    node_seen.add(t_node)
    next_nodes = set(edges[t_node]) - node_seen
    if len(next_nodes) == 0:
        return
    else:
        for nextn in next_nodes:
            if t_node in edge_list[t_edge] and nextn in edge_list[t_edge]:
                pass
            else:
                dfs(nextn, t_edge)

def main():
    global edges, node_count, node_seen, edge_list
    n, m = map(int, input().split())
    edges = {e: [] for e in range(1, n + 1)}
    for _ in range(m):
        s, g = map(int, input().split())
        edges[s].append(g)
        edges[g].append(s)
        edge_list.append((s, g))
        edge_list.append((g, s))
    r = 0
    for itry in range(m):
        node_seen = set()
        node_count = 0
        dfs(1, itry)
        r += node_count < n
    print(r)

if __name__ == '__main__':
    main()