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())
a1=[0]*m
b1=[0]*m
for i in range(m):
  a1[i],b1[i]=map(int,input().split())
ans=0
a,b=a1,b1
for i in range(m):
  a=[int(a1[i]) for i in range(m)]
  b=[int(b1[i]) for i in range(m)]
  a.pop(i)
  b.pop(i)
  for j in range(n):
    for k in range(n):
      if j!=k
        for l1,l2 in zip(a,b):
          if l1==j:
            j=l2
          if j==k:
            break
        if l1!=j and j!=k:
          ans+=1
          break
        elif j==k:
          break
      if l1!=j and j!=k:
          break
      elif j==k:
        break
    if l1!=j and j!=k:
      break
    elif j==k:
      break
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a1=[0]*m
b1=[0]*m
for i in range(m):
  a1[i],b1[i]=map(int,input().split())
ans=0
a,b=a1,b1
for i in range(m):
  a,b=a1,b1
  a.pop(i)
  b.pop(i)
  for j in range(n):
    for k in range(n):
      for l1,l2 in zip(a,b):
        if l1==j:
          j=l2
        if j==k:
          break
      if l1!=j and j!=k:
        ans+=1
        break
      elif j==k:
        break
    if l1!=j and j!=k:
        break
    elif j==k:
      break
  a,b=a1,b1
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a1=[0]*m
b1=[0]*m
for i in range(m):
  a1[i],b1[i]=map(int,input().split())
ans=0
a,b=a1,b1
for i in range(m):
  a,b=a1,b1
  a.pop(a[i])
  b.pop(b[i])
  for j in range(n):
    for k in range(n):
      for l1,l2 in zip(a,b):
        if l1==j:
          j=l2
        if j==k:
          break
      if l1!=j and j!=k:
        ans+=1
        break
      elif j==k:
        break
    if l1!=j and j!=k:
        break
    elif j==k:
      break
  a,b=a1,b1
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a1=[0]*m
b1=[0]*m
for i in range(m):
  a1[i],b1[i]=map(int,input().split())
ans=0
a,b=a1,b1
for i in range(m):
  a.pop(a[i])
  b.pop(b[i])
  for j in range(n):
    for k in range(n):
      for l1,l2 in zip(a,b):
        if l1==j:
          j=l2
        if j==k:
          break
      if l1!=j and j!=k:
        ans+=1
        break
      elif j==k:
        break
    if l1!=j and j!=k:
        break
    elif j==k:
      break
  a,b=a1,b1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
k = [[] for _ in range(N)]
flst = [list([0] * 2) for _ in range(M)]

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

d = [0] * M
def dfs(v):
    d[v] = 1
    for i in range(len(k[v])):
        if d[k[v][i]] == 0:
            dfs(k[v][i])
    return
ans = 0
for i in range(M):
    tmp1 = k[flst[i][0] - 1].index(flst[i][1] - 1)
    tmp2 = k[flst[i][1] - 1].index(flst[i][0] - 1)
    k[flst[i][0] - 1].pop(tmp1)
    k[flst[i][1] - 1].pop(tmp2)
    dfs(0)
    if sum(d) != N:
        ans += 1

    d = [0] * M
    k[flst[i][0] - 1].append(flst[i][1] - 1)
    k[flst[i][1] - 1].append(flst[i][0] - 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)]


def UF_make(Graph):
    ret=[-1]*(N+1)
    for i in range(len(Graph)):
        v1=[ret[Graph[i][0]],Graph[i][0]][ret[Graph[i][0]]<0]
        v2=[ret[Graph[i][1]],Graph[i][1]][ret[Graph[i][1]]<0]
        if v1!=v2:
            if ret[v1]>ret[v2]:
                v1,v2=v2,v1
            ret[v1]+=ret[v2]
            ret[v2]=v1
    return ret

def UF_check(Array,V1,V2):
    v1=[Array[V1],V1][Array[V1]<0]
    v2=[Array[V2],V2][Array[V2]<0]
    return(True if v1==v2 else False)

def UF(Graph,V1,V2):
    return(UF_check(UF_make(Graph),V1,V2))

ans=0
for i in range(M):
    if UF(AB[:i]+AB[i+1:],AB[i][0],AB[i][1])==False:
        ans+=1

print(ans)

Submission status: Runtime Error

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):
    g=[[] for _ in range(n)]
    for j in range(m):
        if i==j:
            continue
        g[e[j][0]-1].append(e[j][1])
        g[e[j][1]-1].append(e[j][0])
    visited=[0]*n
    visited[0]=1
    q=[1]
    while len(q)>0:
        a=pop(q)
        visited[a-1]=1
        for k in g[a-1]:
            if visited[k-1]==0:
                q+=[k]
    if sum(visited)!=n:
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
e=[]
for i in range(n):
    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 and visited[q[1]-1]==0:
                        ntmp.append(q)
        t=tmp
        nall=ntmp
    if sum(visited)!=n:
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
e=[]
for i in range(n):
    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
    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:
                    ntmp.append(q)
        t=tmp
        nall=ntmp
    if sum(visited)!=n:
        ans+=1
print(ans)

Submission status: Runtime Error

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

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

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

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

print(cnt)

Submission status: Runtime Error

Solution code:
atodeyaruyo

Submission status: Runtime Error

Solution code:
from collections import deque
N, M = map(int, input().split())

graph = [set() for _ in range(N + 1)]
edge = [[] for _ in range(N + 1)]
for m in range(M):
    a, b = map(int, input().split())
    graph[a].add(b)
    graph[b].add(a)
    edge[m + 1] = [a, b]

ans = 0
for m in range(M):
    Bridge = True
    fr, to = edge[m + 1][0], edge[m + 1][1]
    V = {fr} | set(graph[fr]) - {to}
    que = set(graph[fr]) - {to}
    while que:
        node = que.pop()
        for new_node in graph[node]:
            if new_node == to:
                Bridge = False
                break
            if new_node not in V:
                que.add(new_node)
                V.add(new_node)
        else:
            continue
        break
    if Bridge:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
N, M = map(int, input().split())

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

ans = 0
for m in range(M):
    Bridge = True
    fr, to = edge[m + 1][0], edge[m + 1][1]
    V = {fr} | set(graph[fr]) - {to}
    que = deque(set(graph[fr]) - {to})
    while que:
        node = que.pop()
        for new_node in graph[node]:
            if new_node == to:
                Bridge = False
                break
            if new_node not in V:
                que.append(new_node)
                V.add(new_node)
        else:
            continue
        break
    if Bridge:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
N, M = map(int, input().split())

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

ans = 0
for m in range(M):
    Bridge = True
    fr, to = edge[m + 1][0], edge[m + 1][1]
    V = {fr} | set(graph[fr]) - {to}
    que = deque(set(graph[fr]) - {to})
    while que:
        node = que.pop()
        for new_node in graph[node]:
            if new_node == to:
                Bridge = False
                break
            if new_node not in V:
                que.append(new_node)
                V.add(new_node)
        else:
            continue
    if Bridge:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
from fractions import gcd
from copy import deepcopy
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  infile.readline().rstrip()
 =  list(infile.readline().rstrip())

## 数値
 =  int(infile.readline())
 =  map(int, infile.readline().split())
 =  list(map(int, infile.readline().split()))
 =  [list(map(int,list(infile.readline().split()))) for i in range(N)]
"""

class Node():
    def __init__(self, ch):
        self.ch_list = [ch]
        self.visited = False

infile = open("input.txt")
N, M = map(int, infile.readline().split())
node_list = [0] * N

edge_list =  [list(map(int,list(infile.readline().split()))) for i in range(M)]
for edge in edge_list:
    # リストのインデックスとnodeのidを統一しておく
    edge[0] -= 1
    edge[1] -= 1
for edge in edge_list:
    a, b = edge
    if node_list[a] == 0:
        node_list[a] = Node(b)
    else:
        if b not in node_list[a].ch_list:
            node_list[a].ch_list.append(b)

    if node_list[b] == 0:
        node_list[b] = Node(a)
    else:
        if a not in node_list[b].ch_list:
            node_list[b].ch_list.append(a)

def dfs(current_idx, ch_num, n_list):
    current = n_list[current_idx]
    if current == 0:
        return ch_num
    if current.visited:
        return ch_num
    ch_num += 1
    current.visited = True
    # print(current_idx + 1, list(map(lambda x: x + 1, current.ch_list)), ch_num)
    for idx in current.ch_list:
        # print("before", current_idx + 1, idx + 1, ch_num)
        ch_num = dfs(idx, ch_num, n_list)
        # print("after", current_idx + 1, idx + 1, ch_num)
    return ch_num

base_num = dfs(0, 0, deepcopy(node_list))

cnt = 0
for edge in edge_list:
    nl = deepcopy(node_list)
    a, b = edge
    nl[a].ch_list.remove((b))
    nl[b].ch_list.remove((a))
    num = dfs(0, 0, nl)
    # print(a + 1, b + 1, num)
    if num != base_num:
        cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <map>
#include <queue>
#include <list>
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
#define crep(i) for(char i='a';i<='z';i++)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define psortfirst(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.first<b.first;});
#define ALL(x) (x).begin(),(x).end()
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
using namespace std;
using pii  = pair<int,int>;
long long gcd(long long a, long long b){return (b == 0 ? a : gcd(b, a%b));}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
typedef long long ll;
#define MOD 1000000007
#define EPS 10e-8

ll N,M,A[3000],B[3000],C=0;
vector<vector<ll>> TEN(57);
ll touri[57];

void kentou(ll a,ll b,ll t){
  t++;
  touri[a]=1;
  if(a==b){
    C++;
    return;
  }
  rep(i,TEN[a].size()){
    if(touri[TEN[a][i]]==0 && (t!=1 || TEN[a][i]!=b)){
      kentou(TEN[a][i],b,t);
    }
  }
}

int main(){
  cin >> N >> M;
  rep(i,M){
    cin >> A[i] >> B[i];
    TEN[A[i]].push_back(B[i]);
    TEN[B[i]].push_back(A[i]);
  }
  rep(i,M){
    kentou(A[i],B[i],0);
    rep(j,57){
      touri[j]=0;
    }
  }
  cout << M-C <<  endl;
}

Submission status: Runtime Error

Solution code:
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<iomanip>
#include<stack>
#include<queue>
#include<ctime>
#include<osstream>//
#include<isstream>// 
using namespace std;
const int maxn=500;
vector<int> G[maxn];
int dfn[maxn],low[maxn];
int n,m,u,v,dep,ans;

void init()
{
    dep=ans=0;
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    for(int i=0;i<=n;i++) G[i].clear();
}

void Tarjan(int u,int fa)
{
    dfn[u]=low[u]=++dep;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(!dfn[v]){
            Tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u]) ans++;
        }else if(v!=fa)
            low[u]=min(low[u],dfn[v]);
    }
}

int main()
{
    while(cin>>n>>m)
    {
        init();
        for(int i=0;i<m;i++){
            cin>>u>>v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        Tarjan(1,-1);
        cout<<ans<<endl;
    }
    return 0;
}

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import dijkstra
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

graph = [[0]*(n+1) for _ in range(n+1)]
for a, b in ab:
    graph[a][b] = 1

ans = 0
inf = 10**9

for a, b in ab:
    graph[a][b] = inf
    dist = dijkstra(graph, indices = a, directed = False)
    if dist[b] >= inf:
        ans += 1
    graph[a][b] = 1

print(ans)

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import dijkstra
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

graph = [[0]*(n+1) for _ in range(n+1)]
for a, b in ab:
    graph[a-1][b-1] = 1

ans = 0
inf = 10**9

for a, b in ab:
    graph[a][b] = inf
    dist = dijkstra(graph, indices = a, directed = False)
    if dist[b] >= inf:
        ans += 1
    graph[a][b] = 1

print(ans)

Submission status: Runtime Error

Solution code:
def dfs(num):
  global visited
  for next_num in num:
    if visited[next_num]:
      continue
    if has_edge[num][next_num]:
      visited[next_num]=1
      dfs(next_num)
      
N,M = map(int,input().split())
ab = []
edge = [[] for x in range(N+1)]
has_edge = [[0 for x in range(N+1)] for x in range(N+1)]
for i in range(M):
  a,b = map(int,input().split())
  ab.append([a,b])
  edge[a].append(b)
  edge[b].append(a)
  has_edge[a][b] = 1
  has_edge[b][a] = 1
  
count = 0
for a,b in ab:
  visited = [0 for x in range(N+1)]
  visited[1] = 1
  has_edge[a][b] = 0
  has_edge[b][a] = 0
  dfs(1)
  if sum(visited) != N:
    count += 1
  has_edge[a][b] = 1
  has_edge[b][a] = 1
print(count)

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
raw = ['/' * (w+2)]
for hi in range(h):
  raw.append('/' + input() + '/')
raw += ['/' * (w+2)]
#print(raw)
for hi in range(h):
  ans = ''
  pre = raw[hi]
  now = raw[hi+1]
  pst = raw[hi+2]
  for wi in range(w):
    if now[wi+1] == '#':
      cnt = '#'
    else:
      cnt = 0
      can = pre[wi:wi+3] + now[wi:wi+3] + pst[wi:wi+3]
      for j in range(9):
        if can[j] == '#':
          cnt += 1
    ans += str(cnt)
  print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9+7)
def check(graph,seen,now):
    seen[now] = True 
    for i in range(len(graph[now])):
        if seen[i] :
            continue
        if graph[now][i] == 0 :
            continue
        check(graph,seen,i)
    return seen


#入力
N,M = map(int,input().split())
para = [[i for i in map(int,input().split())] for j in range(M)]
graph =[[0 for i in range(N)] for  j in range(M)]
for i in range(M):
    graph[para[i][0]-1][para[i][1]-1] = 1
    graph[para[i][1]-1][para[i][0]-1] = 1 

#seen = [False]*(N)
ans = 0
for i in range(M):
    seen = [False]*(N)
    graph[para[i][0]-1][para[i][1]-1] = 0
    graph[para[i][1]-1][para[i][0]-1] = 0
    if False in check(graph,seen,0):
        ans += 1
    graph[para[i][0]-1][para[i][1]-1] = 1
    graph[para[i][1]-1][para[i][0]-1] = 1 
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
def check(graph,seen,now):
    seen[now] = True 
    for i in range(len(graph[now])):
        if seen[i] :
            continue
        if graph[now][i] == 0 :
            continue
        check(graph,seen,i)
    return seen


#入力
N,M = map(int,input().split())
para = [[i for i in map(int,input().split())] for j in range(M)]
graph =[[0 for i in range(N)] for  j in range(M)]
for i in range(M):
    graph[para[i][0]-1][para[i][1]-1] = 1
    graph[para[i][1]-1][para[i][0]-1] = 1 

#seen = [False]*(N)
ans = 0
for i in range(M):
    seen = [False]*(N)
    graph[para[i][0]-1][para[i][1]-1] = 0
    graph[para[i][1]-1][para[i][0]-1] = 0
    if False in check(graph,seen,0):
        ans += 1
    graph[para[i][0]-1][para[i][1]-1] = 1
    graph[para[i][1]-1][para[i][0]-1] = 1 
print(ans)

Submission status: Runtime Error

Solution code:
"""
一本を外して、それが非連結であるのかの判定をしていく
"""
#連結かどうかの判定
#得られている辺をたどって全ノードにたどり着けたらOK
def check(graph,seen,now):
    seen[now] = True 
    for i in range(len(graph[now])):
        if seen[i] :
            continue
        if graph[now][i] == 0 :
            continue
        check(graph,seen,i)
    return seen


#入力
N,M = map(int,input().split())
para = [[i for i in map(int,input().split())] for j in range(M)]
graph =[[0 for i in range(N)] for  j in range(M)]
for i in range(M):
    graph[para[i][0]-1][para[i][1]-1] = 1
    graph[para[i][1]-1][para[i][0]-1] = 1 

#seen = [False]*(N)
ans = 0
for i in range(M):
    seen = [False]*(N)
    graph[para[i][0]-1][para[i][1]-1] = 0
    graph[para[i][1]-1][para[i][0]-1] = 0
    if False in check(graph,seen,0):
        ans += 1
    graph[para[i][0]-1][para[i][1]-1] = 1
    graph[para[i][1]-1][para[i][0]-1] = 1 
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

def dfs(graph, start, goal):
    stack = deque()
    push, pop = stack.append, stack.pop
    push(start)
    visited = [False for i in range(N)]
    visited[start] = True
    
    while stack:
        a = pop()
        for b in graph[a].keys():
            if a in [start, goal] and b in [start, goal]:
                continue
            elif b == goal:
                return True
            elif not visited[b]:
                push(b)
                visited[b] = True
    return False

N,M = map(int, input().split())
graph = {}
bridge = []
for i in range(M):
    a,b = map(int, input().split())
    if a not in graph:
        graph[a] = {}
    if b not in graph:
        graph[b] = {}
    graph[a][b] = graph[b][a] = 1
    bridge.append([a,b])

ans = 0
for a,b in bridge:
    ans += not dfs(graph, a, b)
print(ans)

Submission status: Runtime Error

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

C = []

for i in range(M):
    l = input().split()
    C.append([int(x) - 1 for x in l])

# print(N, M, C)

def visit(s, G, visited):
    # print(s, G, visited)
    visited.add(s)
    for g in G:
        if g[0] in visited:
            n = g[1]
            G.remove(g)
            return visit(n, G, visited)
        elif g[1] in visited:
            n = g[0]
            G.remove(g)
            return visit(n, G, visited)
    return

ans = 0
for i in range(N):
    D = []
    for j in range(N):
        if i != j:
            D.append(C[j])
    visited = set()
    visit(0, D, visited)
    # print(i, len(visited))
    if len(visited) != N:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, N):
        # negative value: represents the root of a tree; its absolute value is the size of the tree
        # positive value: the parent's index
        self.vertices = [-1 for _ in range(N)]
        self.rank = [0] * N
        
    def find(self, v):
        if self.vertices[v] < 0: # v is a root
            return v
        else:
            # path compression: reconnect v to the root
            self.vertices[v] = self.find(self.vertices[v])
            return self.vertices[v]
        
    def union(self, u, v):
        s1 = self.find(u) # the root of the tree including vertex u
        s2 = self.find(v) # the root of the tree including vertex v
        
        if s1 == s2: # u and v is in the same tree
            return False
        
        if self.rank[s1] > self.rank[s2]: # the tree including u is taller
            self.vertices[s1] += self.vertices[s2] # update the size of the bigger tree
            self.vertices[s2] = s1
        else: # the tree including v is taller
            self.vertices[s2] += self.vertices[s1] # update the size of the bigger tree
            self.vertices[s1] = s2
            if self.rank[s1] == self.rank[s2]:
                self.rank[s2] += 1
        return True
        
    def is_connected(self, u, v):
        return self.find(u) == self.find(v)
    
    def size(self, v):
        return -self.vertices[self.find(v)]

N, M = map(int, input().split())
E = []
for _ in range(M):
    a, b = map(int, input().split())
    E.append((a, b))
    
ans = 0
for i in range(M):
    uf = UnionFind(N)
    edges = [e for j, e in enumerate(E) if j != i]
    for a, b in edges:
        uf.union(a, b)
    if len([v for v in uf.vertices if v < 0]) >= 2:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, N):
        # negative value: represents the root of a tree; its absolute value is the size of the tree
        # positive value: the parent's index
        self.vertices = [-1 for _ in range(N)]
        self.rank = [0] * N
        
    def find(self, v):
        if self.vertices[v] < 0: # v is a root
            return v
        else:
            # path compression: reconnect v to the root
            self.vertices[v] = self.find(self.vertices[v])
            return self.vertices[v]
        
    def union(self, u, v):
        s1 = self.find(u) # the root of the tree including vertex u
        s2 = self.find(v) # the root of the tree including vertex v
        
        if s1 == s2: # u and v is in the same tree
            return False
        
        if self.rank[s1] > self.rank[s2]: # the tree including u is taller
            self.vertices[s1] += self.vertices[s2] # update the size of the bigger tree
            self.vertices[s2] = s1
        else: # the tree including v is taller
            self.vertices[s2] += self.vertices[s1] # update the size of the bigger tree
            self.vertices[s1] = s2
            if self.rank[s1] == self.rank[s2]:
                self.rank[s2] += 1
        return True
        
    def is_connected(self, u, v):
        return self.find(u) == self.find(v)
    
    def size(self, v):
        return -self.vertices[self.find(v)]

N, M = map(int, input().split())
E = []
for _ in range(M):
    a, b = map(int, input().split())
    E.append((a, b))
    
ans = 0
for i in range(M):
    uf = UnionFind(N)
    edges = [e for j, e in enumerate(e) if j != i]
    for a, b in edges:
        uf.union(a, b)
    if len([v for v in uf.vertices if v < 0]) >= 2:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
g=[list() for _ in range(n+1)]
side=[list(map(int,input().split())) for i in range(m)]
for a,b in side:
	g[a].append(b)
	g[b].append(a)
cnt=0
def dfs(r,x,s):
	ed[x-1]=1
	for i in g[x]:
		if i!=r and s!={x,i} and ed[i-1]==0:dfs(x,i,s)
cnt=0
for i in range(m):
	ed=[0]*n
	dfs(0,i+1,set(side[i]))
	if 0 in ed:cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
g=[list() for _ in range(n+1)]
side=[list(map(int,input().split())) for i in range(m)]
for a,b in side:
	g[a].append(b)
	g[b].append(a)
cnt=0
def dfs(r,x,s):
	ed[x-1]=1
	for i in g[x]:
		if i!=r and s!={x,i}:dfs(x,i,s)
cnt=0
for i in side:
	ed=[0]*n
	dfs(0,1,set(i))
	if 0 in ed:cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
g=[list() for _ in range(n+1)]
side=[list(map(int,input().split())) for i in range(m)]
for a,b in side:
	g[a].append(b)
	g[b].append(a)
cnt=0
def dfs(r,x,s):
	ed[x-1]=1
	for i in g[x]:
		if i!=r and s!={x,i}:dfs(x,i,s)
cnt=0
for i in range(m):
	ed=[0]*n
	dfs(0,1,set(side[i]))
	if 0 in ed:cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
g=[list() for _ in range(n+1)]
side=[list(map(int,input().split())) for i in range(m)]
for a,b in side:
	g[a].append(b)
	g[b].append(a)
cnt=0
def dfs(r,x,s):
	ed[x-1]=1
	for i in g[x]:
		if i!=r and s!={x,i}:dfs(x,i,s)
cnt=0
for i in range(m):
	ed=[0]*n
	dfs(0,i+1,set(side[i]))
	if 0 in ed:cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a,B,ans = [[] for _ in range(n)],[],0
def solve(v,a,b):
    visited[v] = True
    for n in a[v]:
        if not visited[n] and set([v,n]) != set([a,b]):
            solve(n,a,b)

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

for i in range(m):
    visited = [True]+[False]*(n-1)
    a,b = B[i]
    solve(0,a,b)
    if visited != [True]*n:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
def f(L,res):
    for i in range(1,M+1):
        #print(i,L[i])
        if len(L[i]) == 1:
          L[L[i][0]].remove(i)
          L[i] = []
          res = f(L,res+1)
    return res


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

for i in range(M):
    a,b = map(int,input().split())
    L[a].append(b)
    L[b].append(a)
print(f(L,0))

Submission status: Runtime Error

Solution code:
const int limit = 50;

int n, m;
int a[limit], b[limit];

bool graph[limit][limit];
bool visited[limit];

void dfs(int v){
    visited[v] = true;
    for (int v2=0; v2<n;++v2){
        if (graph[v][v2]==false) continue;
        if (visited[v2]==true) continue;
        dfs(v2);
    }
}

int main(void){
    cin >> n >> m;
    for (int i=0; i<m; ++i){
        graph[a[i]][b[i]] = graph[b[i]][a[i]] = false;
        for (int j=0; j<n; ++j) visited[j] = false;
        dfs(0);
        bool bridge = false;
        for (j=0; j<n; ++j) if (visited[j] == false) bridge = true;
        if (bridge) ans += 1;
        graph[a[i]][b[i]] = graph[b[i]][a[i]] = true;
        }
    cout << ans << endl;
    return 0;
    }

Submission status: Runtime Error

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

x=[[] for i in range(n)]

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

ans=0

while True:
    idx,flg=0,0
    for i in x:
        if len(i)==1:
            flg=1
            x[i[0]-1].remove(idx+1)
            x[idx]=[]
            ans+=1
        idx+=1
    if flg==0:
        break
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
f = [True] * M
v = [0] * N
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if v[a] == 0:
        v[a] = b
    else:
        f[a] = False
        f[b] = False
        f[v[a]] = False

print(sum(f))

Submission status: Runtime Error

Solution code:
class UnionFind():
  def __init__(self):
    self.roots = {}
    self.nums = {}

  def find_root(self, a):
    if a not in self.roots:
      self.nums[a] = 1
      return a
    else:
      self.roots[a] = self.find_root(self.roots[a])
      return self.roots[a]

  def unite(self, a, b):
    root_a = self.find_root(a)
    root_b = self.find_root(b)
    n_a = self.nums[root_a]
    n_b = self.nums[root_b]
    if root_a == root_b:
      return
    else:
      if n_a > n_b: #多い方に合流させる
        self.roots[root_b] = root_a
        self.nums[root_a] = n_a + n_b
        del self.nums[root_b]
      else:
        self.roots[root_a] = root_b
        self.nums[root_b] = n_a + n_b
        del self.nums[root_a]
      return
  
  def is_union(self, a,b):
    return self.find_root(a) == self.find_root(b)

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

answer = 0
for i in range(N):
  temp = AB[:i] + AB[i+1:]
  ai, bi = AB[i]
  uf = UnionFind()
  for ab in temp:
    a,b = ab
    uf.unite(a,b)
  answer += not uf.is_union(ai, bi)


print(answer)