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: Runtime Error

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
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)
def C(x):
    U=UnionFind(n)
    for i in range(m):
        if i==x:
            continue
        U.unite(ab[i][0]-1, ab[i][1]-1)
    for i in range(n):
        for j in range(m):
            if not U.same(i, j):
                return False
    return True
ans=0
for x in range(m):
    if not C(x):
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
n,m=map(int,input().split())
vertex=[[int(i) for i in l.split()] for l in sys.stdin]
def generate(x):
  root=[i for i in range(1,x+1)]
  size=[0]*x
def find(x):
  if root[x]==x:
    return x
  return find(root[x])
def check(x,y):
  return find(x)==find(y)
def union(x,y):
  x=find(x)
  y=find(y)
  if size[x]>=size[y]:
    root[y]=x
  else:
    root[x]=y
  if size[x]==size[y]:
    size[x]+=1
ans=0
for i in range(m):
  generate(n)
  for j in range(m):
    if j!=i:
      if check(vertex[j][0],vertex[j][1]):
        pass
      else:
        union(vertex[j][0],vertex[j][1])
  for j in range(n-1):
    if check(j,j+1)==0:
      pass
    else:
      ans+=1
      break
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd
n,m = map(int, input().split())
dic = dd(list)
l = []
cnt = 0
for _ in range(m):
  a,b = map(int, input().split())
  l.append(a,b)
  dic[a].add(b)
  dic[b].add(a)
def con(x):
  visit.add(x)
  for i in [j for j in dic[x] if j not in visited]:
    con(i)
  return visit == set(range(1,n+1))
for x,y in l:
  dic[x].remove(y)
  dic[y].remove(x)
  visit = set()
  if not con(x):
    cnt += 1
  dic[x].add(y)
  dic[y].add(x)
print(cnt)

Submission status: Runtime Error

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

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

def dfs(v, e):
  for x in v:
    if(len(e[x]) == 1):
      t = e[x][0]
      e[x] = []
      e[t].remove(x)
      v.remove(x)
      return dfs(v, e)+1
  return 0

print(dfs(v, edges))

Submission status: Runtime Error

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

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

def f(v, e):
  for x in v:
    if(len(e[x]) == 1):
      t = e[x][0]
      e[x] = []
      e[t].remove(x)
      v.remove(x)
      return f(v, e)+1
  return 0

print(dfs(v, edges))

Submission status: Runtime Error

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

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

def dfs(v, e):
  for x in v:
    if(len(e[x]) == 1):
      t = e[x][0]
      e[x] = []
      e[t].remove(x)
      v.remove(x)
      return dfs(v, e)+1
  return 0

print(f(v, edges))

Submission status: Runtime Error

Solution code:
# UnionFind構造

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
n, m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(n)]

count = 0
for i in range(len(lst)):
    llst = lst[:]
    del llst[i]
    a = UnionFind(n)
    for i in llst:
        a.union(i[0], i[1])
    rootset = set()
    for i in range(1, n):
        rootset.add(a.find(i))
    if len(rootset)==1:
        pass
    else:
        count += 1
        
print(count)

Submission status: Runtime Error

Solution code:
#075-C
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()
#UnionFindクラス
class UnionFind(object):
 
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
 
    def find(self, x):
  
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
  
    # xとyの根を結合させる
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
  
  # x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
    def same(self, x, y):
        return self.find(x) == self.find(y)
n,m=IL()
nl=[[] for j in range(n)]
for i in range(m):
    f,t=IL()
    nl.append([f-1,t-1])
ans=0
for i in range(m):
    t=nl[i]
    nl.remove(t)
    uf=UnionFind(n)
    for e in nl:
        uf.union(e[0],e[1])
    nl.append(t)
    for j in range(n):
        for k in range(n):
            if not uf.same(j,k):
                ans+=1
                break
            break
        break
print(ans)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


struct Edge{
	int from,to;
};

int V,E;
int boss[55],height[55];
Edge edge[55];

int get_boss(int id){
	if(boss[id] == id)return id; //自分が代表なら、自分の値を返す
	else{
		return boss[id] = get_boss(boss[id]); //代表でないなら、自分が所属する組織の代表を返しつつ、経路圧縮
	}
}

