GRAPH_ - Tìm khớp và cầu (Cơ bản)

Giới hạn

• Thời gian: 0.1s
• Bộ nhớ: 1536MB
• Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Xét đơn đồ thị vô hướng G = (V, E) có n (1 <= n <= 10000) đỉnh và m (1 <= m <= 50000) cạnh. Người ta định nghĩa một đỉnh gọi là khớp nếu như xoá đỉnh đó sẽ làm tăng số thành phần liên thông của đồ thị. Tương tự như vậy, một cạnh được gọi là cầu nếu xoá cạnh đó sẽ làm tăng số thành phần liên thông của đồ thị.

Vấn đề đặt ra là cần phải đếm tất cả các khớp và cầu của đồ thị G.

Input

Dòng đầu: chứa hai số tự nhiên n,m.

M dòng sau mỗi dòng chứa một cặp số (u,v) (u khác v, 1 <= u <= n, 1 <= v < n) mô tả một cạnh của G.

Output

Gồm một dòng duy nhất ghi hai số, số thứ nhất là số khớp, số thứ hai là số cầu của G

Example

 

Input:
10 12
1 10
10 2
10 3
2 4
4 5
5 2
3 6
6 7
7 3
7 8
8 9
9 7

Output:
4 3

 

 

 

 

---

• Người up: company_1
• Nguồn bài: Bài cổ điển - tests added by canhteo