- Time limit: 1.00 s
- Memory limit: 512 MB
Consider a connected undirected graph. A node is called an articulation point if its removal disconnects the graph. Similarly, an edge is called a bridge if its removal disconnects the graph.
Your task is to calculate the number of articulation points and bridges in the graph.
Input
The first line contains two integers n and m: the number of nodes and edges in the graph. The nodes are numbered 1,2,\ldots,n.
Then, there are m lines that describe the edges. Each line contains two values a and b: there is an edge between nodes a and b.
Output
Output two integers: the number of articulation points and bridges.
Constraints
- 1 \le n \le 10^5
- 1 \le m \le 2 \cdot 10^5
Example
Input:
7 8 1 2 1 3 2 3 3 4 4 5 4 6 5 6 5 7
Output:
3 2
Explanation: Nodes 3, 4, and 5 are articulation points, and edges (3,4) and (5,7) are bridges.