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:
# https://atcoder.jp/contests/abc075/tasks/abc075_c
class UnionFind():
    def __init__(self, N):
        self._root = [-1 for _ in range(N)]

    def find(self, x):
        if self._root[x] < 0: return x
        self._root[x] = self.find(self._root[x])
        return self._root[x]

    def unite(self, x, y):
        gx = self.find(x)
        gy = self.find(y)
        if gx == gy: return False
        if self._root[gx] > self._root[gy]:
            gx, gy = gy, gx
        self._root[gx] += self._root[gy]
        self._root[gy] = gx
        return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -(self._root[self.find(x)])

    def roots(self):
        return [i for i in self._root) if i < 0]


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

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

cnt = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i != j:
        uf.unite(nodes[j][0]-1, nodes[j][1]-1)
    cnt += (len(uf.roots()) != 1)
print(cnt)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc075/tasks/abc075_c
class UnionFind():
    def __init__(self, N):
        self._root = [-1 for _ in range(N)]

    def find(self, x):
        if self._root[x] < 0: return x
        self._root[x] == self.find(self._root[x])
        return self._root[x]

    def unite(self, x, y):
        gx = self.find(x)
        gy = self.find(y)
        if gx == gy: return False
        if self._root[gx] > self._root[gy]:
            gx, gy = gy, gx
        self._root[gx] += self._root[gy]
        self._root[gy] = gx
        return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -(self._root[self.find(x)])

    def roots(self):
        return [i for i in self._root if i < 0]


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

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

cnt = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i == j: continue
        uf.unite(nodes[j][0]-1, nodes[j][1]-1)
    cnt += (len(uf.roots()) != 1)
print(cnt)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc075/tasks/abc075_c
class UnionFind():
    def __init__(self, N):
        self._root = [-1 for _ in range(N)]

    def find(self, x):
        if self._root[x] < 0: return x
        self._root[x] == self.find(self._root[x])
        return self._root[x]

    def unite(self, x, y):
        gx = self.find(x)
        gy = self.find(y)
        if gx == gy: return False
        if self._root[gx] > self._root[gy]:
            gx, gy = gy, gx
        self._root[gx] += self._root[gy]
        self._root[gy] = gx
        return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -(self._root[self.find(x)])

    def roots(self):
        return [i for i in self._root) if i < 0]


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

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

cnt = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i == j: continue
        uf.unite(nodes[j][0]-1, nodes[j][1]-1)
    cnt += (len(uf.roots()) != 1)
print(cnt)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc075/tasks/abc075_c
class UnionFind():
    def __init__(self, N):
        self._root = [-1 for _ in range(N)]

    def find(self, x):
        if self._root[x] < 0: return x
        self._root[x] == self.find(self._root[x])
        return self._root[x]

    def unite(self, x, y):
        gx = self.find(x)
        gy = self.find(y)
        if gx == gy: return False
        if self._root[gx] > self._root[gy]:
            gx, gy = gy, gx
        self._root[gx] += self._root[gy]
        self._root[gy] = gx
        return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -(self._root[self.find(x)])

    def roots(self):
        return [i for i, x in enumerate(self._root) if x < 0]


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

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

cnt = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i != j:
           uf.unite(nodes[j][0]-1, nodes[j][1]-1)
    cnt += (len(uf.roots()) != 1)
print(cnt)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc075/tasks/abc075_c
class UnionFind():
    def __init__(self, N):
        self._root = [-1 for _ in range(N)]

    def find(self, x):
        if self._root[x] < 0: return x
        self._root[x] == self.find(self._root[x])
        return self._root[x]

    def unite(self, x, y):
        gx = self.find(x)
        gy = self.find(y)
        if gx == gy: return False
        if self._root[gx] > self._root[gy]:
            gx, gy = gy, gx
        self._root[gx] += self._root[gy]
        self._root[gy] = gx
        return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -(self._root[self.find(x)])

    def roots(self):
        return [i for i, x in emurate(self._root) if x < 0]


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

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

