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
 
N, M = (list(map(int, input().split())))
a = np.array([0]*M)
b = np.array([0]*M)
for i in range(M):
  a[i], b[i] = (input().split())
ans = M
for i in range(M):
  C = set()
  D = set()
  count = 0
  while(True):
    for j in range(M):
      if i != j:
        if(count == 0):
          C.add(a[j]) 
          C.add(b[j])
          count += 1  
        if a[j] in C or b[j] in C:
          C.add(a[j])
          C.add(b[j])
    if(C == D):
      break
    else:
      D = C
  if(len(C) == N):
    ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
 
N, M = (list(map(int, input().split())))
a = np.array([0]*M)
b = np.array([0]*M)
for i in range(M):
  a[i], b[i] = (input().split())
ans = M
for i in range(M):
  C = set()
  D = set()
  count = 0
  while(True):
    count = 0
    for j in range(M):
      if i != j:
        if(count == 0):
          C.add(a[j]) 
          C.add(b[j])
          count += 1  
        if a[j] in C or b[j] in C:
          C.add(a[j])
          C.add(b[j])
    if(C == D):
      break
    else:
      D = C
  if(len(C) == N):
    ans -= 1
  else:
    print(C)
print(ans)

Submission status: Wrong Answer

Solution code:
import copy

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

lis = [[10000 for i in range(n)] for j in range(n)]
hen = []
for _ in range(m):
    hen.append(list(map(int, input().split())))

ans = 0
for x in range(m):
    lis_tmp = copy.deepcopy(lis)
    bri = copy.deepcopy(hen)
    bri.pop(x)
    for y in range(m-1):
        lis_tmp[bri[y][0]-1][bri[y][1]-1] = 1
        lis_tmp[bri[y][1]-1][bri[y][0]-1] = 1

    for k in range(n):
        for i in range(n):
            for j in range(n):
                lis_tmp[i][j] = min(lis_tmp[i][j], lis_tmp[i][k] + lis_tmp[k][j])

    if 10000 in lis_tmp:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:

import sys

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

def DFS(start, graph):
    visited = []
    que = []
    que.append(start)
    
    while que != []:
        now = que[0]
        del que[0]
        for z in graph:
            if now in z:
                if z[0] == now:
                    if z[1] not in visited:
                        visited.append(z[1])
                        que.append(z[1])
                else:
                    if z[0] not in visited:
                        visited.append(z[0])
                        que.append(z[1])
                 
    if len(visited) == N:
        return 0
    else:
        return 1

ans = 0

if N == 2:
    print(1)
    sys.exit()
for i in range(M):
    graph = AB.copy()
    del graph[i]
    ans += DFS(graph[0][0],graph)
    
print(ans)

Submission status: Wrong Answer

Solution code:
import copy

N, M = map(int, input().split())
count = 0
path = [[] for j in range(N + 1)]
for n in range(M):
    a, b = map(int, input().split())
    path[a].append(b)
    path[b].append(a)
visited = []
road = []


def solve(now, visited, road):
    ans = []
    if now in visited:
        return visited
    visited.append(now)
    for i in range(len(road[now])):
        ans.extend(solve(road[now][i], visited[:], road[:]))
    return ans


PATH = copy.deepcopy(path)
check = [[0 for C in range(N + 1)] for c in range(N + 1)]
Ans = [[] for c in range(N + 1)]
for x in range(1, N + 1):
    Q = []
    for y in range(len(PATH[x])):
        check[x][path[x][y]] = 1
        if check[path[x][y]][x] != 1:
            PATH = copy.deepcopy(path)
            PATH[x].pop(y)
            Q = copy.deepcopy(solve(x, [], PATH[:]))
            Q = list(set(Q))
            Ans[x].append(len(Q))

for i in range(N + 1):
    for s in range(len(Ans[i])):
        if Ans[i][s] != N:
            count += 1
            break

print(count)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def solve():
    n, m = map(int, input().split())
    lst = defaultdict(list)
    for _ in range(m):
        a, b = map(int, input().split())
        lst[a].append(b)
        lst[b].append(a)
    targets = [[i, 0, 1] for i in lst[1]]
    visited = [False]*(n+1)
    cnts = [0]*(n+1)
    cnts[1] += 1

    visited[1] = True
    while targets:
        target = targets.pop(0)
        if visited[target[0]]:
            cnts[target[0]] += 1
            cnts[target[1]] += 1
            continue
        targets.extend([[i, target[2], target[0]] for i in lst[target[0]] if i != target[2]])
        visited[target[0]] = True
        cnts[target[0]] += 1
    print(cnts[1:].count(1) if n != cnts[1:].count(1) else (n-1))