int is_same(int x,int y){
	return get_boss(x) == get_boss(y);
}

void unite(int x,int y){
	int boss_x = get_boss(x);
	int boss_y = get_boss(y);

	//既に同じグループなら何もしない
	if(boss_x == boss_y)return;

	//高さが高い方に吸収する
	if(height[x] > height[y]){

		boss[boss_y] = boss_x;

	}else if(height[x] < height[y]){

		boss[boss_x] = boss_y;

	}else{ //height[x] == height[y]

		boss[boss_y] = boss_x;
		height[x]++;
	}
}

void init(){

	for(int i = 0; i < V; i++){
		boss[i] = i;
		height[i] = 0;
	}
}

int main(){

	scanf("%d %d",&V,&E);

	for(int i = 0; i < E; i++){

		scanf("%d %d",&edge[i].from,&edge[i].to);
		edge[i].from--;
		edge[i].to--;
	}

	int ans = 0,num_group;

	for(int i = 0; i < E; i++){

		init();

		for(int k = 0; k < E; k++){
			if(k == i)continue;

			unite(edge[k].from,edge[k].to);
		}

		num_group = 0;

		for(int k = 0; k < V; k++){
			if(k == get_boss(k)){
				num_group++;
			}
		}
		if(num_group != 1)ans++;
	}

	printf("%d\n",ans);

	return 0;
}

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int MAX = 10;
int n, m;
struct edge{
    int to;
    int cost;
};
vector<edge> G[MAX];
int D[MAX];

void dijkstra(int s){
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    for(int i = 0; i < n; i++){
        D[i] = INF;
    }
    D[s] = 0;
    q.push({0, s});

    while(!q.empty()){
        pair<int, int> p = q.top();
        q.pop();
        int now = p.second;
        if(D[now] < p.first) continue;
        for(int i = 0; i < G[now].size(); i++){
            edge e = G[now][i];
            if(D[e.to] > D[now] + e.cost){
                D[e.to] = D[now] + e.cost;
                q.push({D[e.to], e.to});
            }
        }
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> n >> m;

    vector<int> A(m), B(m);

    for(int i = 0; i < m; i++){
        cin >> A[i] >> B[i];
        A[i]--; B[i]--;
        G[A[i]].push_back({B[i], 1});
        G[B[i]].push_back({A[i], 1});
    }

    int ans = 0;
    for(int i = 0; i < m; i++){
        for(int j = 0; j < G[A[i]].size(); j++){
            if(G[A[i]][j].to == B[i]){
                G[A[i]][j].cost = INF;
            }
        }
        for(int j = 0; j < G[B[i]].size(); j++){
            if(G[B[i]][j].to == A[i]){
                G[B[i]][j].cost = INF;
            }
        }

        dijkstra(0);

        for(int j = 0; j < n; j++){
            if(D[j] == INF){
                ans++;
                break;
            }
        }

        for(int j = 0; j < G[A[i]].size(); j++){
            if(G[A[i]][j].to == B[i]){
                G[A[i]][j].cost = 1;
            }
        }
        for(int j = 0; j < G[B[i]].size(); j++){
            if(G[B[i]][j].to == A[i]){
                G[B[i]][j].cost = 1;
            }
        }
    }
    
    cout << ans << endl;

    return 0;
}

Submission status: Runtime Error

Solution code:
from collections import deque

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

# construct indirectional graphs
edges = [[] for _ in range(n)]
for i, j in li:
    i -= 1
    j -= 1
    edges[i].append(j)
    edges[j].append(i)

edges2 = None

S = deque()
S.append([0])
while len(S) > 0:
    path = S.pop()
    # if full path,
    if len(path) == n:
        # used path set
        used = set()
        for i, j in zip(path[:-1], path[1:]):
            used |= {(i, j)}
        # delete unused edges
        if edges2 == None:
            edges2 = used
        else:
            edges2 = edges2 & used
        continue
    for v in edges[path[-1]]:
        if v not in path:
            S.append(path + [v])

ans = len(edges2)

print(ans)

Submission status: Runtime Error

Solution code:
from UnionFind import UnionFind

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

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

mat = [[0]*N for _ in range(N)]
for s, g in edges:
    mat[s][g] = 1
    mat[g][s] = 1

ans = 0

for i in range(M):
    uni = UnionFind(N)

    for j in range(M):
        if i != j:
            uni.union(edges[j][0], edges[j][1])

    if not all(uni.find(0) == uni.find(x) for x in range(N)):
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
from copy import deepcopy

N,M = map(int,input().split())
Matrix = [[False for x in range(N)] for j in range(N)]

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

INF = 63
ans = 0
for i in range(M) :
    Matrix_duplicated = deepcopy(Matrix)
    a,b = Path[i]
    Matrix_duplicated[a][b] = False
    Matrix_duplicated[b][a] = False
    Distance = [INF for i in range(N)]
    Distance[0] = 0
    Queue = deque([0])
    while Queue :
        now = Queue.popleft()
        Visited.append(now)
        for i in range(N) :
            if Matrix_duplicated[now][i] :
                Matrix_duplicated[now][i] = False
                Matrix_duplicated[i][now] = False
                Distance[i] = min(Distance[now]+1, Distance[i])
                Queue.append(i)
    if INF in Distance :
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
class UnionFindWithRank:
    # par: 親の番号(はじめ par[i]==i つまりすべての頂点が根)
    def __init__(self, size:int):
        self.par = [-1]*size
        self.rank = [0]*size
        for i in range(size):
            self.par[i] = i
    
    def root(self, x:int)->int:
        """根を求める"""
        if self.par[x] == x: # if root
            return x
        else:
            self.par[x] = self.root(self.par[x]) # 経路圧縮
            return self.par[x]
        
    def isSame(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)
    
    def unite(self, x:int, y:int):
        """x と y の属する集合を併合"""
        root_x = self.root(x)
        root_y = self.root(y)
        if root_x == root_y: return
        
        # 短いほうを長いほうにくっつける
        if self.rank[root_x] < self.rank[root_y]:
            self.par[root_x] = root_y
        else:
            self.par[root_y] = root_x
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_x] += 1
                

