Problem:


Bridges

Find bridges of an undirected graph G(V, E).

A bridge (also known as a cut-edge) is an edge whose deletion increase the number of connected components.

Input

|V| |E|
s0 t0
s1 t1
:
s|E|-1 t|E|-1

, where |V| is the number of nodes and |E| is the number of edges in the graph. The graph nodes are named with the numbers 0, 1,..., |V|-1 respectively.

si and ti represent source and target nodes of i-th edge (undirected).

Output

A list of bridges of the graph ordered by name. For each bridge, names of its end-ponints, source and target (source < target), should be printed separated by a space. The sources should be printed ascending order, then the target should also be printed ascending order for the same source.

Constraints

1 ≤ |V| ≤ 100,000

0 ≤ |E| ≤ 100,000

The graph is connected

There are no parallel edges

There are no self-loops

Sample Input 1

4 4
0 1
0 2
1 2
2 3

Sample Output 1

2 3

Sample Input 2

5 4
0 1
1 2
2 3
3 4

Sample Output 2

0 1
1 2
2 3
3 4



Sample input:
4 4
0 1
0 2
1 2
2 3


Sample output:
2 3

Submission status: Wrong Answer

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

import sys

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

N,M=MAP()
nodes=[[] for i in range(N)]
for i in range(M):
    u,v=MAP()
    nodes[u].append(v)
    nodes[v].append(u)

visited=[False]*N
timer=1
prenum=[0]*(N+1)
lowest=[0]*(N+1)
ans=[]
def rec(cur, prev):
    global timer
    # curを訪問した直後の処理
    prenum[cur]=lowest[cur]=timer
    timer+=1

    visited[cur]=True
    for nxt in nodes[cur]:
        # 未訪問なら再帰探索する
        if not visited[nxt]:
            rec(nxt, cur)
            # nxtの探索が終了した直後の処理
            lowest[cur]=min(lowest[cur], lowest[nxt])
            # より近い経路を含まないなら橋とする
            if lowest[nxt]==prenum[nxt]:
                ans.append((cur, nxt))
        # 訪問済の場合、親への経路は無視して、他は近い経路となるか確認を取る
        elif nxt!=prev:
            lowest[cur]=min(lowest[cur], lowest[nxt])

rec(0, -1)

ans.sort()
for edge in ans:
    print(*edge)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(1000000)


def dfs(current, prev):
    global time
    # node currentを訪問した直後の処理
    ord[current] = time
    low[current] = time
    time += 1
    color[current] = BLACK

    for next in G[current]:
        if color[next] == WHITE:
            # node currentからnode nextへ訪問する直前の処理
            parent[next] = current
            dfs(next, current)

            # node nextの探索が終了した直後の処理
            low[current] = min(low[current], low[next])
        elif next != prev:
            # edge current --> next がback-edgeの場合の処理
            low[current] = min(low[current], ord[next])


def bridge():
    global time
    time = 1
    dfs(0, -1)  # 0をrootとしてlowの計算
    for u, v in edges:
        if ord[u] < low[v] or ord[v] < low[u]:
            br.add((u, v))


G = {}
edges = set([])
br = set([])
v, n = map(int, input().split())
for i in range(0, v):
    G[i] = []
for i in range(n):
    s, t = map(int, input().split())
    G[s].append(t)
    G[t].append(s)
    edges.add((s, t))
WHITE = 0
BLACK = 2

color = [WHITE] * (v)
parent = [0] * (v)
ord = [0] * (v)
low = [0] * (v)
parent = [0] * (v)
bridge()
if br:
    for ans in sorted(br):
        print(*ans, sep=' ')

Submission status: Wrong Answer

Solution code:
import sys

from collections import deque
sys.setrecursionlimit(1000000)


def dfs(current, prev):
    global time
    # node currentを訪問した直後の処理
    ord[current] = time
    low[current] = time
    time += 1
    color[current] = BLACK

    for next in G[current]:
        if color[next] == WHITE:
            # node currentからnode nextへ訪問する直前の処理
            parent[next] = current
            dfs(next, current)

            # node nextの探索が終了した直後の処理
            low[current] = min(low[current], low[next])
        elif next != prev:
            # edge current --> next がback-edgeの場合の処理
            low[current] = min(low[current], ord[next])