if __name__=="__main__":
    solve()

Submission status: Wrong Answer

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

def DFS(start, graph):
    visited = []
    stack = []
    stack.append(start)
    
    while stack != []:
        now = stack.pop()
        for z in graph:
            if now in z:
                if z[0] == now:
                    if z[1] not in visited:
                        visited.append(z[1])
                        stack.append(z[1])
                else:
                    if z[0] not in visited:
                        visited.append(z[0])
                        stack.append(z[1])
                
    if len(visited) == N:
        return 0
    else:
        return 1

ans = 0

for i in range(M):
    graph = AB.copy()
    del graph[i]
    ans += DFS(graph[0][0],graph)
    
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def solve():
    n, m = map(int, input().split())
    lst = defaultdict(list)
    for _ in range(m):
        a, b = map(int, input().split())
        lst[a].append(b)
        lst[b].append(a)
    targets = [[i, -1, 1] for i in lst[1]]
    visited = [False]*(n+1)
    cnts = [0]*(n+1)
    cnts[1] += 1

    visited[1] = True
    while targets:
        target = targets.pop(0)
        if visited[target[0]]:
            cnts[target[0]] += 1
            continue
        targets.extend([[i, target[2], target[0]] for i in lst[target[0]] if i != target[2]])
        visited[target[0]] = True
        cnts[target[0]] += 1
    print(cnts.count(1) - 1)


if __name__=="__main__":
    solve()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
gragh = [[] for _ in range(n)]
used_v = [False]*n
used_e = [[False]*n for _ in range(n)]
Ord = [0]*n
lowlink = [0]*n
k = 0
for i in range(m) :
    a, b = map(int, input().split())
    gragh[a-1].append(b-1)
    gragh[b-1].append(a-1)

def dfs(v) :
    global k
    used_v[v] = True
    Ord[v] = lowlink[v] = k
    k += 1
    for node in gragh[v] :
        if not used_v[node] :
            used_e[v][node] = True
            dfs(node)
            lowlink[v] = min(lowlink[v], lowlink[node])
        elif not used_e[node][v] :
            lowlink[v] = min(lowlink[v], Ord[node])


dfs(0)
ans = 0
used_e = [[False]*n for _ in range(n)]
for i in range(n) :
    for j in gragh[i] :
        if not used_e[i][j] and Ord[i] < lowlink[j] :
            ans += 1
        used_e[i][j] = True
        used_e[j][i] = True

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = (list(map(int, input().split())))
a = np.array([0]*M)
b = np.array([0]*M)
for i in range(M):
  a[i], b[i] = (input().split())
ans = M
for i in range(M):
  C = set()
  D = set()
  count = 0
  boo = True
  while(boo):
    for j in range(M):
      if i != j:
        if(count == 0):
          C.add(a[j])
          C.add(b[j])
          count += 1
        if C >= {a[j]} or C >= {b[j]}:
          C.add(a[j])
          C.add(b[j])
    if(C == D):
      boo = False
      break
    else:
      D = C
  if(len(C) == N):
    ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
#https://beta.atcoder.jp/contests/abc075
# -*- coding: utf-8 -*-
from collections import Counter
import sys

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

line_count = []
for i in line:
    line_count.append(i[0])
    line_count.append(i[1])
line_count = Counter(line_count)

start_point = []
for k,v in line_count.items():
    if v == 1: start_point.append(k)
if len(start_point) == 0:
    print(0)
    sys.exit()

counter = 0
while(True):
    start_point_bu = start_point
    start_point = []
    for i in start_point_bu:
        for index,j in enumerate(line):
            if i in j:
                if j[0] == i : start_point.append(j[1])
                if j[1] == i : start_point.append(j[0])
                line.pop(index)
                counter+=1
            break
    if len(start_point)==0: break
print(counter)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
F = [0]*N
L = []
for i in range(M):
    a,b = map(int, input().split())
    L.append([a,b])
    F[a-1] += 1
    F[b-1] += 1

L = list(map(list, zip(*L)))

def search(L, i):
    if i in L[0]:
        return L[1][L[0].index(i)]
    else:
        return L[0][L[1].index(i)]