##### main #####
N,M = map(int, input().split())
a,b = [0]*M, [0]*M
for i in range(M):
    ai,bi = map(int, input().split())
    a[i],b[i] = ai-1, bi-1
    
ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if i==j: continue # この辺はパス
        uf.unite(a[j], b[j])
    bridge = False
    for i in range(N):
        if not uf.isSame(0,i):
            bridge = True
    if bridge:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import math
import sys
import bisect

N, M = [int(x) for x in input().split()]
A = [None] * M
B = [None] * M
AB = [[0] * N for _ in range(N)]

for i in range(M):
    a,b = [int(x) for x in input().split()]
    A[i] = a - 1
    B[i] = b - 1
    AB[a - 1][b - 1] = 1
    AB[b - 1][a - 1] = 1

def isRenketsu(MAT):
    openNode = {0}
    reachableNode = {0}

    while(len(openNode) != 0):
        n = openNode.pop()
        for i in range(M):
            if MAT[n][i] == 1:
                if i in reachableNode:
                    pass
                else:
                    openNode.add(i)
                    reachableNode.add(i)
    return len(reachableNode) == N


ret = 0
for i in range(M):
    AB[A[i]][B[i]] = 0
    AB[B[i]][A[i]] = 0
    if isRenketsu(AB) == False:
        ret += 1
    AB[A[i]][B[i]] = 1
    AB[B[i]][A[i]] = 1

print(ret)

Submission status: Runtime Error

Solution code:
def DFS(N, copyedge):
    matrix = [[] for i in range(M)]
    for a, b in copyedge:
        matrix[a].append(b)
        matrix[b].append(a)
        
    check = [True]*N
    check[0] = False
    Que = [0]

    while len(Que) != 0:
        now = Que.pop()
        for i in matrix[now]:
            if check[i] == True:
                check[i] = False
                Que.append(i)
    if True not in check:
        return 0
    else:
        return 1
            
        

ans = 0
N, M = map(int, input().split())
edge = []

