Bridges P37339


Statement
 

pdf   zip

html

A bridge of an undirected graph is defined as any edge whose removal increases the number of connected components. Please compute all the bridges of a given graph.

Input

Input consists of several cases, each with the number of vertices n, followed by the number of edges m, followed by m pairs x y indicating an edge between x and y, with xy. Assume 2 ≤ n ≤ 104, 1 ≤ m ≤ 5n, that vertices are numbered starting from zero, and that there is at most one edge connecting any pair of vertices.

Output

For every graph, print the number of bridges, followed by a line with those bridges. The two vertices of each bridge must be sorted increasingly, and the bridges themselves must also be sorted increasingly. Print a line with 10 dashes at the end of every case.

Public test cases
  • Input

    2 1
    0 1
    
    3 3
    2 1  0 1  2 0
    
    4 3
    2 1  0 1  3 0
    
    7 8
    6 5  4 3  6 1  2 3  3 0  2 0  0 6  1 5
    
    6 3
    1 5  3 4  4 0
    

    Output

    1
    0 1
    ----------
    0
    
    ----------
    3
    0 1  0 3  1 2
    ----------
    2
    0 6  3 4
    ----------
    3
    0 4  1 5  3 4
    ----------
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++
    Event
    Catorzè Concurs de Programació de la UPC - Final
    Date
    2016-09-21