def bridge():
    global time
    time = 1
    dfs(0, -1)  # 0をrootとしてlowの計算
    for u, v in edges:
        if ord[u] < low[v] or ord[v] < low[u]:
            br.add((u, v))


G = {}
edges = set([])
br = set([])
v, n = map(int, input().split())
for i in range(0, v):
    G[i] = []
for i in range(n):
    s, t = map(int, input().split())
    G[s].append(t)
    G[t].append(s)
    edges.add((s, t))
WHITE = 0
BLACK = 2

color = [WHITE] * (v)
parent = [0] * (v)
ord = [0] * (v)
low = [0] * (v)
parent = [0] * (v)
bridge()
if br:
    br = list(map(sorted, br))
    br.sort(key=lambda x: x[0])
    for ans in br:
        print(*ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
readline = stdin.readline

from sys import stdin
readline = stdin.readline


def main():
    v, e = map(int, readline().split())
    from collections import defaultdict
    g = defaultdict(list)

    for _ in range(e):
        s, t = map(int, readline().split())
        g[s].append(t)
        g[t].append(s)

    visited = set()
    lowest = [None] * v
    parent = [None] * v
    prenum = [None] * v
    child = defaultdict(list)
    root = 0

    # dfs??§tree?????????
    stack = [(root, None)]
    while stack:
        u, prev = stack.pop()
        if u not in visited:
            parent[u] = prev
            if prev is not None:
                child[prev].append(u)
            visited |= {u}
            prenum[u] = lowest[u] = len(visited)

        stack.extend([(v, u) for v in g[u] if v not in visited])

    # lowest????¨????
    from collections import Counter
    leaf = [i for i in range(v) if not child[i]]
    unfinished = Counter()
    for li in leaf:
        while li is not None:
            candidate = [prenum[li]] + [prenum[i] for i in g[li] if i != parent[li]] + [lowest[i] for i in child[li]]
            lowest[li] = min(candidate)
            li = parent[li]
            if li is not None and 1 < len(child[li]):
                unfinished[li] += 1
                if unfinished[li] < len(child[li]):
                    break

    # ????????????
    bridge = []
    for i in range(v):
        if child[i]:
            for j in child[i]:
                if prenum[i] < lowest[j]:
                    if i > j:
                        i, j = j, i
                    bridge.append((i, j))
    bridge.sort()
    for bi in bridge:
        print(*bi)

main()

Submission status: Wrong Answer

Solution code:
# Acceptance of input
import sys

f_i = sys.stdin

V, E = map(int, f_i.readline().split())

adj = [[] for i in range(V)]

for l_i in f_i:
    s, t = map(int, l_i.split())
    adj[s].append(t)
    adj[t].append(s)


# dfs traverse
prenum = [1] + [None] * (V - 1)
parent = [0] * V
lowest = [1] + [V] * (V - 1)

import collections

path = collections.deque()
path.append(0)

cnt = 1

while path:
    u = path[-1]
    adj_v = adj[u]
    for v in adj_v:
        if not prenum[v]:
            parent[v] = u
            path.append(v)
            cnt += 1
            lowest[v] = cnt
            prenum[v] = cnt
            adj[u].remove(v)
            adj[v].remove(u)
            break
    if u == path[-1]:
        for v in adj_v:
            lowest[u] = min(lowest[u], prenum[v])
            adj[u].remove(v)
            adj[v].remove(u)
        p = parent[u]
        lowest[p] = min(lowest[u], lowest[p])
        path.pop()


# output
bridge = []

for u in range(1, V):
    p = parent[u]
    if lowest[p] != lowest[u]:
        b = [p, u]
        b.sort()
        bridge.append(b)

bridge.sort()

for b in bridge:
    print(*b)

Submission status: Wrong Answer

Solution code:
# Acceptance of input
import sys

f_i = sys.stdin

V, E = map(int, f_i.readline().split())

adj = [[] for i in range(V)]

for l_i in f_i:
    s, t = map(int, l_i.split())
    adj[s].append(t)
    adj[t].append(s)


# dfs traverse
prenum = [1] + [None] * (V - 1)
parent = [0] * V
lowest = [1] + [V] * (V - 1)

import collections

path = collections.deque()
path.append(0)

cnt = 1

while path:
    u = path[-1]
    adj_v = adj[u]
    for v in adj_v:
        if not prenum[v]:
            parent[v] = u
            path.append(v)
            cnt += 1
            prenum[v] = cnt
            lowest[v] = cnt
            adj[u].remove(v)
            adj[v].remove(u)
            break
    if u == path[-1]:
        for v in adj_v:
            l = min(lowest[u], prenum[v])
            lowest[u] = l
            lowest[v] = l
        p = parent[u]
        lowest[p] = min(lowest[u], lowest[p])
        path.pop()


# output

bridge = []

for u in range(1, V):
    p = parent[u]
    if lowest[p] != lowest[u]:
        b = [p, u]
        b.sort()
        bridge.append(b)

bridge.sort()

for b in bridge:
    print(*b)

Submission status: Wrong Answer

Solution code:
# Acceptance of input
import sys

f_i = sys.stdin

V, E = map(int, f_i.readline().split())

adj = [[] for i in range(V)]

for l_i in f_i:
    s, t = map(int, l_i.split())
    adj[s].append(t)
    adj[t].append(s)


# dfs traverse
prenum = [1] + [None] * (V - 1)
parent = [0] * V
lowest = [1] + [V] * (V - 1)

import collections

path = collections.deque()
path.append(0)

cnt = 1

while path:
    u = path[-1]
    adj_v = adj[u]
    for v in adj_v:
        if not prenum[v]:
            parent[v] = u
            path.append(v)
            cnt += 1
            prenum[v] = cnt
            lowest[v] = cnt
            adj[u].remove(v)
            adj[v].remove(u)
            break
    if u == path[-1]:
        for v in adj_v:
            lowest[u] = min(lowest[u], lowest[v])
        p = parent[u]
        lowest[p] = min(lowest[u], lowest[p])
        path.pop()


# output
bridge = []

for u in range(1, V):
    p = parent[u]
    if lowest[p] != lowest[u]:
        b = [p, u]
        b.sort()
        bridge.append(b)

bridge.sort()

for b in bridge:
    print(*b)

Submission status: Wrong Answer

Solution code:
# Acceptance of input
import sys

f_i = sys.stdin

V, E = map(int, f_i.readline().split())

adj = [[] for i in range(V)]

for l_i in f_i:
    s, t = map(int, l_i.split())
    adj[s].append(t)
    adj[t].append(s)


# dfs traverse
prenum = [1] + [None] * (V - 1)
parent = [0] * V
lowest = [1] + [V] * (V - 1)

import collections

path = collections.deque()
path.append(0)

cnt = 1

while path:
    u = path[-1]
    adj_v = adj[u]
    for v in adj_v:
        if not prenum[v]:
            parent[v] = u
            path.append(v)
            cnt += 1
            prenum[v] = cnt
            lowest[v] = cnt
            adj[u].remove(v)
            adj[v].remove(u)
            break
    if u == path[-1]:
        for v in adj_v:
            l = min(lowest[u], lowest[v])
            lowest[u] = l
            lowest[v] = l
        p = parent[u]
        lowest[p] = min(lowest[u], lowest[p])
        path.pop()


# output
bridge = []

for u in range(1, V):
    p = parent[u]
    if lowest[p] != lowest[u]:
        b = [p, u]
        b.sort()
        bridge.append(b)

bridge.sort()

for b in bridge:
    print(*b)

Submission status: Wrong Answer

Solution code:
# Acceptance of input
import sys

f_i = sys.stdin

V, E = map(int, f_i.readline().split())

adj = [[] for i in range(V)]

for l_i in f_i:
    s, t = map(int, l_i.split())
    adj[s].append(t)
    adj[t].append(s)


# dfs traverse
prenum = [1] + [None] * (V - 1)
parent = [0] * V
lowest = [1] + [V] * (V - 1)

import collections

path = collections.deque()
path.append(0)

cnt = 1

while path:
    u = path[-1]
    adj_v = adj[u]
    for v in adj_v:
        if not prenum[v]:
            parent[v] = u
            path.append(v)
            cnt += 1
            prenum[v] = cnt
            adj[u].remove(v)
            adj[v].remove(u)
            break
    if u == path[-1]:
        lowest[u] = min(lowest[u], prenum[u])
        for v in adj_v:
            l = min(lowest[u], lowest[v])
            lowest[u] = l
            lowest[v] = l
        p = parent[u]
        lowest[p] = min(lowest[u], lowest[p])
        path.pop()


# output
bridge = []

for u in range(1, V):
    p = parent[u]
    if lowest[p] != lowest[u]:
        b = [p, u]
        b.sort()
        bridge.append(b)

bridge.sort()

for b in bridge:
    print(*b)

Submission status: Wrong Answer

Solution code:
import sys

f_i = sys.stdin

V, E = map(int, f_i.readline().split())

adj = [[] for i in range(V)]

for l_i in f_i:
    s, t = map(int, l_i.split())
    adj[s].append(t)
    adj[t].append(s)


# dfs traverse
prenum = [1] + [None] * (V - 1)
parent = [0] * V
lowest = [1] + [V] * (V - 1)

import collections

path = collections.deque()
path.append(0)

cnt = 1

while path:
    u = path[-1]
    adj_v = adj[u]
    for v in adj_v:
        if not prenum[v]:
            parent[v] = u
            path.append(v)
            cnt += 1
            prenum[v] = cnt
            lowest[v] = cnt
            adj[u].remove(v)
            adj[v].remove(u)
            break
    if u == path[-1]:
        lowest[u] = min(lowest[u], prenum[u])
        for v in adj_v:
            l = min(lowest[u], lowest[v])
            lowest[u] = l
            lowest[v] = l
        p = parent[u]
        lowest[p] = min(lowest[u], lowest[p])
        path.pop()


# output
bridge = []

for u in range(1, V):
    p = parent[u]
    if lowest[p] != lowest[u]:
        b = [p, u]
        b.sort()
        bridge.append(b)

bridge.sort()

for b in bridge:
    print(*b)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
5 4
0 1
1 2
2 3
3 4

output:
0 1
1 2
2 3
3 4
"""

import sys
from operator import itemgetter

sys.setrecursionlimit(int(3e6))


def generate_adj_table(_v_info):
    for v_detail in _v_info:
        v_from, v_to = map(int, v_detail)
        init_adj_table[v_from].append(v_to)
        # undirected graph
        init_adj_table[v_to].append(v_from)
    return init_adj_table


def graph_dfs(u, visited, parent, low, disc):
    global Time
    # Count of children in current node
    children = 0

    # Mark the current node as visited and print it
    visited[u] = True

    # Initialize discovery time and low value
    disc[u] = Time
    low[u] = Time
    Time += 1

    # Recur for all the vertices adjacent to this vertex
    for v in adj_table[u]:
        # If v is not visited yet, then make it a child of u
        # in DFS tree and recur for it
        if not visited[v]:
            parent[v] = u
            children += 1
            graph_dfs(v, visited, parent, low, disc)

            # Check if the subtree rooted with v has a connection to
            # one of the ancestors of u
            low[u] = min(low[u], low[v])

            ''' If the lowest vertex reachable from subtree
            under v is below u in DFS tree, then u-v is
            a bridge'''
            if low[v] > disc[u]:
                ans.append(sorted([u, v]))
        elif v != parent[u]:  # Update low value of u for parent function calls.
            low[u] = min(low[u], disc[v])

    return None


def bridge():
    visited = [False] * vertices
    disc = [float("Inf")] * vertices
    low = [float("Inf")] * vertices
    parent = [-1] * vertices

    for v in range(vertices):
        if not visited[v]:
            graph_dfs(v, visited, parent, low, disc)

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])
    Time = 0
    ans = []

    init_adj_table = tuple([] for _ in range(vertices))
    adj_table = generate_adj_table(v_info)
    res = bridge()
    res.sort(key=itemgetter(0))
    res.sort(key=itemgetter(1))
    for ele in res:
        print(*ele)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
5 4
0 1
1 2
2 3
3 4

output:
0 1
1 2
2 3
3 4
"""

import sys
from operator import itemgetter

sys.setrecursionlimit(int(3e6))


def generate_adj_table(_v_info):
    for v_detail in _v_info:
        v_from, v_to = map(int, v_detail)
        init_adj_table[v_from].append(v_to)
        # undirected graph
        init_adj_table[v_to].append(v_from)
    return init_adj_table


def graph_dfs(u, visited, parent, low, disc):
    global Time
    # Count of children in current node
    children = 0

    # Mark the current node as visited and print it
    visited[u] = True

    # Initialize discovery time and low value
    disc[u] = Time
    low[u] = Time
    Time += 1

    # Recur for all the vertices adjacent to this vertex
    for v in adj_table[u]:
        # If v is not visited yet, then make it a child of u
        # in DFS tree and recur for it
        if not visited[v]:
            parent[v] = u
            children += 1
            graph_dfs(v, visited, parent, low, disc)

            # Check if the subtree rooted with v has a connection to
            # one of the ancestors of u
            low[u] = min(low[u], low[v])

            ''' If the lowest vertex reachable from subtree
            under v is below u in DFS tree, then u-v is
            a bridge'''
            if low[v] > disc[u]:
                ans.append(sorted([u, v]))
        elif v != parent[u]:  # Update low value of u for parent function calls.
            low[u] = min(low[u], disc[v])

    return None


def bridge():
    visited = [False] * vertices
    disc = [float("Inf")] * vertices
    low = [float("Inf")] * vertices
    parent = [-1] * vertices

    for v in range(vertices):
        if not visited[v]:
            graph_dfs(v, visited, parent, low, disc)

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])
    Time = 0
    ans = []

    init_adj_table = tuple([] for _ in range(vertices))
    adj_table = generate_adj_table(v_info)
    res = bridge()
    res.sort(key=itemgetter(0))
    res = sorted(res, key=itemgetter(1))
    for ele in res:
        print(*ele)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