c = 0
for i in range(1,N+1):
    if F[i-1] == 1:
        c += 1
        j = search(L,i)
        while F[j-1] == 2:
            c += 1
            j = search(L,j)

print(c)

Submission status: Wrong Answer

Solution code:
#https://beta.atcoder.jp/contests/abc075
# -*- coding: utf-8 -*-
from collections import Counter
import sys

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

line_count = []
for i in line:
    line_count.append(i[0])
    line_count.append(i[1])
line_count = Counter(line_count)
print(line_count)

start_point = []
for k,v in line_count.items():
    if v == 1: start_point.append(k)
if len(start_point) == 0:
    print(0)
    sys.exit()
print(start_point)

counter = 0
while(True):
    start_point_bu = start_point
    start_point = []
    for i in start_point_bu:
        for index,j in enumerate(line):
            if i in j:
                if j[0] == i : start_point.append(j[1])
                if j[1] == i : start_point.append(j[0])
                line.pop(index)
                counter+=1
            break
    if len(start_point)==0: break
print(counter)

Submission status: Wrong Answer

Solution code:
inputs = input().split()
N = int(inputs[0])
M = int(inputs[1])

grid_list = [[] for x in range(N)]
input_edge = []

diff = 0
for i in range(N):
    diff += i

for M in range(M):
    inputs = input().split()
    a = int(inputs[0])
    b = int(inputs[1])
    input_edge.append([a-1, b-1])
    grid_list[a - 1].append(b-1)
    grid_list[b-1].append(a-1)



ans = 0
for inp in input_edge:
    grid_list[inp[0]].remove(inp[1])
    grid_list[inp[1]].remove(inp[0])
    able_list = []
    sum = 0
    search_list = []
    for g in grid_list[0]:
        search_list.append(g)
    for g in search_list:
        able_list.append(g)
        for h in grid_list[g]:
            if h not in search_list:
                search_list.append(h)
    able_list = list(set(able_list))
    for i in able_list:
        sum += i
    if diff > sum:
        print("%s , %s" % (inp[0], inp[1]))
        ans += 1
    grid_list[inp[0]].append(inp[1])
    grid_list[inp[1]].append(inp[0])

print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
range = xrange
N, M = map(int, raw_input().split(' '))
G = [tuple(map(int, raw_input().split(' '))) for _ in range(M)]

onehop = []
for i in range(1, N + 1):
    o = []
    for e in G:
        if i in e:
            o.append(e)
    onehop.append(o)

answer = set()
for i, o in sorted(enumerate(onehop), key=lambda x: len(x[1])):
    c = [e for e in o if e not in answer]
    if len(c) == 1:
        answer.add(c[0])
print len(answer)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = (list(map(int, input().split())))
a = np.array([0]*M)
b = np.array([0]*M)
for i in range(M):
  a[i], b[i] = (input().split())
ans = 0
C = set()
D = set()
for i in range(M):
  count = 0
  boo = True
  while(boo):
    for j in range(M):
      if i != j:
        if(count == 0):
          C.add(a[j])
          C.add(b[j])
          count += 1
        if C <= {a[j]} or C <= {b[j]}:
          C.add(a[j])
          C.add(b[j])
    if(C & D == C):
      print("aaa")
      boo = False
      break
    else:
      D = C
  if(len(C) == N):
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    AB = tuple(tuple(map(int, input().split())) for _ in [0] * M)

    x = M - (N - 1)
    ans = M - x * 3
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5)


N,M = map(int,raw_input().split(" "))
path = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,raw_input().split(" "))
    a-=1
    b-=1
    path[a].append((b,i))
    path[b].append((a,i))




vmemo = [0 for i in range(N)]
ememo = [1 for i in range(M)]

stk = []

def loop(pos,last_edge):
    global stk,vmemo,ememo
    
    if vmemo[pos]:
        for i in range(len(stk)-1,-1,-1):
            _v,_e = stk[i]
            ememo[_e] = 0
            if _v == pos:
                return pos
    
    vmemo[pos] = 1
    for v,e in path[pos]:
        if e != last_edge:
            stk.append((pos,e))
            _p = loop(v,e)
            if _p != pos:
                return pos
            ememo[_p] = 0
            stk.pop()
    vmemo[pos] = 0       

    return -1



loop(0,-1)
print(ememo.count(1))

