ONBRIDGE - Online Bridge Searching
English | Vietnamese |
Given a graph of N vertices, numbered from 0 to N - 1. Initially, there is no edge in the graph. Sequentially adding M undirected edges (u, v) to the graph (0 <= u, v <= N - 1). After adding an edge, you must print out the current number of bridges in the graph. The data guarantees that there is no request to add an existed edge, or an edge from a vertex to itself.
Input
The first line contains an integer T (T <= 10) denotes the number of test cases. Each test case begins with 2 integers N (1 <= N <= 50000) and M (1 <= M <= 100000), followed by M lines, each line contains a pair of integers (u, v) represents a request to add an edge (u, v) to the graph.
Output
After each request, print out the current number of bridges in the graph on a separate line.
Example
For the input data:
1 5 10 3 0 0 2 1 0 1 3 1 4 2 4 4 0 2 1 2 3 3 4
the correct result is:
1 2 3 1 2 0 0 0 0 0
Added by: | Race with time |
Date: | 2012-03-06 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |