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/submissions/15509548

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

#n = len(g)
root = 0
order = [n]*n
low = [n]*n

s = [root]
cnt = 0
par = [-1]*n
seq = []
while s:
    v = s.pop()
    if order[v] != n:
        continue
    order[v] = cnt
    seq.append(v)
    low[v] = cnt
    cnt += 1
    for u in g[v]:
        if order[u] < cnt:
            if par[v] != u:
                low[v] = min(low[v], order[u])
                continue
        else:
            par[u] = v
            s.append(u)
child = [[] for _ in range(n)]
for v in range(n):
    if par[v] != -1:
        child[par[v]].append(v)
#seq.reverse()
#for v in seq:
    #for u in child[v]:
        #low[v] = min(low[v], low[u])
# bridge
bridge = []
for p in range(n):
    for c in child[p]:
        if order[p] < low[c]:
            bridge.append((p, c))

# articulation points
AP = []
for v in range(n):
    if v == root:
        if len(child[v]) >= 2:
            AP.append(v)
    else:
        for c in child[v]:
            if order[v] <= low[c]:
                AP.append(v)
                break

print(len(bridge))

Submission status: Wrong Answer

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

check = [False for _ in range(n)]
d_s = [10 ** 10 for _ in range(n)]
ans = m
def dfs(pos, b_pos, d):
    d_s[pos] = min(d, d_s[pos])
    flg = d
    global ans
    for n_pos in edges[pos]:
        if n_pos == b_pos:
            continue
        if check[n_pos]:
            flg = min(flg, d_s[n_pos])
            ans -= 1
            continue
        check[n_pos] = True
        if dfs(n_pos, pos, d + 1) < d:
            ans -= 1
    return flg        
    
check[0] = True
dfs(0, -1, 0)
print(ans)

Submission status: Wrong Answer

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

check = [False for _ in range(n)]
d_s = [10 ** 10 for _ in range(n)]
ans = m
def dfs(pos, b_pos, d):
    d_s[pos] = d
    flg = d
    global ans
    for n_pos in edges[pos]:
        if n_pos == b_pos:
            continue
        if check[n_pos]:
            flg = min(flg, d_s[n_pos])
            ans -= 1
            continue
        check[n_pos] = True
        if dfs(n_pos, pos, d + 1) < d:
            ans -= 1
    return flg        
    
check[0] = True
dfs(0, -1, 0)
print(ans)

Submission status: Wrong Answer

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

check = [False for _ in range(n)]
d_s = [10 ** 10 for _ in range(n)]
ans = m
def dfs(pos, b_pos, d):
    d_s[pos] = d
    flg = d
    global ans
    for n_pos in edges[pos]:
        if n_pos == b_pos:
            continue
        if check[n_pos]:
            flg = min(flg, d_s[n_pos])
            ans -= 1
            continue
        check[n_pos] = True
        if dfs(n_pos, pos, d + 1) <= d:
            ans -= 1
    return flg        
    
check[0] = True
dfs(0, -1, 0)
print(ans)

Submission status: Wrong Answer

Solution code:
class union_find():
    def __init__(self,n):
        self.n=n
        ##親要素のノード番号を格納。par[x]==xのときそのノードは根
        ##親とはその上にノードなし！！　
        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[y]+=1

    def same(self,x,y):
        return self.find(x) == self.find(y)
      
n,m=map(int,input().split())
uf=union_find(n)
ans=0
s=[]
for _ in range(m):
  a=list(map(int,input().split()))
  s.append(a)
  uf.union(a[0],a[1])
  
for e in range(m):
  uf1=union_find(n)
  for d in range(m):
    if d!=e:
      uf1.union(s[d][0],s[d][1])
      
  if uf.par!=uf1.par:
    ans+=1

    
print(ans)

Submission status: Wrong Answer

Solution code:
class union_find():
    def __init__(self,n):
        self.n=n
        ##親要素のノード番号を格納。par[x]==xのときそのノードは根
        ##親とはその上にノードなし！！　
        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(self,x,y):
        return self.find(x) == self.find(y)
      
n,m=map(int,input().split())
uf=union_find(n)
ans=0
s=[]
for _ in range(m):
  a=list(map(int,input().split()))
  s.append(a)
  uf.union(a[0],a[1])
  
for e in range(m):
  uf1=union_find(n)
  for d in range(m):
    if d!=e:
      uf1.union(s[d][0],s[d][1])
      
  if uf.par!=uf1.par:
    ans+=1

    