for i in range(M):
    edge.append([int(i) - 1 for i in input().split()])
    
for i in range(M):
    copyedge = edge[:i] + edge[i+1:] 
    ans += DFS(N, copyedge)
print(ans)

Submission status: Runtime Error

Solution code:
def solve(N, M, ABs):
    ans = 0
    for i in range(M):
        m = {j: j for j in range(M)}
        for k, (a, b) in enumerate(ABs):
            a -= 1
            b -= 1
            if k == i:
                continue
            d = min(m[a], m[b])
            for mk in m:
                if m[mk] == m[a] or m[mk] == m[b]:
                    m[mk] = d
        if len(set(m.values())) != 1:
            ans += 1
    return ans

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, ABs))

Submission status: Runtime Error

Solution code:
def ABC075C():
    N, M = map(int, input().split())
    graf = [[10000000 for i in range(N)] for j in range(N)]
    for i in range(M):
        graf[i][i] = 0
    inputs = []
    for i in range(M):
        a, b = map(int, input().split())
        inputs.append([a, b])
        graf[a - 1][b - 1] = 1
        graf[b - 1][a - 1] = 1
    import copy
    ans = 0
    for l in range(M):
        key = 1
        this_graf = copy.deepcopy(graf)
        this_graf[inputs[l][0] - 1][inputs[l][1] - 1] = 10000000
        this_graf[inputs[l][1] - 1][inputs[l][0] - 1] = 10000000
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    this_graf[i][j] = min(this_graf[i][j], this_graf[i][k] + this_graf[k][j])
        for i in range(N):
            for j in range(N):
                if this_graf[i][j] >= 100000:
                    ans += 1
                    key = 1
                    break
            if key == 1:
                break

    print(ans)
ABC075C()

Submission status: Runtime Error

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

def DFS(v, ab_list, DFS_list):
    DFS_list[v] = True
    for j in ab_list[v]:
        if not DFS_list[j]:
            DFS(j, ab_list, DFS_list)

ans = 0
for i in range(M):
    ab_list = [[] for i in range(N)]
    for j in range(M):
        if i != j:
            k = ab[j]
            ab_list[k[0] - 1].append(k[1] - 1)
            ab_list[k[1] - 1].append(k[0] - 1)
            
    DFS_list = [False] * N
    
    DFS(i, ab_list, DFS_list)
    
    if False in DFS_list:
        ans += 1
print(ans)

Submission status: Runtime Error

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

ans = 0
for i in range(M):
    ab_list = [[] for i in range(N)]
    for j in range(M):
        if i != j:
            k = ab[j]
            ab_list[k[0] - 1].append(k[1] - 1)
            ab_list[k[1] - 1].append(k[0] - 1)
            
    DFS_list = [False] * N
    
    def DFS(v):
        DFS_list[v] = True
        for j in ab_list[v]:
            if not DFS_list[j]:
                DFS(j)
    DFS(i)
    if False in DFS_list:
        ans += 1
print(ans)

Submission status: Runtime Error

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

ans = 0
for i in range(M):
    ab_list = [[] for i in range(N)]
    for j in range(M):
        if i != j:
            k = ab[j]
            ab_list[k[0] - 1].append(k[1] - 1)
            ab_list[k[1] - 1].append(k[0] - 1)
            
    DFS_list = [False for j in range(N)]
    
    def DFS(v):
        DFS_list[v] = True
        for j in ab_list[v]:
            if not DFS_list[j]:
                DFS(j)
    DFS(i)
    if False in DFS_list:
        ans += 1
print(ans)

Submission status: Runtime Error

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

ans = 0
for i in range(M):
    ab_list = [[] for i in range(N)]
    for j in range(M):
        if i != j:
            k = ab[j]
            ab_list[k[0] - 1].append(k[1] - 1)
            ab_list[k[1] - 1].append(k[0] - 1)
            
    DFS_list = [0 for j in range(N)]
    DFS_list[i] = 0
    def DFS(v):
        DFS_list[v] = 1
        for j in ab_list[v]:
            if DFS_list[j] == 0:
                DFS(j)
    DFS(i)
    if sum(DFS_list) != N:
        ans += 1
