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: 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()) #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 #自身のところに行くコストは０
	for i in range(n):
		for k in range(n):
			if warshall_floyd(d)[i][k]==float("inf"):
				ans+=1
				break
		else:
			continue
		break
	b=copy.deepcopy(l)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
inf = 10**3
n,m = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]
def warshall_floyd(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[k][j])
    return d
point = 0
for i in range(m):
    d = [[inf for i in range(n)]for j in range(n)]
    lin = li[:i]+li[i+1:]
    for j in range(m-1):
        d[lin[j][0]-1][lin[j][1]-1] = 1
        d[lin[j][1]-1][lin[j][0]-1] = 1
    for k in range(n):
        d[k][k] = 0
    lis = warshall_floyd(d)
    for i in lis:
        i.sort()
        if i[-1] == inf:
            point += 1
            break
print(point)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import math
import bisect
import heapq
import numpy as np
from math import factorial

inf = 10**3
n,m = [int(x) for x in stdin.readline().rstrip().split()]

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

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    #k：中継
    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
point = 0
for i in range(m):
    d = [[inf for i in range(n)]for j in range(n)]
    lin = li[:i]+li[i+1:]
    for j in range(m-1):
        d[lin[j][0]-1][lin[j][1]-1] = 1
        d[lin[j][1]-1][lin[j][0]-1] = 1
    for k in range(n):
        d[k][k] = 0
    lis = warshall_floyd(d)
    for i in lis:
        if inf in i:
            point += 1
            break
print(point)

Submission status: Time Limit Exceeded

Solution code:
import copy, heapq
class Dijkstra(object):
  def dijkstra(self, list_cost, start):
    num_node = len(list_cost)
    distance_node = [float("inf") for i in range(num_node)]
    previous_node = [float("inf") for i in range(num_node)]

    distance_node[start] = 0
    queue = []
    heapq.heappush(queue, (0, start))

    while len(queue) != 0:
      previous_cost, pre_loc = heapq.heappop(queue)

      if distance_node[pre_loc] < previous_cost:
        continue

      for check_node in range(num_node):
        check_cost = list_cost[pre_loc][check_node]
        if check_cost != float("inf") and distance_node[check_node] > distance_node[pre_loc] + check_cost:
          distance_node[check_node] = distance_node[pre_loc] + check_cost
          heapq.heappush(queue, (distance_node[check_node], check_node))
          previous_node[check_node] = pre_loc
    
    return previous_node

  def get_path(self, previous_node, start, goal):
    path = [goal]
    last = goal
    while previous_node[last] != float('inf'):
      path.append(previous_node[last])
      last = previous_node[last]

    if start in path:
      return "Linking"
    else:
      return "Uncoupling"


def judge(N, M, test):
  count_bridge = 0

  for cut_edge in test:
    list_edge_cutted = copy.deepcopy(test)
    list_edge_cutted.remove(cut_edge)
    d = Dijkstra()

    list_cost = []
    for start in range(N):
      temp_list = []
      for end in range(N):
        if (start + 1, end + 1) in list_edge_cutted or (end + 1, start + 1) in list_edge_cutted:
          temp_list.append(1)
        else:
          temp_list.append(float("inf"))
      list_cost.append(temp_list)
  
    flag_bridge = False
    for start in range(N):
      list_previous_node = d.dijkstra(list_cost, start)
      for goal in range(N):
        if start != goal:
          check_result = d.get_path(list_previous_node, start, goal)
          if check_result == "Uncoupling":
            flag_bridge = True
            break
      if flag_bridge:
        count_bridge += 1
        break
  print(count_bridge)

  
if __name__ == "__main__":
  n, m = map(int, input().split())
  list_bridge = [tuple(map(int, input().split())) for _ in range(m)]
  judge(n, m, list_bridge)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
e=[]
for i in range(m):
    e.append(list(map(int,input().split())))
ans=0
for i in range(m):
    nall=[]
    for j in range(m):
        if i==j:
            continue
        nall.append(e[j])
    visited=[0]*n
    visited[0]=1
    t=[1]
    while len(t)>0:
        tmp=[]
        ntmp=[]
        for p in t:
            visited[p-1]=1
            for q in nall:
                if q[0]==p:
                    if visited[q[1]-1]==0:
                        tmp.append(q[1])
                        visited[q[1]-1]=1
                elif q[1]==p:
                    if visited[q[0]-1]==0:
                        tmp.append(q[0])
                        visited[q[0]-1]=1
                else:
                    if visited[q[0]-1]==0 or visited[q[1]-1]==0:
                        ntmp.append(q)
        t=tmp
        nall=ntmp
    if sum(visited)!=n:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy 
