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:
import numpy as np
import math

# K = int(input())
# N, K = map(int, input().split())
# A = list(map(int, input().split()))

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

E = np.zeros((N, N), dtype=int)

for m in range(M):
    s, t = map(int, input().split())
    s = s-1
    t = t-1
    E[s][t] = 1
    E[t][s] = 1

# print(E)
    
bridges = set()
TIME = 0
    
def bridgeN(n, visited, parent, low, dis):
    global TIME
    visited[n] = 1
    dis[n] = TIME
    low[n] = TIME
    TIME += 1

    # print('time', TIME)

    # print('n=', n)
    # print('visited=', visited)
    
    for v in range(N):
        if E[n][v] == 0:
            continue
        if visited[v] == 1:
            if v != parent[n]:
                low[n] = min(low[n], dis[v])
            continue

        print('visited[', v, ']=', visited[v])
        
        parent[v] = n
        bridgeN(v, visited, parent, low, dis)

        low[n] = min(low[n], low[v])

        if low[v] > dis[n]:
            if v <= n:
                bridges.add((v, n))
            else:
                bridges.add((n, v))
                

def bridge(E):
    visited = np.zeros(N, dtype=int)
    dis = np.full_like(visited, N*N*10)
    low = np.full_like(visited, N*N*10)
    parent = np.full_like(visited, -1)

    for n in range(N):
        if visited[n] == 0:
            bridgeN(n, visited, parent, low, dis)

bridge(E)
nBridges = len(bridges)
# print(bridges)

print(nBridges)

Submission status: Wrong Answer

Solution code:
f = lambda: list(map(int,input().split()))
f_ = lambda: [int(x)-1 for x in input().split()]