def dfs(v, tm):
    dts[v] = est[v] = tm + 1
    child = 0

    for i in adj[v]:
        if est[i] == float('inf'):
            child += 1
            parents[i] = v
            dfs(i, tm + 1)
            est[v] = min(est[v], est[i])

            if est[i] > dts[v]: bridges.append((v, i))

        elif parents[v] != i:
            est[v] = min(est[v], dts[i])

nv, ne = map(int, input().split(' '))
adj = [[] for _ in range(nv)]
est = [float('inf')] * nv
parents = [None] * nv
dts = [0] * nv
bridges = []

for _ in range(ne):
    s, t = map(int, input().split(' '))
    adj[s].append(t)
    adj[t].append(s)

dfs(0, 0)
bridges.sort(key=lambda tup: (tup[0], tup[1]))
[print(str(bridge[0]) + ' ' + str(bridge[1])) for bridge in bridges]

Submission status: Wrong Answer

Solution code:
def connection(G):
    how_many_point=len(G[0])
    tip=[0]

    G_flag=[0 for i in range(how_many_point)]
    G_flag[0]=1

    while len(tip)>0:
        tip_cash=[]
        for i in tip:
            for j in range(how_many_point):
                if G[i][j]==1 and G_flag[j]==0:
                    tip_cash.append(j)
                    G_flag[j]=1
        tip=list(set(tip_cash))

    if G_flag==[1 for i in range(how_many_point)]:
        return True
    else:
        return False