#深さ優先探索
def dfs(node, E_st_tmp):
      
    #辺の集合が存在しないとき
    if len(E_st_tmp) == 0:
        #全ての頂点を覗いた時
        if not (False in V_look):
            return 
        else:#辺の集合もないし、頂点もない。
            return 
    elif not (False in V_look): #辺の集合があっても全部見る時ある。
        return 

    #ここで探索する
    for i in range(V):
        E_st_tmp_copy   = copy.copy(E_st_tmp)

        if {node, i} in E_st_tmp_copy:
            V_look[i] = True
            E_st_tmp_copy.remove({node, i})
            dfs(i, E_st_tmp_copy)
    
    return

    
#連結かどうかのチェックする
V, E = map(int, input().split())

V_set = [v for v in range(V)]

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

count = 0

for edge in E_set:
    E_set_cut = copy.copy(E_set)
    E_set_cut.remove(edge)
    #全ての頂点を覗いたか?
    V_look = [False] * V
    V_look[0] = True

    #深さ優先探索
    for v in range(V):
        E_set_copy  = copy.copy(E_set_cut)

        if {0, v} in E_set_copy:
            V_look[v] = True
            E_set_copy.remove({0, v})
            flg_t = dfs(v, E_set_copy)
    if (False in V_look):
        count += 1
        

print(count)

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(_) for _ in input().split()]

paths = [[0] * (N + 1) for _ in range(N + 1)]


def has_path(c, t, arrived):
    if c == t: return True
    for i in range(1, N + 1):
        if i in arrived: continue
        if paths[c][i]:
            arrived.append(i)
            if has_path(i, t, arrived):
                return True
            arrived.pop()
    return False


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

ans = 0
for e in edge:
    paths[e[0]][e[1]] = 0
    paths[e[1]][e[0]] = 0
    if not has_path(e[0], e[1], []):
        ans += 1
    paths[e[0]][e[1]] = 1
    paths[e[1]][e[0]] = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N, M = LI()
A, B = [], []
for i in range(M):
    a, b = LI()
    A.append(a)
    B.append(b)

"""
頂点ごとにみる。
その頂点につながっている辺を洗い出す
洗い出した辺の頂点同士がつながっているか確認する
最終的に自分のもとに戻ってこれるか。
dfsで全経路を洗い出す
1とそれ以外が全部つながるか。
2とそれ以外が全部つながるかを調査すればよい
"""

def dfs(reached_nodes, lines):
    print('df', reached_nodes, lines, file=sys.stderr)
    # 最初に与えられた線からたどっていって、すべての線を洗い出す。すべての頂点が入っていればおK
    # このノードにつながっている辺をみつける
    for line in lines:
        if line[0] in reached_nodes or line[1] in reached_nodes:
            # 既に到達しているnodeに入っている場合
            new_lines = [l for l in lines if l != line]
            if not dfs(reached_nodes + line, new_lines):
                # 全部つながることが確認された場合
                return False
    else:
        # 一回もひかからなかったので終了
        print('r', reached_nodes, file=sys.stderr)
        if len(set(reached_nodes)) < N:
            print('True', file=sys.stderr)
            # 無理でした。
            return True
        else:
            return False

ans = 0
for idx in range(N):
    # idx番目の線をなくす
    lines = []
    for m in range(M):
        if m == idx:
            continue
        else:
            lines.append([A[m], B[m]])
    print(idx, lines, file=sys.stderr)
    # 各頂点が全頂点とつながっているか確認
    # ただたんに全頂点が入っているだけでは断絶の可能性があるので不十分
    if dfs(lines[0][:1], lines):
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