Submission status: Wrong Answer

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

nb = [[0 for x in range(n)] for y in range(n)]
for start, end in [map(int, input().split()) for x in range(m)]:
    nb[start - 1][end - 1] = 1
    nb[end - 1][start - 1] = 1

#
# for i in nb: print(*i)

count = 0
for index, i in enumerate(nb):
    if i.count(1) == 1:
        count += 1
        nb[index] = [0 for x in range(n)]
        for row in nb:
            row[index] = 0

# print()
# for i in nb: print(*i)
#         
print(count)

Submission status: Time Limit Exceeded

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

cnt = 0
for p in range(m):
    e = ee[:p] + ee[p+1:]
    dist = [[float("inf")]*n for _ in range(n)]
    
    for i in range(m-1):
        s,t = e[i]
        dist[s-1][t-1]=1
        dist[t-1][s-1]=1

    for i in range(n):
        dist[i][i]=0
    #[print(*dist[l]) for l in range(n)]
    #print("-------------------------")

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != float("inf") and dist[k][j] != float("inf"):
                   dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    #[print(*dist[l]) for l in range(n)]
    #print("-------------------------")

    flag = True
    for i in range(n):
        if flag == False:
            break
        for j in range(n):
            if dist[i][j]==float("inf"):
                cnt += 1
                flag = False
                break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

def warshallfloyd(cost,V):
    INF = float("inf")
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if cost[i][k]!=INF and cost[k][j]!=INF:
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

    for i in cost:
        if float("inf") in i:
            return False
    
    return True

N,M = map(int,input().split())
edge = [[float("inf") for i in range(N)] for j in range(N)]

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

ans = 0

for i in range(N-1):
    for j in range(i+1,N):
        if edge[i][j]:
            tmp = deepcopy(edge)
            tmp[i][j] = float("inf")
            tmp[j][i] = float("inf")
            if not warshallfloyd(tmp,N):
                ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(d, n):
    # d: 隣接行列(正方行列)
    # n: 頂点数

    # i -> j の最短距離を計算する
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # i -> k -> j と頂点kを挟む
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    return d


# -------------------------------------------------------------------#
import copy


def main():
    # n: 頂点数
    # w: 辺の数
    n, w = map(int, input().split())
    # v -> v ; cost: 0
    d = [[float("Inf")] * n for i in range(n)]
    for i in range(n):
        d[i][i] = 0

    # d[u][v] : 辺u-vのコスト(if not: inf)
    e = []
    for i in range(w):
        # edge: u -> v ; cost : z
        u, v = map(lambda x: int(x) - 1, input().split())
        e.append([u, v])
        # 無向グラフを想定
        d[u][v] = 1
        d[v][u] = 1

    ans = 0
    for (u, v) in e:
        dd = copy.deepcopy(d)
        dd[u][v] = float("Inf")
        dd[v][u] = float("Inf")

        wd = warshall_floyd(dd, n)

        for res in wd:
            if float("Inf") in res:
                ans += 1
                break

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from copy import deepcopy
n,m = map(int,input().split())
inf = float("inf")
L = [[inf for i in range(n)] for j in range(n)]

for i in range(m):
    a,b = map(int,input().split())
    L[a-1][b-1] = 1
    L[b-1][a-1] = 1
#print(L)
cnt = 0
for i in range(n):
    for j in range(n):
        LL = deepcopy(L)
        LL[i][j] = 0
        LL[j][i] = 0
        LL = floyd_warshall(LL)
        #print(LL)
        for k in LL:
            if inf in k:
                cnt +=1
                break
print(cnt//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))
import copy
N, M = mi()
D = dp2(float('inf'), N, N)
memo = []
cnt = 0

for i in range(M):
    s, t = mi()
    s, t = s-1, t-1
    memo.append((s, t))
    D[s][t] = D[t][s] = 1

for x in range(M):
    d = copy.deepcopy(D)
    s, t = memo[x][0], memo[x][1]
    d[s][t] = d[t][s] = float('inf')
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    for i in range(N):
        for j in range(i+1, N):
            if d[i][j] == float('inf'):
                cnt += 1
                break
        else:
            continue
        break

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin,setrecursionlimit
from copy import deepcopy
import heapq

n,m = map(int,stdin.readline().rstrip().split())

li = [[0 for i in range(n+1)]for j in range(n+1)]

inf = 10**10

def all_pairs_shortest_paths(W):
    # 頂点の数
    n = len(W)
    # 結果を格納する行列を用意する
    res = [[0] * n for i in range(n)]
    # 用意した行列を初期化する
    for i in range(n):
        for j in range(i, n):
            if i == j:
                val = 0
            elif W[i][j]:
                val = W[i][j]
            else:
                val = inf
            res[i][j] = res[j][i] = val
    # 動的計画法ですべての超点間の最短距離を求める
    for k in range(n):
        for u in range(n):
            for v in range(n):
                res[u][v] = min(res[u][v], res[u][k] + res[k][v])
    return res

lin = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]