print(ans)

Submission status: Wrong Answer

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,M=mi()
    G = [[] for _ in range(N)]
    E = []
    for i in range(M):
        a,b = mi()
        a-=1; b -= 1 # 0-index

        G[a].append(b)
        G[b].append(a)
        E.append((a,b))
    
    deg1_v = -1
    for i in range(N):
        deg = len(G[i])
        if deg == 1:
            deg1_v = i
            break
    
    if deg1_v == -1:
        print(0)
        exit()

    ans = 0
    for i in range(M):
        a,b = E[i]
        G[a].remove(b)
        G[b].remove(a)

        visited_count = 0
        stack = deque([deg1_v])
        seen = set()
        while stack:
            visited_count += 1
            current_e = stack.popleft()

            seen.add(current_e)
            for next in G[current_e]:
                if next in seen: continue
                stack.append(next)
    
        if visited_count != N:
            # print(i)
            ans += 1
    
        G[a].append(b)
        G[b].append(a)
    
    print(ans)





    


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
g=lambda x:int(x)-1
n,m=map(int,input().split())
l=[list(map(g,input().split())) for i in range(m)]

def dfs(t):
    visit[t]=1
    for tt in z[t]:
      if visit[tt]==0:
        global score
        score+=1
        dfs(tt)
  
ans=0
for i in range(n):
  L=l[:i]+l[i+1:]
  z=[[] for i in range(n)]
  for ll in L:
    a,b=ll
    z[a].append(b)
    z[b].append(a)
  visit=[0]*n
  score=0
  dfs(0)
  if score!=n-1:
    ans+=1
  
print(ans)

Submission status: Wrong Answer

Solution code:
g=lambda x:int(x)-1
n,m=map(int,input().split())
l=[list(map(g,input().split())) for i in range(m)]

def dfs(t):
    visit[t]=1
    for tt in z[t]:
      if visit[tt]==0:
        global score
        score+=1
        dfs(tt)
  
ans=0
for i in range(n):
  L=l[:i]+l[i+1:]
  z=[[] for i in range(n)]
  for ll in L:
    a,b=ll
    z[a].append(b)
    z[b].append(a)
  visit=[0]*n
  score=0
  dfs(0)
  if score!=n-1:
    ans+=1
  
print(ans)

Submission status: Wrong Answer

Solution code:
mod = 1000000007
eps = 10**-9


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

    # return: articulation points, bridges
    # The graph must be connected.
    def lowlink(adj, root=1):
        N = len(adj) - 1
        order = [N + 1] * (N + 1)
        low = [N + 1] * (N + 1)
        AP = []
        bridge = []

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

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

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

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

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

        return AP, bridge

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

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
n,m = map(int,input().split())
L = [[0]*n for i in range(n)]
num = []
for i in range(m):
    a,b =  map(int,input().split())
    a,b = a-1,b-1
    L[a][b] = 1
    L[b][a] = 1
    num.append((a,b))
#
def dfs(x):
    if visited[x]:
        return
    visited[x] = 1
    for i in range(n-1):
        if tmp[x][i]:
            dfs(i)
cnt = 0
for a,b in num:
    tmp = deepcopy(L)
    visited = [0]*n
    tmp[a][b] = 0
    tmp[b][a] = 0
    #print(tmp)
    dfs(0)
    #print(visited)
    if 0 in visited:
        cnt +=1
print(cnt)

Submission status: Wrong Answer

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

for i in range(m):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    L[a].append(b)
    L[b].append(a)
#print(L)
cnt = 0

for i in range(m):
    G = [[] for _ in range(n)]
    visited = [0]*n
    for j in range(m):
        if i == j:
            continue
    Q = deque([0])
    while Q:
        q = Q.pop()
        for g in G[q]:
            if visited[g] == 0:
                visited[g] = 1
                #print(visited)
                Q.append(g)
    if 0 in visited:
        cnt +=1
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int, input().split())
#辺を取り除くことはabのセットとなっている要素から取り除くことと等価。頂点を消すのではない。
ab = [list(map(int, input().split())) for _ in range(M)]
c = 0
print(ab)
for i in range(M):
    G = [[] for _ in range(N)]
    for j in range(M):
        if i == j:
            continue
        a, b = ab[j][0], ab[j][1]
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)
    Q = deque()
    Q.append(0)
    d = [0] * N
    d[0] = 1
    while Q:
        q = Q.popleft()
        for g in G[q]:
            if d[g] == 0:
                d[g] = 1
                Q.append(g)
    if 0 in d:
        c += 1