n, m = (int(x) for x in sys.stdin.readline().split())
a_b_list = [[int(x) for x in sys.stdin.readline().split()] for y in range(m)]
count = 0
for i in a_b_list:
    a, b = i[0], i[1]
    a_b_list_temp = [[x for x in y] for y in a_b_list]  # deepcopyだと遅い
    a_b_list_temp.remove([a, b])
    # aをスタートとし、bをゴールと仮定する
    q = deque([])
    for j in a_b_list_temp:
        if j[0] == a:
            q.append([a, j[1]])
        elif j[1] == a:
            q.append([a, j[0]])
    findRoot = False
    while len(q) > 0:
        a_b_root = q.pop()
        for j in a_b_list_temp:
            if (j[0] == a_b_root[-1] and j[1] == b) or (j[1] == a_b_root[-1] and j[0] == b):
                findRoot = True
                q.clear()
                break
            if a_b_root[-1] == j[0]:
                if j[1] not in a_b_root:
                    q.append(a_b_root + [j[1]])
            if a_b_root[-1] == j[1]:
                if j[0] not in a_b_root:
                    q.append(a_b_root + [j[0]])
    if not findRoot:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

n, m = (int(x) for x in sys.stdin.readline().split())
a_b_list = [[int(x) for x in sys.stdin.readline().split()] for y in range(m)]
count = 0
for i in a_b_list:
    a, b = i[0], i[1]
    a_b_list_temp = [[x for x in y] for y in a_b_list]  # deepcopyだと遅い
    a_b_list_temp.remove([a, b])
    # aをスタートとし、bをゴールと仮定する
    q = deque([])
    for j in a_b_list_temp:
        if j[0] == a:
            q.append([a, j[1]])
        elif j[1] == a:
            q.append([a, j[0]])
    findRoot = False
    while len(q) > 0:
        a_b_root = q.popleft()
        for j in a_b_list_temp:
            if (j[0] == a_b_root[-1] and j[1] == b) or (j[1] == a_b_root[-1] and j[0] == b):
                findRoot = True
                q.clear()
                break
            if a_b_root[-1] == j[0]:
                if j[1] not in a_b_root:
                    q.append(a_b_root + [j[1]])
            if a_b_root[-1] == j[1]:
                if j[0] not in a_b_root:
                    q.append(a_b_root + [j[0]])
    if not findRoot:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
from collections import deque

n, m = (int(x) for x in sys.stdin.readline().split())
a_b_list = [[int(x) for x in sys.stdin.readline().split()] for y in range(m)]
count = 0
for i in a_b_list:
    a, b = i[0], i[1]
    a_b_list_temp = copy.deepcopy(a_b_list)
    a_b_list_temp.remove([a, b])
    # aをスタートとし、bをゴールと仮定する
    q = deque([])
    for j in a_b_list_temp:
        if j[0] == a:
            q.append([a, j[1]])
        elif j[1] == a:
            q.append([a, j[0]])
    findRoot = False
    while len(q) > 0:
        a_b_root = q.popleft()
        for j in a_b_list_temp:
            if (j[0] == a_b_root[-1] and j[1] == b) or (j[1] == a_b_root[-1] and j[0] == b):
                findRoot = True
                q.clear()
                break
            if a_b_root[-1] == j[0]:
                if j[1] not in a_b_root:
                    q.append(a_b_root + [j[1]])
            if a_b_root[-1] == j[1]:
                if j[0] not in a_b_root:
                    q.append(a_b_root + [j[0]])
    if not findRoot:
        count += 1

print(count)

Submission status: Time Limit Exceeded

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

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

ans = 0

for ab in abs:
    a = ab[0] - 1
    b = ab[1] - 1
    _abs = abs[::]
    _abs.remove(ab)

    dist_map = [[i == j for j in range(N)] for i in range(N)]

    for _ab in _abs:
        _a = _ab[0] - 1
        _b = _ab[1] - 1
        if not dist_map[_a][_b]:
            dist_map[_a][_b] = True
            dist_map[_b][_a] = True

    for i in range(N):
        for j in range(N):
            for k in range(N):
                dist_map[j][k] = dist_map[j][k] or (dist_map[j][i] and dist_map[i][k])
                dist_map[k][j] = dist_map[j][k]

    if not dist_map[a][b]:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

class Bridge:
    def __init__(self, nodeA, nodeB):
        self.edges = [BridgeEdge(nodeA), BridgeEdge(nodeB)]

class BridgeEdge:
    def __init__(self, node):
        self.node = node
        self.judge = 0

class Node:
    def __init__(self, id):
        self.id = id
        self.bridges = []
    def addEdge(self, bridgeEdge):
        self.bridges.append(bridgeEdge)


nodes = [Node(i) for i in range(N+1)]
bridges = []
for A, B in (map(int, input().split()) for _ in range(M)):
    b = Bridge(nodes[A], nodes[B])
    nodes[A].addEdge(b.edges[1])
    nodes[B].addEdge(b.edges[0])
    bridges.append(b)