true = [True]*(n+1)
point = 0

for j in range(m):
    lis = []
    for num,i in enumerate(lin):
        if num != j:
            lis.append(i)
    liv = [[0 for e in range(n+1)]for o in range(n+1)]
    for kp in lis:
        liv[kp[0]][kp[1]] = 1
        liv[kp[1]][kp[0]] = 1
    kota = all_pairs_shortest_paths(liv)[1:]
    flag = True
    for kk in kota:
        if inf in kk[1:]:
            flag = False
    if flag:
        point += 1

print(m-point)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import sqrt
from collections import Counter, defaultdict

input = sys.stdin.readline


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


def LIN(n: int):
    return [I() for _ in range(n)]


inf = float("inf")
mod = 10 ** 9 + 7


def main():
    n, m = MI()

    g = defaultdict(list)
    for _ in range(m):
        a, b = input().split()
        if a in g:
            g[a].append(b)
        else:
            g[a] = [b]
        if b in g:
            g[b].append(a)
        else:
            g[b] = [a]

    bridge = 0
    passed = []
    for k, v in g.items():
        if len(v) == 1 and k not in passed:
            bridge += 1
            key = k
            now = v[0]
            passed.append(now)
            while len(g[now]) == 2:
                bridge += 1
                if g[now].index(key) == 0:
                    if g[now][1] not in passed:
                        key = now
                        now = g[now][1]
                        passed.append(now)
                else:
                    if g[now][0] not in passed:
                        key = now
                        now = g[now][0]
                        passed.append(now)
    print(bridge)

    pass


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m = map(int,input().split())
to = [[] for _ in range(n)]
v = []
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
    v.append((a,b))
ans = m
seen = [False]*n
stk = deque()
for i in range(m):
    a,b = v[i]
    stk.clear()
    stk.append((a,-1))
    for j in range(n): seen[j] = False
    seen[a] = True
    flag = True
    while stk and flag:
        cur,prev = stk.pop()
        for nxt in to[cur]:
            if nxt == b:
                if cur == a: continue
                ans -= 1
                flag = False
                break
            if nxt == prev: continue
            if seen[nxt]: continue
            stk.append((nxt,cur))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m = map(int,input().split())
to = [[] for _ in range(n)]
v = []
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
    v.append((a,b))
ans = m
seen = [False]*n
q = deque()
for i in range(m):
    a,b = v[i]
    q.clear()
    q.append((a,-1))
    for j in range(n): seen[j] = False
    seen[a] = True
    flag = True
    while q and flag:
        cur,prev = q.popleft()
        for nxt in to[cur]:
            if nxt == b:
                if cur == a: continue
                ans -= 1
                flag = False
                break
            if nxt == prev: continue
            if seen[nxt]: continue
            q.append((nxt,cur))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m = map(int,input().split())
to = [[] for _ in range(n)]
v = []
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
    v.append((a,b))
ans = m
seen = [False]*n
for i in range(m):
    a,b = v[i]
    q = deque()
    q.append((a,-1))
    for j in range(n): seen[j] = False
    seen[a] = True
    flag = True
    while q and flag:
        cur,prev = q.popleft()
        for nxt in to[cur]:
            if nxt == b:
                if cur == a: continue
                ans -= 1
                flag = False
                break
            if nxt == prev: continue
            if seen[nxt]: continue
            q.append((nxt,cur))

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(m):
    a,b = v[i]
    q = deque()
    q.append((a,-1))
    seen = [False]*n
    seen[a] = True
    flag = True
    while q and flag:
        cur,prev = q.popleft()
        for nxt in to[cur]:
            if nxt == b:
                if cur == a: continue
                ans -= 1
                flag = False
                break
            if nxt == prev: continue
            if seen[nxt]: continue
            q.append((nxt,cur))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
