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:
N, M = list(map(int, input().split()))
lines = [list(map(int, input().split())) for _ in range(M)]

graph = [[False] * N for _ in range(N)]
for a,b in lines:
    graph[a-1][b-1] = graph[b-1][a-1] = True

visited = [False for _ in range(N)]

def DFS(v):
    visited[v] = True
    for from_v in range(N):
        if not graph[v][from_v]:
            continue
        if not visited[from_v]:
            continue
        DFS(from_v)
    
cnt = 0
for i in range(M):
    pass_a, pass_b = lines[i]
    pass_a -= 1
    pass_b -= 1
    graph[pass_a][pass_b] = graph[pass_b][pass_a] = False
    DFS(pass_a)
    
    cnt += 1 if False in visited else 0
    
    visited = [False for _ in range(N)]
    graph[pass_a][pass_b] = graph[pass_b][pass_a] = True

print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M = map(int,input().split())
G = {}
for _ in range(M):
    a,b = map(int,input().split())
    if a not in G:
        G[a]=[]
    G[a].append(b)
    if b not in G:
        G[b]=[]
    G[b].append(a)
cnt = 0
for a in G:
    for b in G[a]:
        G[a].remove(b)
        G[b].remove(a)
        hist = [0 for _ in range(N+1)]
        stack = deque([1])
        while stack:
            cur = stack.popleft()
            hist[cur]=1
            for x in G[cur]:
                if hist[x]==0:
                    stack.append(x)
        if sum(hist)<N:
            cnt += 1
        G[a].append(b)
        G[b].append(a)