print(c)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

res = 0
for i in range(m):
    edge = [[] for _ in range(n)]
    for j in range(m):
        if i == j:
            continue
        a, b = e[j]
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)

    d = deque([0])
    visited = [False] * n
    visit_cnt = 0
    while d:
        node = d.popleft()
        visited[node] = True
        visit_cnt += 1
        for next_node in edge[node]:
            if not visited[next_node]:
                d.append(next_node)
    if visit_cnt < n:
        res += 1

print(res)

Submission status: Wrong Answer

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

  def find(self, n):
    if self.parents[n] < 0:
      return n
    else:
      self.parents[n] = self.find(self.parents[n])
      return self.parents[n]

  def union(self, u,v):
    p1,p2 = self.find(u),self.find(v)
    if p1==p2: return
    if p1 > p2:
      p1,p2 = p2,p1
    self.parents[p1] += self.parents[p2]
    self.parents[p2] = p1

  def same(self, u,v):
    return self.find(u) == self.find(v)

N,M = map(int,input().split())
uf = UF(N+1)
ans = 0
for _ in range(M):
  u,v = map(int,input().split())
  if not uf.same(u,v):
    ans += 1
    uf.union(u,v)
  else:
    ans -= 2

print(max(0,ans))

Submission status: Wrong Answer

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

  def find(self, n):
    if self.parents[n] < 0:
      return n
    else:
      self.parents[n] = self.find(self.parents[n])
      return self.parents[n]

  def union(self, u,v):
    p1,p2 = self.find(u),self.find(v)
    if p1==p2: return
    if p1 > p2:
      p1,p2 = p2,p1
    self.parents[p1] += self.parents[p2]
    self.parents[p2] = p1

  def same(self, u,v):
    return self.find(u) == self.find(v)

N,M = map(int,input().split())
uf = UF(N+1)
ans = 0
for _ in range(M):
  u,v = map(int,input().split())
  if not uf.same(u,v):
    ans += 1
    uf.union(u,v)
  else:
    ans -= 2

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

n, m = map(int, input().split())
# E = [[*map(int, input().split())] for _ in range(m)]

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

# print(*E,sep='\n')

vis = [0]*n
# vis[0] = 1
q = deque()
q.append([0, E[0]])
ans = 0
while q:
    # print(q)
    bf = len(q)
    # if bf == 1 and len(to_list)==1:
    if bf == 1:
        ans += 1
    f, to_list = q.popleft()
    # print('f,to_list',f,to_list)
    if vis[f]: continue
    vis[f] = 1
    for t in to_list:
        # print(t,E[t])
        if vis[t]: continue
        # print(t,E[t])
        q.append([t, E[t]])
    # print(q)
    af = len(q)
    df = af-bf
    # print('bf, af, df',bf,af, df)
    # if df == 0:
    # if bf == af:
    # if af == 1:
    #     ans += 1