class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[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.parent[x] = y
        else:
            self.parent[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 = f()
u = UnionFind(n)
e = []
for _ in range(m):
    e.append(f_())

ans = 0
for edge in e:
    e.remove(edge)
    for a,b in e:
        u.unite(a,b)

    f = False
    k = u.find(0)
    for i in range(n):
        if u.find(i) is not k:
            f = True
            break
    if f:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
a=[0 for i in range(M)]
b=[0 for i in range(M)]
for i in range(M):
    a[i],b[i]=map(int,input().split())
    a[i]-=1
    b[i]-=1
par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
def init(n):
    for i in range(N):
        par[i]=i
        rnk[i]=0
def find(x):
    if par[x]==x:
        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
    if (rnk[x]<rnk[y]):
        par[x]=y
    else:
        par[y]=x
        if(rnk[x]==rnk[y]):
            rnk[x]+=1
def same(x,y):
    return find(x)==find(y)
ans=0
for i in range(M):
    init(N)
    for j in range(M):
        if i==j:
            continue
        unite(a[j],b[j])
    flag=0
    for j in range(N):
        if find(j)!=0:
            flag=1
            break
    if flag==1:
        ans+=1
print(ans)

Submission status: Wrong Answer

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

a_counts = [0]*n
for a_i in sum(a, []):
	a_counts[a_i-1] += 1

bridge_count = 0
for i, count in enumerate(a_counts):
	if count == 1:
		p = i+1
		while a_counts[p-1] <= 2: 
			for j, a_i in enumerate(a):
				if a_i and p in a_i and a_counts[p-1] <= 2:
					a_i.remove(p)
					p = a_i[0]
					a[j] = None
					bridge_count += 1
			break
			
print(bridge_count)

Submission status: Wrong Answer

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

a_counts = [0]*n
for a_i in sum(a, []):
	a_counts[a_i-1] += 1

bridge_count = 0
for i, count in enumerate(a_counts):
	if count == 1:
		p = i+1
		while a_counts[p-1] <= 2: 
			for j, a_i in enumerate(a):
				if a_i and p in a_i and a_counts[p-1] <= 2:
					print(a_i)
					a_i.remove(p)
					print(a_i)
					p = a_i[0]
					a[j] = None
					bridge_count += 1
			break
			
print(bridge_count)

Submission status: Wrong Answer

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

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

if N==M+1:
    print(M)
    exit()
    
count=0
for i in range(M-1):
    if a[i+1][0] == a[i][0] or a[i+1][1] == a[i][1]:
       count+=1
print(M-1-count)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
d={}
for i in range(m):
    a,b=map(int,input().split())
    if a in d:
        d[a]+=1
    else:
        d[a]=1
    if b in d:
        d[b]+=1
    else:
        d[b]=1
ans=0
for i in d:
    if d[i]<3:
        ans+=d[i]
print(ans//2)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
t=[0]*N
u=[]
s=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    s[a-1].append(b-1)
    s[b-1].append(a-1)
for i in range(len(s[0])):
    u.append((s[0][i],0))
t[0]+=1
while u:
    (a,b)=u[0]
    if t[a]==0:
        for i in s[a]:
            if i!=b:
                u.append((i,a))
    t[a]+=1    
    u.pop(0) 
print(t.count(1)-1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
arr = [[ 0 for i in range(N) ] for i in range(N)]
res = 0

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

for i in range(N):
    co = 0
    for j in range(N):
        if arr[i][j] == 1:
            co += 1
            tmp1, tmp2 = i, j
            
    if co == 1:
        arr[tmp1][tmp2] = 0
        arr[tmp2][tmp1] = 0
        res += 1
        
for j in range(N):
    co = 0
    for i in range(N):
        if arr[i][j] == 1:
            co += 1
            
    if co == 1:
        res += 1

print(res)

Submission status: Wrong Answer

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

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

b = [[0 for i in range(n)] for j in range(n)]
for i in a:
    b[i[0]][i[1]] = 1
    b[i[1]][i[0]] = 1

ans = 0
for i in b:
    if sum(i) <= 2:
        ans += sum(i)
if n == 3 and m == 3:
    print(0)
else:
    print(ans//2)

Submission status: Wrong Answer

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

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

b = [[0 for i in range(n)] for j in range(n)]
for i in a:
    b[i[0]][i[1]] = 1
    b[i[1]][i[0]] = 1


c = [i+1 for i in range(n-1)]
ans = 0
for i in itertools.permutations(c,n-1):
    j = [0]
    j += i
    count = 0
    for i in range(n-1):
        if b[j[i]][j[i+1]] == 1:
            count += 1
            if count == n-1:
                ans += 1
                count = 0
        else:
            break
print(ans)

Submission status: Wrong Answer

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

from pprint import pprint

l=[[False for _ in range(n)] for _ in range(n)]
v=[True for _ in range(n)]
for a,b in ab:
    l[b-1][a-1], l[a-1][b-1]=True,True
def dfs(x,t,v,j,m,n):
    j+=1
    if j<n+m:
        v[x]=False
        for i in range(1,n):
            if v[i]:
                if t[x][i]:
                    dfs(i,t,v,j,m,n)
import copy

ans=0
for i in range(m):
    j=0
    t=copy.deepcopy(l)
    t[ab[i][1]-1][ab[i][0]-1],t[ab[i][0]-1][ab[i][1]-1]=False,False
    v=[True for _ in range(n)]
    if i!=0:
        dfs(ab[0][0]-1, t, v, j, m,n)
    else:
        dfs(ab[1][0]-1, t, v, j, m,n)
        
    z=False
    for x in v:
        if x:
            z=True
    if z:
        ans+=1
print(ans)

Submission status: Wrong Answer

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

from pprint import pprint

l=[[False for _ in range(n)] for _ in range(n)]
v=[True for _ in range(n)]
for a,b in ab:
    l[b-1][a-1], l[a-1][b-1]=True,True
def dfs(x,t,v,j,m,n):
    j+=1
    if j<=m:
        v[x]=False
        for i in range(1,n):
            if v[i]:
                if t[x][i]:
                    dfs(i,t,v,j,m,n)
import copy

ans=0
for i in range(m):
    j=0
    t=copy.deepcopy(l)
    t[ab[i][1]-1][ab[i][0]-1],t[ab[i][0]-1][ab[i][1]-1]=False,False
    v=[True for _ in range(n)]
    if i!=0:
        dfs(ab[0][0]-1, t, v, j, m,n)
    else:
        dfs(ab[1][0]-1, t, v, j, m,n)
        
    z=False
    for x in v:
        if x:
            z=True
    if z:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
# input
N, M = map(int, input().split())
edge_lst = [list(map(int, input().split())) for i in range(M)]

adj_matrix = {} # グラフを辺列挙 -> 隣接行列に変換
for i in range(1, N + 1):
    adj_lst = []
    for j in range(M):
        if edge_lst[j][0] == i:
            adj_lst.append(edge_lst[j][1])
        if edge_lst[j][1] == i:
            adj_lst.append(edge_lst[j][0])
    adj_matrix[i] = adj_lst

# root: 葉を探索中の根
# next: 次に探索される葉
# count: 探索回数
# order[1,...,N]: 頂点iが探索された順番
# low[1,...,N]: 頂点iから訪問可能な頂点のうち、最も上にある頂点の探索順

def dfs_bridge(graph, root, next, count, low, order, bridges): # graph is represented by adj. matrix
    count += 1
    order[next] = count
    low[next] = order[next]

    for w in graph[next]: # neighbors of v
        if order[w] == -1: # if w is not visited yet
            dfs_bridge(graph, next, w, count, low, order, bridges)

            low[next] = min(low[next], low[w])
            if low[w] == order[w]: # 頂点w以降から頂点v以前に戻れない
                bridges.append((next, w))
        elif w != root: # 一つ前の頂点（自明に戻れる頂点）より前に戻れる場合
            low[next] = min(low[next], order[w])

def get_bridges(graph):
    bridges = []
    count = 0
    low = {n: -1 for n in graph.keys()}
    order = low.copy()

    for n in graph.keys():
        dfs_bridge(graph, n, n, count, low, order, bridges)
    
    return(bridges) # List of [node, node] lists for all bridges in G
            
ans = get_bridges(adj_matrix)
print(ans)

Submission status: Wrong Answer

Solution code:
# input
N, M = map(int, input().split())
edge_lst = [list(map(int, input().split())) for i in range(M)]

adj_matrix = {} # グラフを辺列挙 -> 隣接行列に変換
for i in range(1, N + 1):
    adj_lst = []
    for j in range(M):
        if edge_lst[j][0] == i:
            adj_lst.append(edge_lst[j][1])
        if edge_lst[j][1] == i:
            adj_lst.append(edge_lst[j][0])
    adj_matrix[i] = adj_lst

# root: 葉を探索中の根
# next: 次に探索される葉
# count: 探索回数
# order[1,...,N]: 頂点iが探索された順番
# low[1,...,N]: 頂点iから訪問可能な頂点のうち、最も上にある頂点の探索順

def dfs_bridge(graph, root, next, count, low, order, bridges): # graph is represented by adj. matrix
    count += 1
    order[next] = count # 頂点vが探索された順番
    low[next] = order[next] # 頂点vから訪問可能な頂点のうち、最も番号が小さい頂点の番号

    for w in graph[next]: # neighbors of v
        if order[w] == -1: # if w is not visited yet
            dfs_bridge(graph, next, w, count, low, order, bridges)

            low[next] = min(low[next], low[w])
            if low[w] == order[w]: # 頂点w以降から頂点v以前に戻れない
                bridges.append([next, w])
        elif w != root:
            low[next] = min(low[next], order[root])

def get_bridges(graph):
    bridges = []
    count = 0
    low = {n: -1 for n in graph.keys()}
    order = low.copy()

    for n in graph.keys():
        dfs_bridge(graph, n, n, count, low, order, bridges)
    
    return(bridges) # List of [node, node] lists for all bridges in G
            
ans = get_bridges(adj_matrix)
print(len(ans))

Submission status: Wrong Answer

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

uf = []
for i in range(n):
	uf.append(i)

count = 0
for i in range(m):
	f,t = map(int,raw_input().split())
	f -= 1
	t -= 1
	if uf[f] == uf[t]:
		count -= 2
	else :
		uf[t] = f
		count += 1

print count

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
edges = [[] for _ in range(N + 1)]
res = 0
passed_nodes = set()
thsh = 3

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

if len(edges) - 1 == 3:
    thsh = 2

for e in edges[1:-1]:
    if len(e) < thsh:
        res += 1

print(res)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
edges = [[] for _ in range(N + 1)]
res = 0
passed_nodes = set()
thsh = 3

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

if len(edges) - 2 == 3:
    thsh = 2

for e in edges[1:-1]:
    if len(e) < thsh:
        res += 1

print(res)

Submission status: Wrong Answer

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

B = []
for i in range(n+1):
    onel = []
    for j in range(n+1):
        onel.append(0)
    B.append(onel)
    
visited_checklist = []

input_node = []

for i in range(n+1):
    visited_checklist.append(i)
    
for k in range(m):
    ai,bi = map(int,input().split())
    B[ai][bi] = 1
    B[bi][ai] = 1
    input_node.append([ai,bi])
    
def DFS(node):
    l[node] = 0
    for j in range(n+1):
        if X[node][j] == 1 or X[j][node] == 1 :
            l[j] = 0 
            X[node][j] = 0
            X[j][node] = 0
            DFS(j)
        if X[node][j] == 0 or X[j][node] == 0:
            continue
    

    
count = 0

for i in input_node:
    X = B
    X[i[0]][i[1]] = 0
    X[i[1]][i[0]] = 0
    l = visited_checklist
    DFS(1)
    if max(l) != 0:
        count += 1
print(count)

Submission status: Wrong Answer

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

B = []
for i in range(n+1):
    onel = []
    for j in range(n+1):
        onel.append(0)
    B.append(onel)
    
visited_checklist = []

input_node = []

for i in range(n+1):
    visited_checklist.append(i)
    
for k in range(m):
    ai,bi = map(int,input().split())
    B[ai][bi] = 1
    B[bi][ai] = 1
    input_node.append([ai,bi])
    
def DFS(node):
    l[node] = 0
    for j in range(n+1):
        if X[node][j] == 1 :
            l[j] = 0 
            X[node][j] = 0
            X[j][node] = 0
            DFS(j)
        if X[node][j] == 0 or X[j][node] == 0:
            continue
        if l[j] == 0:
            continue
    

    
count = 0

for i in input_node:
    X = B
    X[i[0]][i[1]] = 0
    X[i[1]][i[0]] = 0
    l = visited_checklist
    DFS(1)
    if max(l) != 0:
        count += 1
print(count)

Submission status: Wrong Answer

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

B = []
for i in range(n+1):
    onel = []
    for j in range(n+1):
        onel.append(0)
    B.append(onel)
    
visited_checklist = []

input_node = []

for i in range(n+1):
    visited_checklist.append(i)
    
for k in range(m):
    ai,bi = map(int,input().split())
    B[ai][bi] = 1
    B[bi][ai] = 1
    input_node.append([ai,bi])
    
def DFS(node):
    l[node] = 0
    for j in range(n+1):
        if X[node][j] == 1 or X[j][node] == 1:
            l[j] = 0 
            X[j][node] = 0
            X[node][j] = 0
            DFS(j)
        if X[node][j] == 0 or X[j][node] == 0:
            continue
        if l[node] == 0:
            continue

    
count = 0

for i in input_node:
    X = B
    X[i[0]][i[1]] = 0
    X[i[1]][i[0]] = 0
    l = visited_checklist
    DFS(1)
    if max(l) != 0:
        count += 1
print(count)

Submission status: Wrong Answer

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

B = []
for i in range(n+1):
    onel = []
    for j in range(n+1):
        onel.append(0)
    B.append(onel)
    
visited_checklist = []

input_node = []

for i in range(n+1):
    visited_checklist.append(i)
    
for k in range(m):
    ai,bi = map(int,input().split())
    B[ai][bi] = 1
    B[bi][ai] = 1
    input_node.append([ai,bi])
    
def DFS(node,l,X):
    l[node] = 0
    for j in range(n+1):
        if X[node][j] == 1 or X[j][node] == 1:
            l[j] = 0 
            X[j][node] = 0
            X[node][j] = 0
            DFS(j,l,X)
        if X[node][j] == 0 or X[j][node] == 0:
            continue
        if l[node] == 0:
            continue

    
count = 0

for i in input_node:
    S = B
    S[i[0]][i[1]] = 0
    S[i[1]][i[0]] = 0
    ll = visited_checklist
    DFS(1,ll,S)
    if max(ll) != 0:
        count += 1
print(count)

Submission status: Wrong Answer

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

M = []
for i in range(n+1):
    onel = []
    for j in range(n+1):
        onel.append(0)
    M.append(onel)
    
visited_checklist = []

input_node = []

for i in range(n+1):
    visited_checklist.append(i)
    
for k in range(m):
    ai,bi = map(int,input().split())
    M[ai][bi] = 1
    M[bi][ai] = 1
    input_node.append([ai,bi])
    
def DFS(node,l,X):
    l[node] = 0
    for j in range(n+1):
        if M[node][j] == 1 or M[j][node] == 1:
            l[j] = 0 
            M[j][node] = 0
            M[node][j] = 0
            DFS(node,l,X)
        else:
            return 1
        
    if max(l) == 0:
        return 0
    
count = 0

for i in input_node:
    S = M
    S[i[0]][i[1]] = 0
    S[i[1]][i[0]] = 0
    count = count + DFS(1,visited_checklist,S)
    
print(count)

Submission status: Wrong Answer

Solution code:
import copy

def m():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N+1)]
    E = []
    visited = []
    for i in range(M):
        a, b = map(int, input().split())
        E.append((a,b))

    for m in range(M):
        a, b = E[m]
        graph[a].append(b)
        graph[b].append(a)


    def dfs(v, g):
        if visited[v] == True:
            return
        visited[v] = True
        for i in g[v]:
            dfs(i,g)


    def is_all_visited(v):
        for i in range(1, N):
            if v[i]:
                pass
            else:
                return False
        return True
    ans = 0
    for j in range(M):
        y,z = E[j]
        visited = [False] * (N + 1)
        tmp = copy.deepcopy(graph)
        tmp[y].remove(z)
        tmp[z].remove(y)
        dfs(1,tmp)
        if is_all_visited(visited):
            pass
        else:
            ans +=1

    return ans


print(m())

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import numpy as np

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

adjacent = np.zeros((N, N))
for l in L:
    adjacent[l[0] - 1, l[1] - 1] = 1
    adjacent[l[1] - 1, l[0] - 1] = 1
print(adjacent, end='\n\n')

pre = [-1 for _ in range(N)]
low = [-1 for _ in range(N)]
v = k = 0
ans = 0


def dfs(v, pre, low, k, parent):
    global ans
    pre[v] = k
    k += 1
    low[v] = pre[v]
    for to, n in enumerate(adjacent[v, :]):
        if n == 1:
            if pre[to] == -1:
                # destination has not been visited
                # visit destination and update low[v]
                # print('-----', v, '-------')
                # print(pre, low)
                low[v] = min(low[v], dfs(to, pre, low, k, v))
                if low[to] == pre[to]:
                    ans += 1
                    # print(v + 1, to + 1)
            else:
                # visited
                if to == parent:
                    pass
                else:
                    low[v] = min(low[v], low[to])

    return low[v]


dfs(v, pre, low, k, -1)
# print(pre, low)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
path=[[0]*n for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    path[a-1][b-1]=1
    path[b-1][a-1]=1

def connected(v,visited):
    visited[v]=1
    if sum(visited)==n:
        visited=[0]*n
        return 1
    count=0
    for i in range(n):
        if path[v][i]==1 and visited[i]==0:#行ったことある点にはいかない
            visited[i]=1#行ったことを記録
            count+=connected(i,visited)
    visited=[0]*n
    return count
bridge=0

for x in range(n):
    for y in range(x+1,n):
        if path[x][y]==1:
            visited=[0]*n
            path[x][y]=0
            if not connected(x,visited):
                print(x,y)
                bridge+=1
            path[x][y]=1
print(bridge)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
graph = []
for i in range(M):
  l,r = map(int,input().split())
  graph.append((l,r))
count = 0
for j in range(M):
  queue = [graph[j][0]]
  check = [graph[j][0]]
  while len(queue) > 0:
    for k in range(M): 
      if graph[k][0] == queue[0] and graph[k][1] not in check and k != j:
        queue.append(graph[k][1])
        check.append(graph[k][1])
      elif graph[k][1] == queue[0] and graph[k][0] not in check and k != j:
        queue.append(graph[k][0])
        check.append(graph[k][0])
    queue.pop(0)
    if len(check) == N:
      count += 1
print(M - count)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
graph = []
for i in range(M):
  l,r = map(int,input().split())
  graph.append((l,r))
count = 0
for j in range(M):
  queue = [graph[j][0]]
  check = []
  while len(queue) > 0:
    check.append(queue[0])
    for k in range(M): 
      if graph[k][0] == queue[0] and graph[k][1] not in check and k != j:
        queue.append(graph[k][1])
      elif graph[k][1] == queue[0] and graph[k][0] not in check and k != j:
        queue.append(graph[k][0])
    queue.pop(0)
    if len(check) == N:
      count += 1

print(M - count)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
graph = []
for i in range(M):
  l,r = map(int,input().split())
  graph.append((l,r))
count = 0
for j in range(M):
  queue = [graph[0][0]]
  check = []
  while len(queue) > 0:
    now = queue[0]
    check.append(queue[0])
    for k in range(M): 
      if graph[k][0] == now and graph[k][1] not in check and k != j:
        queue.append(graph[k][1])
      elif graph[k][1] == now and graph[k][0] not in check and k != j:
        queue.append(graph[k][0])
    queue.pop(0)
  if len(check) == N:
    count +=1
print(M - count)

Submission status: Wrong Answer

Solution code:
def connect(blist, a):
	x = []
	for i in range(len(blist)):
		if blist[i][0]==a:
			x.append(blist[i][1])
		elif blist[i][0]>a:
			break
	for j in range(len(blist)):
		if blist[j][1]==a:
			x.append(blist[j][0])
	return(x)

n,m = (int(i) for i in input().split())
y = [[int(i) for i in input().split()] for i in range(m)]
answer = m
for j in range(len(y)):
	y2,z = [],set()
	for k in range(1,n+1):
		y2.append(connect(y[:j]+y[min(j+1,len(y)):],k))
	for j2 in y2[y[j][0]-1]:
		z.add(j2)
	num = 0
	while y[j][1] not in z and len(z) != num:
		num,z2 = len(z),list(z)
		for k in z2:
			for k2 in y2[k-1]:
				z.add(k2)
	if y[j][1] in z:
		answer -= 1
print(answer)

Submission status: Wrong Answer

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

dotlist = [[] for i in range(N)]
sidlist = []
count = 0 

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

if (N -1) == M:
    print(M)
    exit()

def check(anum,bnum,cnum):
    for i in dotlist[cnum - 1]: 
        if (anum == cnum and i == bnum) or (bnum == cnum and i == anum):
            pass
        elif donedot[i - 1] == False:
            donedot[i - 1] = True
            check(anum,bnum,i)

donedot = None

for m in range(M):
    donedot = [False for i in range(M)]
    a,b = sidlist[m]
    check(a,b,1)
    TorF = True
    for i in donedot:
        TorF  = TorF and i
    if  not TorF:
        count += 1

print(count)

Submission status: Wrong Answer

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

dotlist = [[] for i in range(N)]
sidlist = []
count = 0 

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

if N -1 == M:
    print(0)
    exit()

def check(anum,bnum,cnum):
    for i in dotlist[cnum - 1]: 
        if (anum == cnum and i == bnum) or (bnum == cnum and i == anum):
            pass
        elif donedot[i - 1] == False:
            donedot[i - 1] = True
            print(cnum,i)
            check(anum,bnum,i)

donedot = None

for m in range(M):
    donedot = [False for i in range(M)]
    a,b = sidlist[m]
    check(a,b,1)
    TorF = True
    for i in donedot:
        TorF  = TorF and i
    if  not TorF:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
N,M = list(map(int,input().split()))
set =[]
s=int(N*(N+1)/2)
count = 0
for i in range(M):
    set.append(list(map(int,input().split())))

def BFS(L):
    while L:
        start = L.pop(0)
        visited.append(start)
        for item in lis[start-1]:
            if (item not in visited) and (item not in L):
                L.append(item)
    global check
    if sum(visited) == s:
        return True
    else:
        return False



for num in range(N):
    visited = []
    lis = [[] for i in range(N)]
    for i,item in enumerate(set):
        if i == num:
            continue
        x,y = item
        lis[x-1].append(y)
        lis[y-1].append(x)
    if not BFS([1]):
        count += 1
print (count)

Submission status: Wrong Answer

Solution code:
N,M = list(map(int,input().split()))
set =[]
s=int(N*(N+1)/2)
count = 0
for i in range(M):
    set.append(list(map(int,input().split())))

def BFS(L):
    start = L.pop(0)
    visited.append(start)
    for item in lis[start-1]:
        if (item not in visited) and (item not in L):
            L.append(item)
    if L:
        BFS(L)
    else:
        global check
        if sum(visited) == s:
            check = 1
        else:
            check = 0



for num in range(N):
    visited = []
    lis = [[] for i in range(N)]
    que = [1]
    for i,item in enumerate(set):
        if i == num:
            continue
        x,y = item
        lis[x-1].append(y)
        lis[y-1].append(x)
    check = -1
    BFS(que)
    if check == 0:
        count += 1
print (count)

Submission status: Wrong Answer

Solution code:
N,M = list(map(int,input().split()))
set =[]
s=int(N*(N+1)/2)
count = 0
for i in range(M):
    set.append(list(map(int,input().split())))

def BFS(L):
    start = L.pop(0)
    visited.append(start)
    for item in lis[start-1]:
        if (item not in visited) and (item not in L):
            L.append(item)
    if L:
        BFS(L)
    else:
        global check
        if sum(visited) == s:
            check = 1
        else:
            check = 0



for num in range(N):
    visited = []
    lis = [[] for i in range(N)]
    que = [1]
    for i,item in enumerate(set):
        if i == num:
            continue
        x,y = item
        lis[x-1].append(y)
        lis[y-1].append(x)
    check = -1
    BFS(que)
    print (check)
    if check == 0:
        count += 1
print (count)

Submission status: Wrong Answer

Solution code:
inp = input().split(" ")
num_vertex = int(inp[0])
num_edge = int(inp[1])
vertices = {}
edges = {}

for i in range(1, num_vertex+1):
	vertices[i] = []

for i in range(num_edge):
	inp = input().split(" ")
	edge = list(map(int, inp))
	vertices[edge[0]].append(edge[1])
	vertices[edge[1]].append(edge[0])

bridges = 0
visited = []

for i, j in vertices.items():
	visited.append(i)
	if len(j) == 1:
		bridges += 1
		for k in j:
			vertices[k].remove(i)
			if k in visited and len(vertices[k]) == 1:
				bridges += 1
print(bridges)

Submission status: Wrong Answer

Solution code:
import copy

def set(adjacent,edge):
    for x in edge:
        adjacent[x[0]].append(x[1])
        adjacent[x[1]].append(x[0])

    
def search(goal,path):
    n = path[len(path) - 1]
    if n == goal:
        print(path)
    else:
        for x in adjacent[n]:
            if x not in path:
                path.append(x)
                search(goal, path)
                path.pop()

def search_loop_node(adjacent,start,path,node_loops):
    n = path[len(path)-1]
    for x in adjacent[n]:
        if x == start and len(path) >=2 and path[-2] != start :
            path.append(x)
            node_loops.append(copy.deepcopy(path))
            path.pop()
        elif x not in path:
            path.append(x)
            search_loop_node(adjacent,start, path,node_loops)
            path.pop()

def main():
    #入力
    N, M = [int(i) for i in input().split()]
    edge = []
    for i in range(M):
        a,b = [int(i) for i in input().split()]
        edge.append([a,b])

    #辺の生成
    adjacent=[ [] for i in range(N+1)]
    loops=[]
    set(adjacent,edge)
    #ループの検索
    for i in range(N):
        search_loop_node(adjacent,i,[i],loops)
    #ループに属する辺(橋でない辺)の検索
    not_bridge = []
    for loop in loops:
        pre_node = loop[0]
        for node in loop:
            if pre_node < node and [pre_node, node] not in not_bridge:
                not_bridge.append([pre_node,node])
    #答えは全体の辺の数からループでないものを引いた数
    print(M-len(not_bridge))
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
nums = [0] * (N)
for i in range(M):
    a, b = map(int, input().split())
    nums[a - 1] += 1
    nums[b - 1] += 1
if N - 1 == M:
    print(M)
else:
    print(nums.count(1) + nums.count(2))

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python3
# -*- coding: utf-8 -*-

N,M = map(int,input().split(" "))
ans = N - 1

line = {}
double = {}

for i in range(1,N+1):
	line[i] = [i,i]
	double[i] = 0


for i in range(M):
	a,b = map(int,input().split(" "))
	double[a] += 1
	double[b] += 1
	if (b - line[b][0]) < (b - a):
		line[b][0] = a
	if (line[a][1] - a) < (b - a):
		line[a][1] = b 


if N-1 == M :
	print(N-1)
	exit(0)

for i in double.items():
	if i[1] >= 3:
		if double[line[i[0]][0]] >= 3:
			ans -= i[0] - line[i[0]][0]
			double[line[i[0]][0]] -= 1

		else:
			ans -= line[i[0]][1] - i[0]
			double[line[i[0]][1]] -= 1



print(ans)