cnt = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i != j:
           uf.unite(nodes[j][0]-1, nodes[j][1]-1)
    cnt += (len(uf.roots()) != 1)
print(cnt)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc075/tasks/abc075_c
class UnionFind():
    def __init__(self, N):
        self._root = [-1 for _ in range(N)]

    def find(self, x):
        if self._root[x] < 0: return x
        self._root[x] == self.find(self._root[x])
        return self._root[x]

    def unite(self, x, y):
        gx = self.find(x)
        gy = self.find(y)
        if gx == gy: return False
        if self._root[gx] > self._root[gy]:
            gx, gy = gy, gx
        self._root[gx] += self._root[gy]
        self._root[gy] = gx
        return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -(self._root[self.find(x)])

    def roots(self):
        return [i for i in self._root if i < 0]


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

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

cnt = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i != j:
           uf.unite(nodes[j][0]-1, nodes[j][1]-1)
    cnt += (len(uf.roots()) != 1)
print(cnt)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc075/tasks/abc075_c
class UnionFind():
    def __init__(self, N):
        self._root = [-1 for _ in range(N)]

    def find(self, x):
        if self._root[x] < 0: return x
        self._root[x] == self.find(self._root[x])
        return self._root[x]

    def unite(self, x, y):
        gx = self.find(x)
        gy = self.find(y)
        if gx == gy:
            return False
        if self._root[gx] > self._root[gy]:
            gx, gy = gy, gx
        self._root[gx] += self._root[gy]
        self._root[gy] = gx
        return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -(self._root[self.find(x)])

    def roots(self):
        return [i for i in self._root if i < 0]


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

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

cnt = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i != j:
           uf.unite(nodes[j][0]-1, nodes[j][1]-1)
    cnt += (len(uf.roots()) != 1)
print(cnt)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc075/tasks/abc075_c
class UnionFind():
    def __init__(self, N):
        self._root = [-1 for _ in range(N)]

    def find(self, x):
        if self._root[x] < 0: return x
        self._root[x] == self.find(self._root[x])
        return self._root[x]

    def unite(self, x, y):
        gx = self.find(x)
        gy = self.find(y)
        if gx == gy:
            return False
        if self._root[gx] > self._root[gy]:
            gx, gy = gy, gx
        self._root[gx] += self._root[gy]
        self._root[gy] = gx
        print(self._root)
        return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -(self._root[self.find(x)])

    def roots(self):
        return [i for i in self._root if i < 0]


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

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

cnt = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i != j: 
           uf.unite(nodes[j][0]-1, nodes[j][1]-1)
    cnt += (len(uf.roots()) != 1)
print(cnt)

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import floyd_warshall

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]

cnt=0
for i in range(m):
  ll=deepcopy(l)
  del ll[i]

  d=[[float('inf')]*n for i in range(n)]
  for i in range(n):
    d[i][i]=0

  for a,b in ll:
    a-=1
    b-=1
    d[a][b]=1
    d[b][a]=1

  s=floyd_warshall(d)
  for i in s:
    if float('inf') in i:
      cnt+=1
      break