V,E=[int(i) for i in input().split(" ")]
G_original=[[0 for i in range(V)] for j in range(V)]
s=[]
t=[]
for i in range(E):
    si,ti=[int(j) for j in input().split(" ")]
    s.append(si)
    t.append(ti)
    G_original[si][ti]=1
    G_original[ti][si]=1

for i in range(E):
    G=G_original.copy()
    G[s[i]][t[i]]=0
    G[t[i]][s[i]]=0
    if not(connection(G)):
        print(s[i],t[i])
    G[s[i]][t[i]]=1
    G[t[i]][s[i]]=1

Submission status: Wrong Answer

Solution code:
import operator
def connection(G):
    how_many_point=len(G[0])
    tip=[0]

    G_flag=[0 for i in range(how_many_point)]
    G_flag[0]=1

    while len(tip)>0:
        tip_cash=[]
        for i in tip:
            for j in range(how_many_point):
                if G[i][j]==1 and G_flag[j]==0:
                    tip_cash.append(j)
                    G_flag[j]=1
        tip=list(set(tip_cash))

    if G_flag==[1 for i in range(how_many_point)]:
        return True
    else:
        return False




V,E=[int(i) for i in input().split(" ")]
G_original=[[0 for i in range(V)] for j in range(V)]
s=[]
t=[]
for i in range(E):
    si,ti=[int(j) for j in input().split(" ")]
    s.append(si)
    t.append(ti)
    G_original[si][ti]=1
    G_original[ti][si]=1


answer=[]
class Point:
    def __init__(self,s,t):
        self.s=s
        self.t=t


for i in range(E):
    G=G_original.copy()
    G[s[i]][t[i]]=0
    G[t[i]][s[i]]=0
    if not(connection(G)):
        answer.append(Point(s[i],t[i]))
    G[s[i]][t[i]]=1
    G[t[i]][s[i]]=1



answer.sort(key=operator.attrgetter("s"))
for i in answer:
    print("%d %d"%(i.s,i.t))

Submission status: Wrong Answer

Solution code:
import operator
def connection(G):
    how_many_point=len(G[0])
    tip=[0]

    G_flag=[0 for i in range(how_many_point)]
    G_flag[0]=1

    while len(tip)>0:
        tip_cash=[]
        for i in tip:
            for j in range(how_many_point):
                if G[i][j]==1 and G_flag[j]==0:
                    tip_cash.append(j)
                    G_flag[j]=1
        tip=list(set(tip_cash))

    if G_flag==[1 for i in range(how_many_point)]:
        return True
    else:
        return False




V,E=[int(i) for i in input().split(" ")]
G_original=[[0 for i in range(V)] for j in range(V)]
s=[]
t=[]
for i in range(E):
    si,ti=[int(j) for j in input().split(" ")]
    s.append(si)
    t.append(ti)
    G_original[si][ti]=1
    G_original[ti][si]=1


answer=[]
class Point:
    def __init__(self,s,t):
        self.s=s
        self.t=t


for i in range(E):
    G=G_original.copy()
    G[s[i]][t[i]]=0
    G[t[i]][s[i]]=0
    if not(connection(G)):
        if s[i]<=t[i]:
            answer.append(Point(s[i],t[i]))
        else:
            answer.append(Point(t[i],s[i]))
    G[s[i]][t[i]]=1
    G[t[i]][s[i]]=1



answer.sort(key=operator.attrgetter("s"))
for i in answer:
    print("%d %d"%(i.s,i.t))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

def seq():
    a = 1
    while True:
        yield a
        a += 1

def dfs(here, went, connect, discovery, low, answer, seq):
    went |= {here}
    discovery[here] = low[here] = next(seq)
    child = 0
    for con in connect[here]:
        if con not in went:
            parent[con] = here
            child += 1
            dfs(con, went, connect, discovery, low, answer, seq)
            low[here] = min(low[here], low[con])
            if discovery[here] < low[con]:
                answer[min(here,con)].append(max(here,con))
        elif parent[here] != con:
            low[here] = min(low[here], discovery[con])

vertices, edges = (int(n) for n in input().split(" "))
connect = defaultdict(list)
for _ in range(edges):
    v1, v2 = (int(n) for n in input().split(" "))
    connect[v1].append(v2)
    connect[v2].append(v1)
answer = defaultdict(list)
new_seq = seq()
went = set()
discovery = [0 for n in range(vertices)]
low = [float("inf") for n in range(vertices)]
parent = [None for n in range(vertices)]
dfs(0, went, connect, discovery, low, answer, new_seq)

for k in answer.keys():
    for n in answer[k]:
        print(k,n)

Submission status: Wrong Answer

Solution code:
import sys

aumento = 0
def dfs(u,parent,G,id,dfs_num,dfs_low,vis,puntos,acumulador):
    #if(u==parent):acumulador+=1
    vis[u]=1
    id+=1
    dfs_num[u] = id
    dfs_low[u] = id
    for v in G[u]:
        if v==parent:continue
        if vis[v]==-1:
            dfs(v,u,G,id,dfs_num,dfs_low,vis,puntos,acumulador)
            dfs_low[u]=min(dfs_low[u],dfs_low[v])
            if(dfs_low[v]>dfs_num[u]):
                puntos.append((u,v))
        else:
            dfs_low[u]=min(dfs_low[u],dfs_num[v])
    

def main():
    T = [int(x) for x in sys.stdin.readline().strip().split()]
    V = T[0]
    E = T[1]
    G = [[] for i in range(V)]
    for j in range(E):
        line =[int(x) for x in sys.stdin.readline().strip().split()]
        G[line[0]].append(line[1])
        G[line[1]].append(line[0])
    n = len(G)
    id=0
    dfs_num = [0 for i in range(n)]
    dfs_low = [0 for i in range(n)]
    vis = [-1 for i in range(n)]
    #puntos=[False for i in range(n)]
    puntos=[]
    for i in range(V):
        if vis[i]==-1:
            acumulador=0
            dfs(i,-1,G,id,dfs_num,dfs_low,vis,puntos,acumulador)
            #puntos[i]=acumulador>1
    for i in sorted(puntos):
        print(i[0],i[1])

main()

Submission status: Wrong Answer

Solution code:
import sys


def dfs(root,u,parent,G,id,dfs_num,dfs_low,vis,puntos,acumulador,puentes,raices):
    vis[u]=1
    id+=1
    dfs_num[u] = id
    dfs_low[u] = id
    for v in G[u]:
        if v==parent:continue
        if vis[v]==-1:
            dfs(root,v,u,G,id,dfs_num,dfs_low,vis,puntos,acumulador,puentes,raices)
            dfs_low[u]=min(dfs_low[u],dfs_low[v])
            if(dfs_low[v]>dfs_num[u]):
     
                puntos.append((u,v))
            if(dfs_low[v]>=dfs_num[u]):
                puentes[u]=True
            if(dfs_low[u]>=dfs_num[root] and u!=root):
                puentes[root]=True
        else:
            dfs_low[u]=min(dfs_low[u],dfs_num[v])
    

def main():
    T = [int(x) for x in sys.stdin.readline().strip().split()]
    V = T[0]
    E = T[1]
    G = [[] for i in range(V)]
    for j in range(E):
        line =[int(x) for x in sys.stdin.readline().strip().split()]
        G[line[0]].append(line[1])
        G[line[1]].append(line[0])
    n = len(G)
    id=0
    dfs_num = [0 for i in range(n)]
    dfs_low = [0 for i in range(n)]
    vis = [-1 for i in range(n)]
    puentes=[False for i in range(n)]
    puntos=[]
    raices = [0 for i in range(n)]
    for i in range(V):
        if vis[i]==-1:
            acumulador=0
            dfs(i,i,-1,G,id,dfs_num,dfs_low,vis,puntos,acumulador,puentes,raices)

    for i in range(len(puentes)):
        puentes[i] = puentes[i] or raices[i]>1
    #print(puentes.count(True))
    T = []
    #for k in range(len(puentes)):
       # if(puentes[k]):
            #T.append(str(k))
    #print(" ".join(T))
    #print(len(puntos))
    for i in sorted(puntos):
        print(i[0],i[1])

main()

Submission status: Wrong Answer

Solution code:
import sys


def dfs(root,u,parent,G,id,dfs_num,dfs_low,vis,puntos,acumulador,puentes,raices):
    vis[u]=1
    id+=1
    dfs_num[u] = id
    dfs_low[u] = id
    for v in G[u]:
        if v==parent:continue
        if vis[v]==-1:
            dfs(root,v,u,G,id,dfs_num,dfs_low,vis,puntos,acumulador,puentes,raices)
            dfs_low[u]=min(dfs_low[u],dfs_low[v])
            if(dfs_low[v]>dfs_num[u]):
     
                puntos.append((u,v))
            if(dfs_low[v]>=dfs_num[u]):
                puentes[u]=True
            if(dfs_low[u]>=dfs_num[root] and u!=root):
                puentes[root]=True
        else:
            dfs_low[u]=min(dfs_low[u],dfs_num[v])
    

def main():
    T = [int(x) for x in sys.stdin.readline().strip().split()]
    V = T[0]
    E = T[1]
    G = [[] for i in range(V)]
    for j in range(E):
        line =[int(x) for x in sys.stdin.readline().strip().split()]
        G[line[0]].append(line[1])
        #G[line[1]].append(line[0])
    n = len(G)
    id=0
    dfs_num = [0 for i in range(n)]
    dfs_low = [0 for i in range(n)]
    vis = [-1 for i in range(n)]
    puentes=[False for i in range(n)]
    puntos=[]
    raices = [0 for i in range(n)]
    for i in range(V):
        if vis[i]==-1:
            acumulador=0
            dfs(i,i,-1,G,id,dfs_num,dfs_low,vis,puntos,acumulador,puentes,raices)

    for i in range(len(puentes)):
        puentes[i] = puentes[i] or raices[i]>1
    #print(puentes.count(True))
    T = []
    #for k in range(len(puentes)):
       # if(puentes[k]):
            #T.append(str(k))
    #print(" ".join(T))
    #print(len(puntos))
    for i in sorted(puntos):
        print(i[0],i[1])

main()

Submission status: Time Limit Exceeded

Solution code:
import operator
def connection(G):
    how_many_point=len(G[0])
    tip=[0]

    G_flag=[0 for i in range(how_many_point)]
    G_flag[0]=1

    while len(tip)>0:
        tip_cash=[]
        for i in tip:
            for j in range(how_many_point):
                if G[i][j]==1 and G_flag[j]==0:
                    tip_cash.append(j)
                    G_flag[j]=1
        tip=list(set(tip_cash))

    if G_flag==[1 for i in range(how_many_point)]:
        return True
    else:
        return False




V,E=[int(i) for i in input().split(" ")]
G_original=[[0 for i in range(V)] for j in range(V)]
s=[]
t=[]
for i in range(E):
    si,ti=[int(j) for j in input().split(" ")]
    s.append(si)
    t.append(ti)
    G_original[si][ti]=1
    G_original[ti][si]=1


answer=[]
class Point:
    def __init__(self,s,t):
        self.s=s
        self.t=t


for i in range(E):
    G=G_original.copy()
    G[s[i]][t[i]]=0
    G[t[i]][s[i]]=0
    if not(connection(G)):
        if s[i]<=t[i]:
            answer.append(Point(s[i],t[i]))
        else:
            answer.append(Point(t[i],s[i]))
    G[s[i]][t[i]]=1
    G[t[i]][s[i]]=1



answer.sort(key=operator.attrgetter("t"))
answer.sort(key=operator.attrgetter("s"))
for i in answer:
    print("%d %d"%(i.s,i.t))

Submission status: Time Limit Exceeded

Solution code:
import operator
def connection(G,s,t):
    how_many_point=len(G[0])
    tip=[0]

    G_flag=[0 for i in range(how_many_point)]
    G_flag[0]=1
    flag=0
    while len(tip)>0:
        
        tip_cash=[]
        for i in tip:
            for j in range(how_many_point):
                if G[i][j]==1 and G_flag[j]==0:
                    tip_cash.append(j)
                    G_flag[j]=1
                    if j==s:
                        flag+=1
                    if j==t:
                        flag+=1
                    if flag==2:
                        return True
        tip=list(set(tip_cash))

    if G_flag==[1 for i in range(how_many_point)]:
        return True
    else:
        return False




V,E=[int(i) for i in input().split(" ")]
G_original=[[0 for i in range(V)] for j in range(V)]
s=[]
t=[]
for i in range(E):
    si,ti=[int(j) for j in input().split(" ")]
    s.append(si)
    t.append(ti)
    G_original[si][ti]=1
    G_original[ti][si]=1


answer=[]
class Point:
    def __init__(self,s,t):
        self.s=s
        self.t=t


for i in range(E):
    G=G_original.copy()
    G[s[i]][t[i]]=0
    G[t[i]][s[i]]=0
    if not(connection(G,s[i],t[i])):
        if s[i]<=t[i]:
            answer.append(Point(s[i],t[i]))
        else:
            answer.append(Point(t[i],s[i]))
    G[s[i]][t[i]]=1
    G[t[i]][s[i]]=1



answer.sort(key=operator.attrgetter("t"))
answer.sort(key=operator.attrgetter("s"))
for i in answer:
    print("%d %d"%(i.s,i.t))

Submission status: Time Limit Exceeded

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

visited = None
def dfs(v):
    visited[v] = True
    for u,e in enumerate(G[v]):
        if e == 0 or visited[u] == True: continue
        dfs(u)
 
ans = []
for i in range(N):
    for j in range(i+1, N):
        if G[i][j] is 0:continue
        G[i][j] = G[j][i] = 0
        visited = [False] * N
        dfs(0)
        G[i][j] = G[j][i] = 1
        if not all(visited):ans.append((i,j))
 
for a in ans:
    print(' '.join(map(str,a)))