s = [(None, nodes[1], 1)]
idx = 0
while idx < len(s):
    pre, cur, level = s[idx]
    idx += 1

    if level > N * 2:
        break

    for nxt in cur.bridges:
        if not pre is nxt.node:
            nxt.judge += 1
            s.append((cur, nxt.node, level+1))

cnt = 0
for bd in bridges:
    if sum(1 for b in bd.edges if b.judge <= 1) > 0:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

N,M=[int(val) for val in input().split()]
a=deque()
b=deque()

for i in range(M):
  x,y = (int(val) for val in input().split())
  a.append(x)
  b.append(y)

cnt=0
for j in range(M):
    
    val_a=a.popleft()
    val_b=b.popleft()

    stack=deque([1])
    visited=deque()

    while len(stack) > 0:
        val=stack.pop()
        if visited.count(val)==0:
            visited.append(val)
        for i in range(len(a)):
            if a[i]==val:
                if b[i] != visited:
                    stack.append(b[i])
        for i in range(len(b)):
            if b[i]==val:
                if a[i] != visited:
                    stack.append(a[i]) 
                        
    if len(visited) < N:
        cnt+=1
    
    a.append(val_a)
    b.append(val_b)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def wf(this_graf):
    s = len(graf)
    for k in range(s):
        for i in range(s):
            for j in range(s):
                this_graf[i][j] = min(this_graf[i][j], this_graf[i][k] + this_graf[k][j])
    return this_graf

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
graf = [[10 ** 10 for i in range(n)] for j in range(n)]

for i, j in ab:
    graf[i - 1][j - 1] = 1
    graf[j - 1][i - 1] = 1

import copy
cnt = 0

for i, j in ab:
    this_graf = copy.deepcopy(graf)
    tmp = 0
    this_graf[i - 1][j - 1] = 10 ** 10
    this_graf[j - 1][i - 1] = 10 ** 10
    this_graf = wf(this_graf)
    for i in range(n):
        for j in range(n):
            if this_graf[i][j] == 10 ** 10:
                tmp = 1
                break
        if tmp:
            break
    cnt += tmp

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import math
import copy

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N,M = (int(_) for _ in input().split())
    a = []
    b = []
    d = []
    for i in range(M):
        s1,s2 = (int(_) for _ in input().split())
        a.append(s1-1)
        b.append(s2-1)
        
    for i in range(N):
        d.append(list(INF for _ in range(N)))

    for i in range(N):
        for j in range(N):
            if (i==j):
                d[i][j] = 0
                    
    for i in range(M):
        d[a[i]][b[i]] = 1
        d[b[i]][a[i]] = 1

    ans = 0
    for m in range(M):
        d_tmp = copy.deepcopy(d)
        d_tmp[a[m]][b[m]] = INF
        d_tmp[b[m]][a[m]] = INF

        for k in range(N):
            for i in range(N):
                for j in range(N):
                    d_tmp[i][j] = min(d_tmp[i][j],d_tmp[i][k]+d_tmp[k][j])

        for i in range(N):
            if d_tmp[i].count(INF) > 0:
                ans +=1
                break
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import math
import copy

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N,M = (int(_) for _ in input().split())
    a = []
    b = []
    d = []
    for i in range(M):
        s1,s2 = (int(_) for _ in input().split())
        a.append(s1-1)
        b.append(s2-1)

    ans = 0
    for m in range(M):
        d.clear()
        a_tmp = copy.copy(a)
        b_tmp = copy.copy(b)
        a_tmp.pop(m)
        b_tmp.pop(m)
        
        for i in range(N):
            d.append(list(INF for _ in range(N)))

        for i in range(N):
            for j in range(N):
                if (i==j):
                    d[i][j] = 0
                    
        for i in range(M-1):
            d[a_tmp[i]][b_tmp[i]] = 1
            d[b_tmp[i]][a_tmp[i]] = 1

        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):
            if d[i].count(INF) > 0:
                ans +=1
                break
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
import collections
N,M=map(int,input().split(' '))
R=[list(map(int,input().split(' '))) for i in range(M)]
Mat=[[0]*N]
for i in range(N-1):
	Mat.append([0]*N)
for r in R:
	Mat[r[0]-1][r[1]-1]=1
stack=[1]
island=[]

ans=0
Matmini=[]

