Cặp đỉnh một chiều

Buổi 24 — Mock Contest Phase 1
Points
15
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho đồ thị có hướng đơn giản gồm $N$ đỉnh và $M$ cung (không có khuyên, không có cung song song cùng hướng).

Một cặp đỉnh không thứ tự ${u, v}$ ($u < v$) được gọi là một chiều nếu tồn tại cung $u \to v$ hoặc cung $v \to u$, nhưng không tồn tại cả hai.

Ngoài ra, độ chênh lệch của một đỉnh $u$ được định nghĩa là $\text{outdeg}(u) - \text{indeg}(u)$ (bậc ra trừ bậc vào).

Hãy tìm:

  1. Số lượng cặp đỉnh một chiều.
  2. Đỉnh có độ chênh lệch lớn nhất (nếu có nhiều đỉnh cùng đạt giá trị lớn nhất, chọn đỉnh có chỉ số nhỏ nhất).
Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N, M$ ($1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$).
  • $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le N$, $u \ne v$) mô tả một cung có hướng $u \to v$.
Dữ liệu ra
  • In ra hai số nguyên cách nhau bởi dấu cách: số cặp đỉnh một chiều và đỉnh có độ chênh lệch lớn nhất.
Ví dụ
Input Output
4 4
1 2
2 1
2 3
3 4
2 2
3 3
1 2
2 3
3 1
3 1
Giới hạn
  • $1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$.
Draft saved