print(cnt)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self,N):
        self.par =[-1 for i in range(N)]
    def find(self,x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.par[x] > self.par[y]:
            x,y = y,x
        self.par[x] +=self.par[y]
        self.par[y] = x

    def size(self,x):
        return -self.par[self.find(x)]
    def same(self,x,y):
        return self.find(x)==self.find(y)

N,M=map(int,input().split(' '))
q = [list(map(int,input().split(' '))) for i in range(M)]
ans = 0
for i in range(M):
    tmp = q[:i]+q[i+1:]
    uf = UnionFind(N)
    for j,k in tmp:
        uf.unite(j-1,k-1)
    for l in range(M):
        if uf.size(l) != N:
            ans += 1
            break
print(ans)

Submission status: Runtime Error

Solution code:
## import numpy as np
from collections import defaultdict

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

AB = []
G = defaultdict(list)
for _ in range(m):
    a, b = map(int, input().split())
    AB.append([a, b])
    G[a].append(b)
    G[b].append(a)

ans = 0
for a, b in AB:
    memo = [0]*(n+1)
    memo[a] = 1
    que = [c for c in G[a] if c != b]
    while que:
        c = que.pop()
        memo[c] = 1
        for nc in G[c]:
            if memo[nc] == 0:
                que.append(nc)
    if np.count_nonzero(memo) != n:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
n,m=map(int,input().split())
A=[[0]*2 for i in range(n)]
for i in range(m):
  A[i]=list(map(int,input().split()))
ans=0
for i in range(m):
  B=[[] for i in range(n)]
  for j in range(m):
    if j==i:
      continue
    B[A[j][0]-1].append(A[j][1]-1)
    B[A[j][1]-1].append(A[j][0]-1)
  C=[0]*n
  C[0]=1
  D=deque([0])
  while len(D)>0:
    x=D[0]
    D.popleft()
    for j in range(len(B[x])):
      if C[B[x][j]]==0:
        D.append(B[x][j])
        C[B[x][j]]=1
  if C!=[1]*n:
    ans=ans+1
print(ans)

Submission status: Runtime Error

Solution code:

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define veci vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define vec2(a,b) vector<vec>(a,vec(b))
#define vec2ll(a,b) vector<vec>(a,vecll(b))
#define vec3(a,b,c) vector<vector<vec>>(a,vec2(b,c))
#define vec3ll(a,b,c) vector<vector<vecll>>(a,vec2ll(b,c))
#define fi first
#define se second
#define all(c) begin(c),end(c)
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))


using namespace std;
int in() {int x;cin>>x;return x;}
ll lin() {ll x;cin>>x;return x;}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T> inline void print(pair<T,T> p){cout<<"("<<p.first<<","<<p.second<<") ";}
//template<class T> inline void print(vector<pair<T,T>> v){for(auto e:v)print(e); cout<<endl;}
//template<class T> inline void print(T v){for(auto e:v)cout<<e<<" ";cout<<endl;}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x:vec) is >> x;
    return is;
}
const ll INF=1e10+100;

class DisjointSet{
    public:
    vector<ll> rank,p;
    DisjointSet(){}
    DisjointSet(ll size){
        rank.resize(size,0);
        p.resize(size,0);
        rep(i,size){
            makeSet(i);
        }
    }
    void makeSet(ll x){
        p[x]=x;
        rank[x]=0;
    }
    bool same(ll x,ll y){
        return findSet(x)==findSet(y);
    }
    void unite(ll x,ll y){
        link(findSet(x),findSet(y));
    }
    void link(ll x, ll y){
        if(rank[x]>rank[y]){
            p[y]=x;
        }
        else{
            p[x]=y;
            if(rank[x]==rank[y]){
                rank[y]++;
            }
        }
    }
    ll findSet(ll x){
        if(p[x]!=x){
            p[x]=findSet(p[x]);
        }
        return p[x];
    }
};

int main()
{
    ll n,m;
    cin >> n >> m;
    vector<ll> a(m);
    vector<ll> b(m);
    rep(i,m){
        ll s,t;
        cin >> s >> t;
        s--;
        t--;
        a[i]=s;
        b[i]=t;
    }
    ll ans=0;
    rep(i,m){ //i番目の辺を使わない
        DisjointSet dis=DisjointSet(n);
        bool flag=true; //trueならばグラフは連結
        rep(j,m){
            if(j==i) continue;
            dis.unite(a[j],b[j]);
        }
        rep(p,n){
            for(ll q=p+1;q<n;q++){
                if(!dis.same(p,q)){
                    flag=false;
                    break;
                }
            }
        }
        if(!flag) ans++;
    }
    cout << ans << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return r'\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m=map(int,input().split())
a=[None]*m
b=a[:]
ans=0
for i in range(m):
  a[i],b[i]=map(lambda x:x-1,map(int,input().split()))
for i in range(m):
  u=UnionFind(n)
  for j in range(i):
    if j!=i:
      u.union(a,b)
  if u.size(0)!=n:
    ans+=1
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

N, M = map(int, input().split())
G = {k:[] for k in range(N)}
for _ in range(M):
  a, b = map(int, input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)


def rel_side(v, G):  # 任意の頂点から、他のすべての頂点を訪問したかどうかを確認する関数
  if all(vis):
    return 1
  r = 0
  for side in G[v]:
    if not vis[side]:
      vis[side] = True)
      r += rel_side(side, G)
  return r


bridge = 0
for i in range(N):
  for j, k in enumerate(G[i]):
    vis = [False] * N
    vis[i] = True
    pop1 = G[i].pop(j)
    idx = G[pop1].index(i)
    pop2 = G[pop1].pop(idx)
    if not rel_side(i, G):
      bridge += 1
    # print(vis, rel_side(i, G))
    G[i].insert(j, pop1)
    G[pop1].insert(idx, pop2)
    

print(bridge // 2)

Submission status: Runtime Error

Solution code:
import sys
import copy

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

V = []
E = []

for i in range(N):
    V.append(set())

for i in range(M):
    *l,  = map(int, input().split())
    V[l[0]-1].add(l[1]-1)
    V[l[1]-1].add(l[0]-1)
    E.append([l[0], l[1]])

count = 0


E_copy = copy.deepcopy(E)
V_copy = copy.deepcopy(V)

for i in range(M):
    e = [E[i][0], E[i][1]]

	V[e[0]].remove(e[1])
    V[e[1]].remove(e[0])
    
    #辺が存在しないノードがあるかをチェックする。
    for v in V:
        if len(v)==0:
            count = count + 1
            break
    
    E = copy.deepcopy(E_copy)
    V = copy.deepcopy(V_copy)
   
print(count)

Submission status: Runtime Error

Solution code:
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.ranks = [0] * n
        self.count = n

    def union(self, x, y):
        self.link(x, y)

    def link(self, x, y):
        x_root = self.parents[x]
        y_root = self.parents[y]
        if x_root == y_root:
            return

        if self.ranks[x] > self.ranks[y]:
            self.parents[y] = xroot
        else:
            self.parents[x] = y_root
            if self.ranks[x] == self.ranks[y]:
                self.ranks[y] += 1
        self.count -= 1

    def find(self, x):
        if self.parents[x] != x:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

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

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


count = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if j == i:
            continue
        else:
            x, y = bridges[j]
            uf.union(x, y)
    if uf.count > 1:
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.ranks = [0] * n
        self.count = n

    def union(self, x, y):
        self.link(x,y)

    def link(self, x, y):
        if self.parents[x] == self.parents[y]:
            return
        if self.ranks[x] < self.ranks[y]:
            self.parents[x] = y
        else:
            if self.ranks[y] == self.ranks[x]:
                self.ranks[y] += 1
            self.parents[y] = x
        # print('linked')
        self.count -= 1

    def find(self, x):
        if self.parents[x] != x:
            return self.find(self.parents[x])
        else:
            return self.parents[x]

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

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


# bridges = bridges[::-1]
# result = []
# print('-----')
count = 0
for i in range(M):
    # print(i, 'th ------')
    uf = UnionFind(N)
    for j in range(M):
        x, y = bridges[j]
        if j == i:
            # print('  skip',x-1,y-1, 'count',uf.count, uf.parents)
            continue
        else:
            uf.union(x, y)
            # print('  union',x-1,y-1, 'count',uf.count, uf.parents)
    # print(i, uf.count)
    if uf.count > 1:
        count += 1


# for x, y in bridges:
#     uf.union(x-1, y-1)
#     result.append(uf.get_group_num())

# print(result[::-1])

print(count)

Submission status: Runtime Error

Solution code:
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.ranks = [0] * n
        self.count = n

    def union(self, x, y):
        self.link(x,y)

    def link(self, x, y):
        if self.parents[x] == self.parents[y]:
            return
        if self.ranks[x] < self.ranks[y]:
            self.parents[x] = y
        else:
            if self.ranks[y] == self.ranks[x]:
                self.ranks[y] += 1
            self.parents[y] = x

        self.count -= 1

    def find(self, x):
        if self.parents[x] != x:
            return self.find(self.parents[x])
        else:
            return self.parents[x]

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

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


# bridges = bridges[::-1]
# result = []
print('-----')
count = 0
for i in range(M):
    # print(i, 'th ------')
    uf = UnionFind(N)
    for j in range(M):
        x, y = bridges[j]
        if j == i:

            continue
        else:
            uf.union(x, y)


    if uf.count > 1:
        count += 1


# for x, y in bridges:
#     uf.union(x-1, y-1)
#     result.append(uf.get_group_num())

# print(result[::-1])

print(count)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)
n, m = map(int, input().split())
g = [[False] * n for _ in range(n)]
visited = [False] * n
a = []
b = []
ans = 0