if len(E[0]) > 1: ans -= 1
print(ans-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

n, m = map(int, input().split())
# E = [[*map(int, input().split())] for _ in range(m)]

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

# print(*E,sep='\n')

vis = [0]*n
vis[0] = 1
q = deque()
q.append(E[0])
# print(q)
ans = 0
while q:
    bf = len(q)
    # if bf == 1:
    #     ans += 1
    to_list = q.popleft()
    # print(to_list)
    # print('bf len(q)',bf)
    for to in to_list:
        if vis[to]: continue
        vis[to] = 1
        # print(to)
        q.append(E[to])
    af = len(q)
    df = af-bf
    # print('af len(q)',af)
    # print('bf, af, df',bf,af, df)
    # if df == 0:
    if bf == af:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

n, m = map(int, input().split())
# E = [[*map(int, input().split())] for _ in range(m)]

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

# print(*E,sep='\n')

vis = [0]*n
vis[0] = 1
q = deque()
q.append(E[0])
# print(q)
ans = 0
while q:
    bf = len(q)
    to_list = q.popleft()
    # print(to_list)
    # print('bf len(q)',bf)
    for to in to_list:
        if vis[to]: continue
        vis[to] = 1
        # print(to)
        q.append(E[to])
    af = len(q)
    df = af-bf
    # print('af len(q)',af)
    # print('bf, af, df',bf,af, df)
    if df == 0:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
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
    #sizeの大きいほうがx
    if par[x] > par[y]: x,y = y,x
    par[x] += par[y]
    par[y] = x
    return True

n, m = map(int, input().split())
ab = []
ans = m
for _ in range(m):
    a, b = map(int, input().split())
    ab.append([a-1, b-1])
for i in range(m):
    par = [-1]*n
    for j in range(m):
        if i==j: continue
        unite(ab[j][0], ab[j][1])
    if -par[0] == n: ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
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
    #sizeの大きいほうがx
    if par[x] > par[y]: x,y = y,x
    par[x] += par[y]
    par[y] = x
    return True

n, m = map(int, input().split())
ab = []
ans = m
for _ in range(m):
    a, b = map(int, input().split())
    ab.append([a-1, b-1])
for i in range(m):
    par = [-1]*n
    for j in range(m):
        if i==j: continue
        unite(ab[j][0], ab[j][1])
    print(par)
    if -par[0] == n: ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc075/tasks/abc075_c?lang=ja

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

    def sequence(self, x, seq):
        if self.parents[x] < 0:
            seq.append(x)
            return seq
        seq.append(x)
        self.sequence(self.parents[x], seq)
        return seq

    def union(self,x,y,res):
        X = self.sequence(x,[])
        Y = self.sequence(y,[])
        if X[-1] == Y[-1]:
            z = set(X) & set(Y)
            for i in range(len(X)-1):
                res.add(tuple(sorted([X[i],X[i+1]])))
                if X[i+1] in z:
                    break
            for i in range(len(Y)-1):
                res.add(tuple(sorted([Y[i],Y[i+1]])))
                if Y[i+1] in z:
                    break
            res.add(tuple(sorted([x, y])))
        else:
            if x < y:
                self.parents[y] = x
            else:
                self.parents[x] = y

N, E = map(int, input().split())
tree = UnionFind(N)
res = set()
for _ in range(E):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    tree.union(x,y,res)

print(E - len(res))
# print(tree.parents)
# print(res)


'''

3 3
1 2
2 3
3 1


'''


'''

9 12
1 2
1 3
1 4
1 5
6 2
6 3
7 3
7 4
8 4
8 5
9 5
9 2

'''

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc075/tasks/abc075_c?lang=ja

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

    def sequence(self,x,sec):
        if self.parents[x] < 0:
            sec.append(x)
            return sec
        sec.append(x)
        self.sequence(self.parents[x],sec)
        return sec

    def union(self,x,y,res):
        X = self.sequence(x,[])
        Y = self.sequence(y,[])
        if X[-1] == Y[-1]:
            z = set(X) & set(Y)
            for i in range(len(X)-1):
                res.add(tuple(sorted([X[i],X[i+1]])))
                if X[i+1] in z:
                    break
            for i in range(len(Y)-1):
                res.add(tuple(sorted([Y[i],Y[i+1]])))
                if Y[i+1] in z:
                    break
            res.add(tuple(sorted([x, y])))
        else:
            self.parents[y] = x

N, E = map(int, input().split())
tree = UnionFind(N)
res = set()
for _ in range(E):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    tree.union(x,y,res)

print(E - len(res))

'''

7 8
1 2
2 3
3 4
1 4
3 6
6 5
4 5
4 7

'''

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc075/tasks/abc075_c?lang=ja

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

    def sequence(self,x,res):
        if self.parents[x] < 0:
            res.append(x)
            return res
        res.append(x)
        self.sequence(self.parents[x],res)
        return res

    def union(self,x,y,res):
        X = self.sequence(x,[])
        Y = self.sequence(y,[])
        if X[-1] == Y[-1]:
            z = set(X) & set(Y)
            for i in range(len(X)-1):
                res.add(tuple(sorted([X[i],X[i+1]])))
                if X[i+1] in z:
                    break
            for i in range(len(Y)-1):
                res.add(tuple(sorted([Y[i],Y[i+1]])))
                if Y[i+1] in z:
                    break
            res.add(tuple(sorted([x, y])))
        else:
            self.parents[y] = x

N, E = map(int, input().split())
tree = UnionFind(N)
res = set()
for _ in range(E):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    tree.union(x,y,res)

print(E - len(res))

'''

7 8
1 2
2 3
3 4
1 4
3 6
6 5
4 5
4 7

'''

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc075/tasks/abc075_c?lang=ja

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

    def sequence(self,x,res):
        if self.parents[x] < 0:
            res.append(x)
            return res
        res.append(x)
        self.sequence(self.parents[x],res)
        return res

    def union(self,x,y,res):
        X = self.sequence(x,[])
        Y = self.sequence(y,[])
        if X[-1] == Y[-1]:
            z = set(X) & set(Y)
            for i in range(len(X)-1):
                res.add(tuple(sorted([X[i],X[i+1]])))
                if X[i+1] in z:
                    break
            for i in range(len(Y)-1):
                res.add(tuple(sorted([Y[i],Y[i+1]])))
                if Y[i+1] in z:
                    break
            res.add(tuple(sorted([x, y])))
            print(X, Y, res)
        else:
            self.parents[y] = x

N, E = map(int, input().split())
tree = UnionFind(N)
res = set()
for _ in range(E):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    tree.union(x,y,res)

print(E - len(res))

'''

7 8
1 2
2 3
3 4
1 4
3 6
6 5
4 5
4 7

'''

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc075/tasks/abc075_c?lang=ja

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

    def sequence(self,x,res):
        if self.parents[x] < 0:
            res.append(x)
            return res
        res.append(x)
        self.sequence(self.parents[x],res)
        return res

    def union(self,x,y,res):
        X = self.sequence(x,[])
        Y = self.sequence(y,[])
        if X[-1] == Y[-1]:
            z = set(X) & set(Y)
            for i in range(len(X)-1):
                res.add(tuple(sorted([X[i],X[i+1]])))
                if X[i+1] in z:
                    break
            for i in range(len(Y)-1):
                res.add(tuple(sorted([Y[i],Y[i+1]])))
                if Y[i+1] in z:
                    break
            res.add(tuple(sorted([x, y])))
        else:
            self.parents[y] = x

N, E = map(int, input().split())
tree = UnionFind(N)
res = set()
for _ in range(E):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    tree.union(x,y,res)

print(E - len(res))

Submission status: Wrong Answer

Solution code:
from collections import deque

N,M,*abf = map(int, open(0).read().split())
ab = [abf[i*2:i*2+2] for i in range(M)]
connected = [[] for _ in range(N+1)]
searched = [0] * (N+1)
ans = 0
for a, b in ab:
    connected[a].append(b)
    connected[b].append(a)
for i in range(1,N+1):
    if len(connected[i]) == 1:
        if searched[i] == 0:
            d = deque([i])
            while d:
                count = 0
                temp = d.popleft()
                if len(connected[temp]) > 2:
                    break
                else:
                    for edge in connected[temp]:
                        if searched[edge] == 0:
                            d.append(edge)
                            count += 1
                    searched[temp] = 1
                    if count == 1:
                        ans += 1
                    else:
                        break
print(ans)

Submission status: Wrong Answer

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

#各部屋の通じてる部屋番のリストを作る
l=[[] for _ in range(n)]
for i in range(m):
    a,b=s[i][0],s[i][1]
    l[a-1].append(b)
    l[b-1].append(a)

#複数ループができる場合を考慮しないdfs
def dfs(now,prev,visited):
    visited.append(now)#訪れた頂点を追加
    
    for edge in l[now-1]:#次に行ける場所を探索
        if edge==prev:continue#さっきいた所をスルー
        if edge in visited:#次行くところがすでに訪れた所の場合(ループができてしまうとき)
            count=len(visited)-visited.index(now)+2#ループの長さ
            print(m-count)#全辺からループぶんの長さを引く
            exit()
        
        if len(visited)==m:#ループがない場合
            print(len(visited))
            exit()

        dfs(edge,now,visited)#次の場所を同様に探索

print(dfs(1,0,[]))

Submission status: Wrong Answer

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

#各部屋の通じてる部屋番のリストを作る
l=[[] for _ in range(n)]
for i in range(m):
    a,b=s[i][0],s[i][1]
    l[a-1].append(b)
    l[b-1].append(a)
print(l)


#複数ループができる場合を考慮しないdfs
def dfs(now,prev,visited):
    visited.append(now)#訪れた頂点を追加
    
    for edge in l[now-1]:#次に行ける場所を探索
        if edge==prev:continue#さっきいた所をスルー
        if edge in visited:#次行くところがすでに訪れた所の場合(ループができてしまうとき)
            count=len(visited)-visited.index(now)+2#ループの長さ
            print(m-count)#全辺からループぶんの長さを引く
            exit()
        
        if len(visited)==m:#ループがない場合
            print(len(visited))
            exit()

        dfs(edge,now,visited)#次の場所を同様に探索

print(dfs(1,0,[]))

Submission status: Wrong Answer

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