print(ans)

Submission status: Runtime Error

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

ans = 0
for i in range(M):
    ab_list = [[] for i in range(N)]
    for j in range(M):
        if i != j:
            k = ab[j]
            ab_list[k[0] - 1].append(k[1] - 1)
            ab_list[k[1] - 1].append(k[0] - 1)
            
    DFS_list = [0 for j in range(N)]
    DFS_list[i] = 0
    def DFS(v):
        for j in ab_list[v]:
            if DFS_list[j] == 0:
                DFS_list[j] = 1
                DFS(j)
    DFS(i)
    if sum(DFS_list) != N:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
i = 0
while:
  i += 1

Submission status: Runtime Error

Solution code:
while:
  1

Submission status: Runtime Error

Solution code:
a

Submission status: Runtime Error

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

ans = 0
for i in range(M):
    ab_list = [[] for i in range(N)]
    for j in range(M):
        if i != j:
            k = ab[j]
            ab_list[k[0] - 1].append(k[1] - 1)
            ab_list[k[1] - 1].append(k[0] - 1)
            
    DFS_list = [0 for i in range(N)]
    DFS_list[i] = 0
    def DFS(v):
        for j in ab_list[v]:
            if DFS_list[j] == 0:
                DFS_list[j] = 1
                DFS(j)
    DFS(i)
    if sum(DFS_list) != N:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import collections
N = int(input())
A = collections.Counter(list(map(int, input().split())))
seihou = []
tyouhou = []
ans = 0

for i in A.keys():
    if A[i] >= 2:
        tyouhou.append(i)
    if A[i] >= 4:
        seihou.append(i)

if len(seihou) >= 1:
    ans = max(seihou)**2

if len(tyouhou) >= 2:
    c = max(tyouhou)
    tyouhou.remove(c)
    ans = max(ans, c*max(tyouhou))
print(ans)

Submission status: Runtime Error

Solution code:
cnt = 0
def dfs(g , start,N):
    global cnt
    visited = [False for i in range(N)]
    stack =[]
    stack.append(start)

    while stack:
        v = stack.pop()
        visited[v] = True


        for i in range(N):
            if g[v][i] == 1 and visited[i] ==False:
                stack.append(i)

    for i in range(N):
        if visited[i] == False:
            cnt += 1
            break


N,M = map(int,input().split())
g = [ [0 for i in range(N)] for j in range(N)]
a,b = [0] * N,[0] * N

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

for i in range(M):

    g[a[i]][b[i]] -= 1
    g[b[i]][a[i]] -= 1

    dfs(g,0,N)

    g[a[i]][b[i]] += 1
    g[b[i]][a[i]] += 1

print(cnt)

Submission status: Runtime Error

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

# 0-indexed
visited = [False]*n
aa = []
bb = []
edge = []
for i in range(7):
    edge.append([False]*7)
"""
edge = [[False]*7]*7
"""

for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    aa.append(a)
    bb.append(b)
    edge[a][b] = True
    edge[b][a] = True
    """
    for l in edge:
        print(l)
    print('')
    """

def dfs(vertex):
    visited[vertex] = True
    for i in range(n):
        if edge[vertex][i] and not visited[i]:
            #print(i, end=' ')
            dfs(i)

res = 0
for i in range(m):
    visited = [False]*n
    edge[aa[i]][bb[i]] = False
    edge[bb[i]][aa[i]] = False
    dfs(0)
    if not visited==[True]*n:
        res += 1
    #print(visited)
    edge[aa[i]][bb[i]] = True
    edge[bb[i]][aa[i]] = True

print(res)

Submission status: Runtime Error

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

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

# 入力値の頂点ペア(辺)を格納する配列
a = [0] * N
b = [0] * N
# 頂点ペアが隣接しているかどうかを格納する配列
graph = [[False for i in range(N)] for j in range(N)]
# ある頂点が訪問済かどうかを格納する配列
visited = [False] * N