def dfs(v):
    visited[v] = True
    for to in range(n):
        if not g[v][to]:
            continue
        if visited[to]:
            continue
        dfs(v)


for _ in range(m):
    ai, bi = map(int, input().split())
    ai -= 1
    bi -= 1
    a.append(ai)
    b.append(bi)
    g[ai][bi] = True
    g[bi][ai] = True

for i in range(m):
    g[a[i]][b[i]] = False
    g[b[i]][a[i]] = False
    for j in range(n):
        visited[j] = False
    dfs(0)
    for j in range(n):
        if not visited[j]:
            ans += 1
            break
    g[a[i]][b[i]] = True
    g[b[i]][a[i]] = True

print(ans)

Submission status: Runtime Error

Solution code:
"""
頂点数nと隣接リストesが与えられて, そのグラフが木か連結かどちらでもないか判定する
"""
n,m = map(int,input().split())# 頂点数
es = []
ans=-1
for i in range(n):
    es.append([])
for j in range(m):
    a,b=map(int,input().split())
    es[a-1].append(b-1)
    es[b-1].append(a-1)
tmp=0
for i in range(m):
    for j in range(m):
        if i==j:
            if tmp!=0:
                es.remove([])
                es.insert(i-1,tmp)
                tmp=es.pop(j)
                es.insert(i,[])
            else:
                tmp=es.pop(j)
                es.insert(i,[])
    #print(es)
    sw = [True for i in range(n)]
    # 頂点0とのパスが存在すればFalse, 存在しないならTrue と定義する
    def dfs(v):
        sw[v] = False
        if es[v]!=[]:
            for i in es[v]:
                if sw[i]:
                    dfs(i)
    
    # 連結か判定 ( 頂点0とのパスが存在しない頂点があれば連結でない )
    for i in range(n):
        dfs(i)
        for j in range(n):
            if sw[j]:
                ans+=1
                break
print(ans)
# 木か判定 ( 連結で (頂点数-1) = (辺の数)　ならば木 )
# (隣接リストの要素数の和) = (辺の数)*2 であることに注意

Submission status: Runtime Error

Solution code:
import sys

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def dfs(G, v):
	seen[v] += 1
	#print('v :', v)
	
	for nv in G[v]:
		if seen[nv]: continue
		#print('v nv :', v, nv, 'Recursion')
		dfs(G, nv)

N, M = MAP()
A = [MAP() for _ in range(M)]

#print(A)