def dfs():
	global stack
	global island
	global Matmini
	if stack==[]:
		return None
	if len(list(collections.Counter(island).keys()))==N:
		#全頂点が網羅できていたらそこで終了
		return None
	else:
		#たどれるノードがあるかどうかを確認
		for i in range(2,N+1):
			#iが未訪問のときのみ処理続行
			if i not in stack:
				#実際に辺が存在するか
				if Matmini[min(stack[0],i)-1][max(stack[0],i)-1]==1:
					stack = [i] + stack
					dfs()
		#これ以上先に進めなくなったら島の構成要素を更新
		island += stack
		stack.pop(0)

for r in R:
	#Rからi番目の辺だけ除去したもの
	Matmini = copy.deepcopy(Mat)
	Matmini[r[0]-1][r[1]-1]=0
	stack = [1]
	island = []
	dfs()
	if len(list(collections.Counter(island).keys()))!=N:
		ans += 1
		
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
N,M=map(int,input().split(' '))
R=[list(map(int,input().split(' '))) for i in range(M)]
Mat=[[0]*N]
for i in range(N-1):
	Mat.append([0]*N)
for r in R:
	Mat[r[0]-1][r[1]-1]=1
stack=[1]
island=[]

ans=0
Matmini=[]

def dfs():
	global stack
	global island
	global Matmini
	if stack==[]:
		return None
	if len(set(island))==N:
		#全頂点が網羅できていたらそこで終了
		return None
	else:
		#たどれるノードがあるかどうかを確認
		for i in range(2,N+1):
			#iが未訪問のときのみ処理続行
			if i not in stack:
				#実際に辺が存在するか
				if Matmini[min(stack[0],i)-1][max(stack[0],i)-1]==1:
					stack = [i] + stack
					dfs()
		#これ以上先に進めなくなったら島の構成要素を更新
		island += stack
		stack.pop(0)

for r in R:
	#Rからi番目の辺だけ除去したもの
	Matmini = copy.deepcopy(Mat)
	Matmini[r[0]-1][r[1]-1]=0
	stack = [1]
	island = []
	dfs()
	if len(set(island))!=N:
		ans += 1
		
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split(' '))
R=sorted([list(map(int,input().split(' '))) for i in range(M)], key=lambda l: l[0])

stack=[1]
island=[]

ans=0
Rdrop=[]

def dfs():
	global stack
	global island
	global Rdrop
	if stack==[]:
		return None
	if len(set(island))==N:
		#全頂点が網羅できていたらそこで終了
		return None
	else:
		#たどれるノードがあるかどうかを確認
		for i in range(1,N+1):
			#iが未訪問のときのみ処理続行
			if i not in stack:
				#実際に辺が存在するか
				if sorted([stack[0], i]) in Rdrop:
					stack = [i] + stack
					dfs()
		#これ以上先に進めなくなったら島の構成要素を更新
		island += stack
		stack.pop(0)

for i in range(len(R)):
	#Rからi番目の辺だけ除去したもの
	Rdrop = [ R[j] for j in range(M) if j!=i]
	stack = [1]
	island = []
	dfs()
	if len(set(island))!=N:
		ans += 1
		
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split(' '))
R=sorted([list(map(int,input().split(' '))) for i in range(M)], key=lambda l: l[0])

stack=[1]
island=[]

ans=0
Rdrop=[]

def dfs():
	global stack
	global island
	global Rdrop
	if stack==[]:
		return None
	if len(set(island))==N:
		#全頂点が網羅できていたらそこで終了
		return None
	else:
		#たどれるノードがあるかどうかを確認
		for i in range(1,N+1):
			#iが未訪問のときのみ処理続行
			if i not in stack:
				#実際に辺が存在するか
				if sorted([stack[0], i]) in Rdrop:
					stack = [i] + stack
					dfs()
		#これ以上先に進めなくなったら島の構成要素を更新
		island += [s for s in stack]
		stack.pop(0)

for i in range(len(R)):
	#Rからi番目の辺だけ除去したもの
	Rdrop = [ R[j] for j in range(M) if j!=i]
	stack = [1]
	island = []
	dfs()
	if len(set(island))!=N:
		ans += 1
		
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split(' '))
R=sorted([list(map(int,input().split(' '))) for i in range(M)], key=lambda l: l[0])

stack=[1]
island=[]

ans=0
Rdrop=[]