d=[[] for i in range(N)]
for i in range(M):
    b, c = map(int, input().split())
    d[b-1].append(c-1)
    d[c-1].append(b-1)
a=0
while True:
    count = 0
    for i in range(N):
        if len(d[i]) == 1:
            d[d[i][0]].remove(i)
            d[i]=[]
            count += 1
        if count == 0:
            break
        a+=count
print(a)

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(d):
    #d[i][j]=i番目の頂点からj番目の頂点までの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
import copy

n,m=map(int,input().split())
way_list=[[100 for i in range(n)] for j in range(n)]
for i in range(n):
    way_list[i][i]=0
#自分から自分の値はもちろんゼロ
#way_list[i][j]頂点iからjまでの最短距離
lists=[]
for i in range(m):
    a,b=map(int,input().split())
    way_list[a-1][b-1]=1
    way_list[b-1][a-1]=1
    lists.append((a,b))
#最短距離が100以下であれば十分到達可能
#そうでないなら到達は不可能
answer=0
for i in range(m):
    sub=copy.deepcopy(way_list)
    x,y=lists[i][0],lists[i][1]
    sub[x-1][y-1]=100
    sub[y-1][x-1]=100
    #一度この頂点がないものとして計算してみる
    P=warshall_floyd(sub)
    
    flag=True
    for i in range(n):
        for j in range(n):
            if P[i][j]>=100:
                flag=False
                #到達不可能な点が出た時→絶対必要な点
    if not flag:
        answer+=1
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

    return m - len(ng_edges)

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

Submission status: Time Limit Exceeded

Solution code:
#warshal-floydの練習だと思ってやる。
n,m=map(int,input().split())
A=[list(map(int,input().split()))for i in range(m)]
d=[[float('inf') for i in range(n)]for i in range(n)]

def wf(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j]=min(d[i][j], d[i][k]+d[j][k])
#warshal floydする関数

# for t in range(n):
#     a,b=A[t]
#     a-=1
#     b-=1
#     d[a][b]=1
#Aにある経路を、おもみ1で計算。
count=0
for i in range(m):
    d=[[float('inf') for _ in range(n)]for _ in range(n)]
    for j in range(m):
        if i==j:
            p,q=A[j]
            p-=1
            q-=1
            #1箇所くっつけないでおく場所を指定し、そこの場所をp,qでmemo
        else:
            a,b=A[j]
            a-=1
            b-=1
            d[a][b]=1
            d[b][a]=1
    wf(d)
    if d[p][q]==float('inf'):
        count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

ans = 0

n,m = map(int, input().split())
tpl = tuple([tuple(map(int, input().split())) for _ in range(m)])
ls = []
for i in range(1,n+1):
    tmpls = []
    for j in range(1,n+1):
        if i < j:
            if (i,j) in tpl:
                tmpls.append(j)
        elif i > j:
            if (j,i) in tpl:
                tmpls.append(j)
    ls.append(tuple(tmpls))
ls = tuple(ls)

def dfs(a, visitedls, ini, ininext):
    global flag
    visitedls.append(a)
    if a == ini:
        if ininext != visitedls[-2]:
            flag = True
    else:
        for b in ls[a-1]:
            if b not in visitedls:
                dfs(b, visitedls, ini, ininext)
    visitedls.remove(a)

def main():
    for i in range(n):
        for p in ls[i]:
            global flag, ans
            flag = False
            visitedls = []
            dfs(p, visitedls, i+1, p)
            if not flag:
                ans += 1
    print(int(ans/2))



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

n,m = map(int,input().split()) #n:頂点数　w:辺の数
l=[list(map(int,input().split())) for i in range(m)]
ans=0

#d[u][v] : 辺uvのコスト(存在しないときはinf)
for j in range(m):
	d = [[float("inf") for i in range(n)] for i in range(n)]
	b=l[:j]+l[j+1:]
	for i in range(m-1):
		x,y = b[i][0],b[i][1]
		x-=1;y-=1
		d[x][y] = 1
		d[y][x] = 1
	for i in range(n):
		d[i][i] = 0 #自身のところに行くコストは０
	#print(warshall_floyd(d))
	for i in range(n):
		for k in range(n):
			if warshall_floyd(d)[i][k]==float("inf"):
				ans+=1
				break
		else:
			continue
		break
	#print(ans)
print(ans)