ans = 0
for i in range(M):
	G = [[] for _ in range(N)]
	for j, m in enumerate(A):
		# i!=jのとき辺を追加しない
		if i != j:
			a, b = m
			G[a-1].append(b-1)
			G[b-1].append(a-1)
		
	seen = [0] * N
	dfs(G, 1)
	#print(i, j, seen)
	
	if sum(seen) != N: ans += 1

print(ans)import sys

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def dfs(G, v):
	seen[v] += 1
	#print('v :', v)
	
	for nv in G[v]:
		if seen[nv]: continue
		#print('v nv :', v, nv, 'Recursion')
		dfs(G, nv)

N, M = MAP()
A = [MAP() for _ in range(M)]

#print(A)

ans = 0
for i in range(M):
	G = [[] for _ in range(N)]
	for j, m in enumerate(A):
		# i!=jのとき辺を追加しない
		if i != j:
			a, b = m
			G[a-1].append(b-1)
			G[b-1].append(a-1)
		
	seen = [0] * N
	dfs(G, 1)
	#print(i, j, seen)
	
	if sum(seen) != N: ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
N,Mmap(int,input())
e=[[] for i in range(N)]
tester=[None]*M
for i in range(M):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  e[a].append(b)
  e[b].append(a)
  tester[i]=set(a,b)
  
ans=0
seen=[0 for i in range(N)]
for test in tester:
  stack=[]
  stack.append([0,-1])
  while stack:
    node=stack.pop()
    v=node[0]
    parent=node[1]
    if seen[v]==1:
      continue
    seen[v]=1
    childs=e[v]
    for child in childs:
      if child==parent:
        continue
      if len(test&set([v,child]))==2:
        continue
      stack.append([child,v])
      
  if sum(seen)!=N:
    ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
ll =[[0]*n for _ in [0]*n]
edges = [list(map(int,input().split())) for _ in [0]*m]
for edge in edges:
  ll[edge[0]][edge[1]] = 1
  ll[edge[1]][edge[0]] = 1
originalll = ll.copy()
seen = [0]*n
ans = 0

for edge in edges:
  ll = originalll.copy()
  ll[edge[0]][edge[1]] = 0
  ll[edge[1]][edge[0]] = 0
  seen = [0]*n
  tmp = 0
  seen,tmp,ll = dfs(seen,tmp,ll)
print(ans)

def dfs(seen,tmp,ll):
  for i in range(n):
    if ll[tmp][i] = 1 and seen[i] = 0
    seen[i] = 1
    tmp = i
    seen,tmp,ll = dfs(seen,tmp,ll)
  if sum(seen) == n:
    ans+=1
  return seen,tmp,ll

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
ll =[[0]*n for _ in [0]*n]
edges = [list(map(int,input().split())) for _ in [0]*m]
for edge in edges:
  ll[edge[0]][edge[1]] = 1
  ll[edge[1]][edge[0]] = 1
originalll = ll.copy()
seen = [0]*n
ans = 0

def dfs(seen,tmp,ll):
  for i in range(n):
    if ll[tmp][i] = 1 and seen[i] = 0
    seen[i] = 1
    tmp = i
    seen,tmp,ll = dfs

Submission status: Runtime Error

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

graph=[[False]*N for i in range(N)]
visited=[False]*N
a=[0]*N
b=[0]*N

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


def dfs(v):
    visited[v]=True
    for v2 in range(N):
        if graph[v][v2]==False:continue
        if 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(0)
    bridge=False
    for j in range(N):
        if visited[j]==False:
            bridge=True
    if bridge==True:
        ans+=1
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True

print(ans)

Submission status: Runtime Error

Solution code:
N, M = [int(i) for i in input().split()]
for j in range(M):
    a, b = [int(k) for k in input().split()]
    graph[a-1][b-1] = graph[b-1][a-1] = 1

nmax = 50
graph = [[0]*nmax for i in range(nmax)]

print(*graph)

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)