def dfs():
	global stack
	global island
	global Rdrop
	if stack==[]:
		return None
	else:
		#たどれるノードがあるかどうかを確認
		for i in range(1,N+1):
			#iが未訪問のときのみ処理続行
			if i not in stack:
				#実際に辺が存在するか
				if sorted([stack[0], i]) in Rdrop:
					stack = [i] + stack
					dfs()
		#これ以上先に進めなくなったら島の構成要素を更新
		island += [s for s in stack]
		stack.pop(0)

for i in range(len(R)):
	#Rからi番目の辺だけ除去したもの
	Rdrop = [ R[j] for j in range(M) if j!=i]
	stack = [1]
	island = []
	dfs()
	if len(set(island))!=N:
		ans += 1
		
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
d = [[float("inf")] * n for i in range(n)]
edge = []
for i in range(m):
    a, b = map(int, input().split())
    edge.append((a, b))
    d[a - 1][b - 1] = 1
    d[b - 1][a - 1] = 1
ans = 0
for a in range(m):
    d_s = [x[:] for x in d]
    x, y = edge[a]
    d_s[x - 1][y - 1] = float("inf")
    d_s[y - 1][x - 1] = float("inf")
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d_s[i][j] = min(d_s[i][j], d_s[i][k] + d_s[k][j])
    flag = 0
    for i in range(n):
        if flag:
            break
        for j in range(n):
            if flag:
                break
            if d_s[i][j] == float("inf"):
                ans += 1
                flag = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy

sys.setrecursionlimit(10000)

[vertex_num , sides_num] = list(map(int,input().split()))
sides = []

def _is_reachable( ver1, ver2, sides, sides_num):
	
#	print("sides_num:",sides_num ,"ver1 ",ver1,"ver2 ",ver2)
#	print(sides)
	for i in range(sides_num):
#		print(" :",sides[i])
		if( set(sides[i]) == set([ver2,ver1])):return 1

	for i in range(sides_num):
		if(sides[i][0] == ver2 or sides[i][1] == ver2):

			if( sides[i][0] == ver2 ):nex_ver = sides[i][1]
			else: nex_ver = sides[i][0]
			
			sides_buf = copy.deepcopy(sides)
			del sides_buf[i]
			
			if (_is_reachable( ver1, nex_ver, sides_buf, sides_num-1)  ):
				#print(ver1," and " , nex_ver , "is reachable")
				return 1
			else: continue
	return 0	
		 

for i in range(sides_num):
	sides.append( list(map(int,input().split())))


cnt = 0
for i in range(sides_num):
	sides_buf = copy.deepcopy( sides )
	del sides_buf[i]
#########	print("**",i,"**"," : ",  sides_buf)
	if(_is_reachable( sides[i][0],sides[i][1],sides_buf,sides_num-1)):
		cnt += 0
	else:
		cnt += 1 #bridge
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy

sys.setrecursionlimit(10000)

[vertex_num , sides_num] = list(map(int,input().split()))
sides = []

def _is_reachable( ver1, ver2, sides, sides_num):
	
#	print("sides_num:",sides_num ,"ver1 ",ver1,"ver2 ",ver2)
#	print(sides)
	for i in range(sides_num):
#		print(" :",sides[i])
		if( set(sides[i]) == set([ver2,ver1])):return 1
		if(sides[i][0] == ver2 or sides[i][1] == ver2):

			if( sides[i][0] == ver2 ):nex_ver = sides[i][1]
			else: nex_ver = sides[i][0]
			
			sides_buf = copy.deepcopy(sides)
			del sides_buf[i]
			
			if (_is_reachable( ver1, nex_ver, sides_buf, sides_num-1)  ):
				#print(ver1," and " , nex_ver , "is reachable")
				return 1
			else: continue
	return 0	
		 

for i in range(sides_num):
	sides.append( list(map(int,input().split())))


cnt = 0
for i in range(sides_num):
	sides_buf = copy.deepcopy( sides )
	del sides_buf[i]
#########	print("**",i,"**"," : ",  sides_buf)
	if(_is_reachable( sides[i][0],sides[i][1],sides_buf,sides_num-1)):
		cnt += 0
	else:
		cnt += 1 #bridge
print(cnt)

Submission status: Time Limit Exceeded

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 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: Time Limit Exceeded

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 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: Time Limit Exceeded

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 t[x][i]:
                dfs(i,t,v,j,m,n)

ans=0
for i in range(m):
    j=0
    t=[[False for _ in range(n)] for _ in range(n)]
    for a,b in ab:
        t[b-1][a-1],t[a-1][b-1]=True,True
    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)