# 入力値の頂点ペア(辺)を格納していくループ
for i in range(M):
    a[i], b[i] = map(int, input().split())
    # 添字に合わせて入力値から1減らしておく
    a[i] -= 1
    b[i] -= 1
    # 入力値の内容に合わせて、隣接していることを記録
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True

# 連結かどうか(全ての頂点が訪問済かどうか)を判定するDFS
def dfs(v):
    # 関数内で使用する変数のglobal宣言
    global graph
    global visited
    # 通った頂点は訪問済にする
    visited[v] = True
    for v2 in range(N):
        # 隣接していないor訪問済はやる意味ないのでcontinue
        if graph[v][v2] == False or visited[v2] == True:
            continue
        # 調べる必要のある箇所は再帰的に調べていく
        dfs(v2)

ans = 0
# 各辺について、橋かどうかを判定していくループ
for i in range(M):
    # まず該当の辺を外す(この状態で連結ではなくなってしまえばそれは橋)
    graph[a[i]][b[i]] = False
    graph[b[i]][a[i]] = False
    # 訪問済判定を初期化
    for j in range(N):
        visited[j] = False
    # 連結かどうか(全ての頂点が訪問済かどうか)を判定するDFS
    dfs(0)
    # 各頂点について、訪問済かどうかを確認していく
    bridge = False
    for j in range(N):
        # 頂点で一つでも未訪問の箇所があれば橋と判定する
        if visited[j] == False:
            bridge = True
    if bridge:
        ans += 1
    # 外した辺を元に戻す
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True

print(ans)

Submission status: Runtime Error

Solution code:
import copy


def dfs(array, pos, res_array):
    res = False
    if False not in res_array:
        return True
    elif res_array[pos]:
        return False
    else:
        res_array[pos] = True
        for i in array[pos]:
            if dfs(array, i, res_array):
                res = True
    return res


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

array = [[int(x) for x in input().split()] for x in range(m)]
res_array = [True] + [False for x in range(n)]

res = 0
for i in range(len(array)):
    adj_array = [[] for x in range(n + 1)]
    tmp_array = array[:i] + [[]] + array[i+1:]
    for item in tmp_array:
        if len(item) == 0:
            continue
        adj_array[item[0]].append(item[1])
        adj_array[item[1]].append(item[0])
    res += 1 ^ dfs(adj_array, -i-1, copy.copy(res_array))

print(res)

Submission status: Runtime Error

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

edgeset  = []
for i in range(M):
    a,b = map(int,input().split())
    G[a-1][b-1] = 1
    G[b-1][a-1] = 1
    edgeset.append([a,b])
    
visited = None
def dfs(v):
    visited[v] = 1
    for u, e in enumerate(G[v]):
        if e == 0 or visited[u] == 1:
            continue
        dfs(u)
ans = 0

for j in edgeset:
    G[j[0] - 1][j[1] - 1]= 0
    G[j[1] - 1][j[0] - 1]= 0
    visited = [[0] * N]
    dfs(0)   
    G[j[0] - 1][j[1] - 1]= 1
    G[j[1] - 1][j[0] - 1]= 1
    if 0 in visited:
        ans+= 1
print(ans)

Submission status: Runtime Error

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 and l[j] != 0:
            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 max(l) == 0:
            break
        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: Runtime Error

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

g = {}
E = []
for _ in range(N):
    line = input().split(" ")
    a = line[0]
    b = line[1]
    E.append((a,b))
    if not a in g:
        g[a] = []
    g[a].append(b)

    if not b in g:
        g[b] = []
    g[b].append(a)

def judge(a, b):
    flags = {}
    for v in g:
        flags[v] = False
    q = [a]
    flags[a] = True
    while len(q)>0:
        v = q.pop(0)
        for u in g[v]:
            if (v==a and u==b) or (v==b and u==a):
                continue
            elif not flags[u]:
                flags[u] = True
                q.append(u)
    ret = True
    for v in flags:
        ret = ret and flags[v]

    return not ret

cnt = 0
for e in E:
    if judge(e[0],e[1]):
        cnt += 1

print(cnt)

Submission status: Runtime Error

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(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(start, path,loops)
            path.pop()

#入力
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(i,[i],loops)
#ループに属する辺(橋でない辺)の検索
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))