print(cnt//2)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
graph = [[0]*N for _ in range(N)]
Edge = []

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

def dfs(x):
  if(vis[x] == 1): return
  vis[x] = 1
  for i in range(N):
    if(graph[x][i] == 1):
      dfs(0)

ans = 0      
for i in range(M):
  graph[Edge[i][0]][Edge[i][1]] = 0
  graph[Edge[i][1]][Edge[i][0]] = 0
  vis = [0]*60
  dfs(0)
  for j in range(N):
    if(vis[j] == 0):
      ans += 1
      break
  graph[Edge[i][0]][Edge[i][1]] = 1
  graph[Edge[i][1]][Edge[i][0]] = 1
print(ans)

Submission status: Wrong Answer

Solution code:

# C
from collections import deque

def Connected(g, nodenum):
    visited = [False]*nodenum
    que = deque([])
    posi = 0
    que.append(posi)
    while que:
        visit = que.pop()
        visited[visit] = True
        for goto in g[visit]:
            if visited[goto]:
                continue
            que.append(goto)
    if all(visited):
        return True
    else:
        return False

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

ans = 0
for edge in edge_log:
    g[edge[0]].remove(edge[1])
    g[edge[1]].remove(edge[0])
    if not Connected(g, nodenum=n):
        ans += 1
    g[edge[0]].append(edge[1])
    g[edge[1]].append(edge[0])
print(ans//2)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m= map(int,input().split())
graph = [[]for _ in range(n)]
deg = [0 for _ in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    graph[x-1] += [y-1]
    graph[y-1] += [x-1]
    deg[x-1] += 1
    deg[y-1] += 1
q = deque([i for i in range(n) if deg[i] == 1])# 無向グラフのシンクは 1
seen = [False for _ in range(n)]
if len(deg) == n:print(n-1);exit()
while q:
    v = q.popleft()
    seen[v] = True
    for i in graph[v]:
        deg[i] -= 1
        if deg[i] == 1:
            q.append(i)
print(seen.count(True))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)

def dfs(v,p):
    global flag
    seen[v] = True

    for i in graph[v]:
        if i == p:continue
        if finished[i]:continue
        if seen[i] and not finished[i] :
            flag = i
            return
        dfs(i,v)
        if flag != -1:
            return
    finished[v] = True
def dfs2(v):
    seen[v] = True
    memo.append(v)

    for i in graph[v]:
        if i == flag:continue
        if seen[i]:continue
        dfs2(i)

n, m=map(int,input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    graph[x-1] += [y-1]
    graph[y-1] += [x-1]
ans = 0
for i in range(n):
    if len(graph[i]) == 1:
        seen = [False] * n
        finished = [False] * n
        memo = []
        flag = -1
        dfs(i,-1)
        if flag == -1:print(n-1);exit()
        else:
            dfs2(i)
            ans += len(memo)+1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)

def dfs(v,p):
    global flag
    seen[v] = True
    memo.append(v)

    for i in graph[v]:
        if i == p:continue
        if finished[i]:continue
        if seen[i] and not finished[i] :
            flag = i
            return
        dfs(i,v)
        if flag != -1:
            return
    finished[v] = True

n, m=map(int,input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    graph[x-1] += [y-1]
    graph[y-1] += [x-1]
ans = 0
for i in range(n):
    if len(graph[i]) == 1:
        seen = [False] * n
        finished = [False] * n
        memo = []
        flag = -1
        dfs(i,-1)
        if flag == -1:print(n-1);exit()
        else:
            for j in range(len(memo)):
                a = memo.pop()
                if a == flag:
                    ans += len(memo)
                    break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)

def dfs(v,p):
    global flag
    seen[v] = True
    memo.append(v)

    for i in graph[v]:
        if i == p:continue
        if finished[i]:continue
        if seen[i] and not finished[i] :
            flag = i
            return
        dfs(i,v)
        if flag != -1:
            return
    finished[v] = True

n, m=map(int,input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    graph[x-1] += [y-1]
    graph[y-1] += [x-1]
ans = 0
for i in range(n):
    if len(graph[i]) == 1:
        seen = [False] * n
        finished = [False] * n
        memo = []
        flag = -1
        dfs(i,-1)
        if flag == -1:print(n-1);exit()
        else:
            print(memo)
            for j in range(len(memo)):
                a = memo.pop()
                if a == flag:
                    ans += len(memo)
                    break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)

def dfs(v,p):
    global flag
    seen[v] = True
    memo.append(v)

    for i in graph[v]:
        if i == p:continue
        if finished[i]:continue
        if seen[i] and not finished[i] :
            flag = i
            return
        dfs(i,v)
        if flag != -1:
            return
    finished[v] = True
    memo.pop()

n, m = map(int,input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    graph[x-1] += [y-1]
    graph[y-1] += [x-1]
ans = 0
for i in range(n):
    if len(graph[i]) == 1:
        seen = [False] * n
        finished = [False] * n
        memo = []
        flag = -1
        dfs(i,-1)
        if flag == -1:print(n-1);exit()
        else:
            for j in range(len(memo)):
                a = memo.pop()
                if a == flag:
                    ans += len(memo)
                    break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)

def dfs(v,p):
    global flag
    seen[v] = True
    memo.append(v)

    for i in graph[v]:
        if i == p:continue
        if seen[i] == True and finished[i] == False:
            flag = i
            return
        dfs(i,v)
        if flag != -1:
            return
    finished[v] = True
    memo.pop()

n, m = map(int,input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    graph[x-1] += [y-1]
    graph[y-1] += [x-1]
ans = 0
for i in range(n):
    if len(graph[i]) == 1:
        seen = [False] * n
        finished = [False] * n
        memo = []
        flag = -1
        dfs(i,-1)
        if flag == -1:print(n-1);exit()
        else:
            for j in range(len(memo)):
                a = memo.pop()
                if a == flag:
                    ans += len(memo)
                    break
print(ans)

Submission status: Wrong Answer

Solution code:
def dfs(v,p):
    global flag
    seen[v] = True
    memo.append(v)

    for i in graph[v]:
        if i == p:continue
        if seen[i] == True and finished[i] == False:
            flag = i
            return
        dfs(i,v)
        if  flag != -1:
            return
    finished[v] = True
    memo.pop()

n, m = map(int,input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    graph[x-1] += [y-1]
    graph[y-1] += [x-1]
ans = 0
for i in range(n):
    if len(graph[i]) == 1:
        seen = [False] * n
        finished = [False] * n
        memo = []
        flag = -1
        dfs(i,-1)
        if flag == -1:print(n-1);exit()
        else:
            for j in range(len(memo)):
                a = memo.pop()
                if a == flag:
                    ans += len(memo)
                    break
print(ans)

Submission status: Wrong Answer

Solution code:
# Union Find 木
def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j


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

result = 0
for i in range(M):
    parent = [-1] * N
    for j in range(M):
        if j == i:
            continue
        unite(parent, ab[j][0], ab[j][1])
    if len([i for i in parent if i < 0]) != -1:
        result += 1
print(result)

Submission status: Wrong Answer

Solution code:
# pdf解法（隣接行列でグラフを管理して、DFSで連結判定する）
def dfs(x):
    if visited[x]:
        return
    visited[x] = True
    for i in range(N):
        # xに繋がっている頂点をたどっていく
        if graph[x][i]:
            dfs(i)


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

edge = []
graph = [[False]*N for _ in range(N)]   # 隣接行列
visited = [False]*N

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

ans = 0
for i, e in enumerate(edge):
    # 辺を取り除く
    graph[e[0]-1][e[1]-1] = False
    graph[e[1]-1][e[0]-1] = False

    # 初期化（全ての頂点を未訪問にする）
    for j in range(N):
        visited[j] = False

    # 任意の１つの頂点からDFS
    dfs(0)

    # 連結判定（訪問していない頂点がある＝非連結）
    bridge = True
    for j in range(N):
        if visited[j]:
            bridge=False
            break
#     for j in range(N):
#         if not visited[j]:
#             bridge = True
    if bridge:
        ans += 1

    # 取り除いた辺を戻す
    graph[e[0]-1][e[1]-1] = True
    graph[e[1]-1][e[0]-1] = True

print(ans)

Submission status: Wrong Answer

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

justified=True
while lists and justified:
    ans=0
    limit=0
    for i in range(1,n+1):
        cnt=0
        for _ in lists:
            if _[0]==i or _[1]==i:
                cnt+=1
                index=lists.index(_)     
        if cnt==1:
            ans+=1
            limit+=1
            del lists[index]        
        else:
            continue
    if limit==0:
        justified=False
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int, input().split())  # N頂点, M個の辺

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

# グラフを定義する
for i in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
    graph[b].append(a)


q = deque([0])  # 開始のノード
flag = [False] * N
count = [0] * N

# 幅優先で1回しか到達できない頂点を調べる（親もカウントするならちょうど二回か？）
while len(q):
    v = q.pop()

    flag[v] = True  # 部分木の根を到達済みにする
    for e in graph[v]:  # vを根にもつノード全てに操作をする
        # graphは子のみを格納するのではなく、そのノードから出ている辺を
        # 親とか子供とか関係なく全て格納してしまうため、親の方向に
        # 対して伝播をしないようにflagで管理する
        if flag[e]:  # 頂点eがvの親であればスルー
            continue
        count[e] += 1

        # この時点でeはvの子供であることが確定する
        q.append(e)

ans = M
for c in count:
    if c > 1:
        ans -= (c+1)

print(min(M, ans))

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int, input().split())  # N頂点, M個の辺

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

# グラフを定義する
for i in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
    graph[b].append(a)


q = deque([0])  # 開始のノード
flag = [False] * N
count = [0] * N

# 幅優先で1回しか到達できない頂点を調べる（親もカウントするならちょうど二回か？）
while len(q):
    v = q.pop()
    flag[v] = True  # 部分木の根を到達済みにする
    count[v] += 1
    for e in graph[v]:  # vを根にもつノード全てに操作をする
        # graphは子のみを格納するのではなく、そのノードから出ている辺を
        # 親とか子供とか関係なく全て格納してしまうため、親の方向に
        # 対して伝播をしないようにflagで管理する
        if flag[e]:  # 頂点eがvの親であればスルー
            continue

        # この時点でeはvの子供であることが確定する
        q.append(e)

ans = 0
for c in count:
    if c == 1:
        ans += 1
    else:
        ans -= c

print(min(M, ans))

Submission status: Wrong Answer

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

cnt=0
for x in e:
  l=list(range(n))
  for y in e:
    print('y',y)
    if y!=x:l=[l[y[0]-1] if l[i]==l[y[1]-1] else l[i] for i in range(n)]
    print('l',l)
  if len(set(l))!=1:cnt+=1
print(cnt)

Submission status: Wrong Answer

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

ans=0
for i in range(m):
  x=[ab[i][0]]
  for k in range(m):
    if k!=i and ab[k][0] in x:
      x.append(ab[k][1])
    elif k!=i and ab[k][1] in x:
      x.append(ab[k][0])
  if ab[i][1] not in x:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 12 10:38:04 2019
C - Bridge
実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 
300
 点
@author: justwah
use union find
"""

import sys
read = sys.stdin.readline

n, m = map(int, input().split())    # single line use regular input() is faster

l = [list(tuple(map(int, read().split()))) for i in range(m)]   #multiple lines use sys.stdin.readline faster

def root(x): #recursively find root for a node
    if parent[x] < 0: # if at root, return self
        return x
    else:
        parent[x] = root(parent[x])  # while searching rejoint queried node to a common parent for hierarchical tree
        return parent[x]
    
def merge(a, b):
    a = root(a)
    b = root(b)
    if rank[a] < rank[b]: # joint lower rank node to a higher rank one
        parent[a] = b
    else:
        parent[b] = a
        if rank[a] == rank[b]: # rank only change if two same rank node joined
            rank[a] +=1    
    return

score = 0

for i in range(m):
    parent = [-1]*(n+1)
    rank = [0]*(n+1)
    for j, (a, b) in enumerate(l[i:]): #iteraete from different starting point - test different "last bridge"
        a = root(a)
        b = root(b)
        if a != b:
            merge(a, b)
        else:
            if j == (len(l)-1):# if the last bridge is redundant, +1
                score += 1 

print(m-score)

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
a = [set() for _ in range(n+1)]
count = 0
for i in range(m):
    x,y = map(int,input().split())
    a[x].add(y)
    a[y].add(x)
    a[0].add((x,y))
    a[0].add((y,x))
for i in range(1, n + 1):
    if len(a[i]) == 1:
        count += 1
        continue
    elif len(a[i]) >= 3:
        continue
    if tuple(a[i]) in a[0]:
        continue
    count += 1
if count == n:
    count -= 1
print(count)

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
a = [set() for _ in range(n+1)]
count = 0
for i in range(m):
    x,y = map(int,input().split())
    a[x].add(y)
    a[y].add(x)
    a[0].add((x,y))
    a[0].add((y,x))
for i in range(1, n + 1):
    print(a[i])
    if len(a[i]) == 1:
        count += 1
        continue
    elif len(a[i]) >= 3:
        continue
    if tuple(a[i]) in a[0]:
        continue
    count += 1
if count == n:
    count -= 1
print(count)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
list_a = []
list_b = []
g = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    list_a.append(a-1)
    list_b.append(b-1)
    g[a-1][b-1] = 1
    g[b-1][a-1] = 1


def dfs(v):
    seen[v] = 1 #vを訪問済みにする
    ret = 1
    for v2 in range(N):
        if g[v][v2] == 1 and seen[v2] == 0:
            print(v,v2,seen,"####")
            dfs(v2)
    if seen == [1] * N: #すべての頂点を訪問したらretを返す
        ret = 0

    return ret

ans = 0
for i in range(M):
    seen = [0] * N
    g[list_a[i]][list_b[i]] = 0
    g[list_b[i]][list_a[i]] = 0
    ans += dfs(0)
    g[list_a[i]][list_b[i]] = 1
    g[list_b[i]][list_a[i]] = 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
edges=[list(map(lambda x:int(x)-1,input().split())) for _ in range(m)]
ans=0
for x in edges:
    C=list(range(n))
    for y in edges:
        if y==x: continue
        for i in range(n):
            if C[i]==C[y[1]]: C[i]=C[y[0]:y[0]+1][0]
    if len(set(C))!=1: ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
edges=[list(map(lambda x:int(x)-1,input().split())) for _ in range(m)]
ans=0
for x in edges:
    C=list(range(n))
    for y in edges:
        if y==x: continue
        for i in range(n):
            if C[i]==C[y[1]]: C[i]=C[y[0]]
    if len(set(C))!=1: ans+=1
print(ans)

Submission status: Wrong Answer

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

	def find(self, x):
		if(self.root[x] < 0):
			return x
		else:
			self.root[x] = self.find(self.root[x])
			return self.root[x]
			
	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if(x == y):
			return 0
		elif(self.rank[x] > self.rank[y]):
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if(self.rank[x] == self.rank[y]):
				self.rank[y] += 1

	def size(self, x):
		return -self.root[self.find(x)]
		
n,m,*l = map(int,open(0).read().split())
edges = [(a,b)for a,b in zip(l[::2],l[1::2])]
ans = 0
for i in range(n):
	uf = UnionFind(n)
	for j,(a,b) in enumerate(edges):
		if i==j:
			continue
		else:
			uf.unite(a,b)
	ans += uf.size(a)<n
print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
    n,m=map(int,input().split())
    edges=[list(map(lambda x:int(x)-1,input().split())) for _ in range(m)]
    ans=0
    for x in edges:
        C=list(range(n))
        for y in edges:
            if y==x: continue
            for i in range(n):
                if C[i]==C[y[1]]: C[i]=C[y[0]]
        if len(set(C))!=1: ans+=1
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    n,m=map(int,input().split())
    edges=[list(map(lambda x:int(x)-1,input().split())) for _ in range(m)]
    ans=0
    for x in edges:
        C=list(range(n))
        for y in edges:
            if y==x: continue
            for i in range(n):
                if C[i]==C[y[1]]: C[i]=C[y[0]]
        if len(set(C))>1: ans+=1
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
import collections 
import sys,heapq,bisect,math,itertools,string,queue,datetime
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

n,m = inpl()
t = []
cnt = [0] * (n+1)
ans = 0
for i in range(m):
    a,b = inpl()
    t.append([a,b])
    cnt[a] += 1
    cnt[b] += 1
# print(cnt)
while m:
    flag = False
    for i in range(1,n+1):
        if cnt[i] == 1:
            flag = True
            cnt[i] = 0
            ans += 1
            for j in t:
                if j[0] == i:
                    cnt[j[1]] -= 1
                    t.remove(j)
            break
    if flag == False:
        break
    m -= 1
        # print(i,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import collections 
import sys,heapq,bisect,math,itertools,string,queue,datetime
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

n,m = inpl()
t = []
cnt = [0] * (n+1)
ans = 0
for i in range(m):
    a,b = inpl()
    t.append([a,b])
    cnt[a] += 1
    cnt[b] += 1
# print(cnt)
flag = True
while flag:
    flag = False
    for i in range(1,n+1):
        if cnt[i] == 1:
            flag = True
            cnt[i] = 0
            ans += 1
            for j in t:
                if j[0] == i:
                    cnt[j[1]] -= 1
                    t.remove(j)
            break
        # print(i,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
count = 0
A = []
B = []
for i in range(m):
  a,b = map(int,input().split())
  A.append(a)
  B.append(b)
def degreesOfSeparation(list_a,list_b,pop_edge):
    graph = {}
    for i in range(m):
      if i == pop_edge:
        pass
      else:
        a,b = list_a[i],list_b[i]
        if a not in graph:
          graph[a] = [b]
        else:
          graph[a] += [b]
        if b not in graph:
          graph[b] = [a]
        else:
          graph[b] += [a]
    start = 1
    if start not in graph:
        return -1
    visited = set()
    frontier = set()
    degrees = 0
    visited.add(start)
    frontier.add(start)
    while len(frontier) > 0:
        degrees += 1
        newfront = set()
        for g in frontier:
            for next in graph[g]:
                if next not in visited:
                    visited.add(next)
                    newfront.add(next)
            frontier = newfront
    return len(visited)
for x in range(n):
  if degreesOfSeparation(A,B,x) != n:
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
V,E=map(int,input().split())
edges=[set() for i in range(V)]
for i in range(E):
    a,b=map(int,input().split())
    edges[a-1].add(b-1)
    edges[b-1].add(a-1)
for i in range(V):
    print(len({n for v in edges[i] for n in edges[v] if not n in edges[i] and n!=i}))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[0]*n
xx=[]
yy=[]
for i in range(m):
	x,y=map(int,input().split())
	a[x-1]+=1
	a[y-1]+=1
	xx.append(x)
	yy.append(y)
ans=0
b=[]
while 1 in a:
	for i in range(n):
		if a[i]==1:
			b.append(i)
	for j in range(len(b)):
		for k in range(m):
			if xx[k]==b[j]+1:
				a[yy[k]-1]-=1
			elif yy[k]==b[j]+1:
				a[xx[k]-1]-=1
		a[b[j]]=0
for i in range(n):
	if a[i]<=0:
		ans+=1
if ans==n:
	ans-=1
print(ans)

Submission status: Wrong Answer

Solution code:
import copy

def j(n):
    if n:print("Yes")
    else:print("No")
    exit(0)
rem = 10 ** 9 + 7

"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def ipmultiplerow(n):
    a = []
    for i in range(n):
        a.append(ip())
    return a
def printrow(a):
    for i in a:
        print(i)

n,m = ips()
a = []
s = 0
for i in range(m):
    x,y = ips()
    a.append([x,y])
connection = [[] for i in range(n+1)]
for i in range(m):
    [x,y] = a[i]
    connection[x].append(y)
    connection[y].append(x)
for i in range(1,n+1):
    if len(connection[i]) == 1:
        temp = connection[i][0]
        d = connection[temp].index(i)
        connection[temp].pop(d)
        s+=1
        connection[i].pop(0)
print(s)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def solve(graph, m, brg):
  ans = 0
  for i in range(m):
    if len(graph[i]) == 1 and set(sorted([graph[i][0], i])) not in brg:
      graph[graph[i][0]].remove(i)
      brg.append(set(sorted([graph[i][0], i])))
      ans += 1
  return ans

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

brg = []
print(solve(graph, m, brg))

Submission status: Wrong Answer

Solution code:
import itertools
from collections import defaultdict

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

brg = []
ans = 0
for i in range(m):
  if len(graph[i]) == 1 and set(sorted([graph[i][0], i])) not in brg:
    graph[graph[i][0]].remove(i)
    brg.append(set(sorted([graph[i][0], i])))
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ab = [[int(i) for i in input().split()] for j in range(m)]

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1 for _ in range(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
            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_check(self, x, y):
        return self.find(x) == self.find(y)

bridge = 0

for i in range(m):
    ins = UnionFind(n)
    for j in range(m):
        if j == i:
            continue
        if not ins.same_check(ab[j][0],ab[j][1]):
            ins.union(ab[j][0],ab[j][1])
        #print(ins.size[ins.find(ab[0][0])],j)
        
    #print(ins.size[ins.find(ab[0][0])])
    if ins.size[ab[0][0]] != n:
        bridge += 1
        
print(bridge)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ab = [[int(i) for i in input().split()] for j in range(m)]

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1 for _ in range(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
            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_check(self, x, y):
        return self.find(x) == self.find(y)

bridge = 0

for i in range(m):
    ins = UnionFind(n)
    for j in range(m):
        if j == i:
            continue
        ins.union(ab[j][0],ab[j][1])
        
    #print(ins.size[ab[0][0]])
    if ins.size[ab[0][0]] != n:
        bridge += 1
        
print(bridge)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
min = N-1
ans = min-((M-min)*2)
if ans < 0:
  ans = 0
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
min = N-1
print(min-((M-min)*2))