Trạm Phát Trung Tâm · canuc80k3302

Một hệ thống gồm $n$ trạm, nối với nhau bởi $n - 1$ liên kết. Nếu bỏ qua chiều, các liên kết tạo thành một cây. Mỗi liên kết hiện chỉ truyền tín hiệu theo một chiều.

Bạn sẽ chọn một trạm làm trạm phát trung tâm. Sau đó, tín hiệu phải đi được từ trạm này đến mọi trạm khác theo chiều các liên kết. Trước khi phát, bạn được phép đảo chiều bất kỳ liên kết nào; mỗi liên kết bị đảo được tính một lần.

Hãy tìm số liên kết ít nhất cần đảo và tất cả các trạm có thể làm trung tâm với số lần đảo ít nhất đó.

Input

Dòng đầu chứa số nguyên $n$ .
Mỗi dòng trong $n - 1$ dòng tiếp theo chứa hai số nguyên $u$ và $v$ , cho biết liên kết ban đầu có chiều từ $u$ đến $v$ .

Output

Dòng đầu in số liên kết ít nhất cần đảo.
Dòng thứ hai in tất cả chỉ số trạm đạt giá trị nhỏ nhất, theo thứ tự tăng dần và cách nhau bởi dấu cách.

Constraints

$2 \leq n \leq 2 \cdot 1 0^{5}$ .
$1 \leq u, v \leq n$ và $u \neq = v$ .
Khi bỏ qua chiều, $n - 1$ liên kết tạo thành một cây.
Mỗi giới hạn trên áp dụng cho một test độc lập.

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 15$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

0
4

Giải thích: Nếu chọn trạm $4$ , các liên kết đã hướng lần lượt tới $2$ , rồi từ $2$ tới $1$ và $3$ , đồng thời từ $4$ tới $5$ . Vì vậy không cần đảo liên kết nào.

Phân tích: Lưu mỗi cạnh có hướng u -> v thành hai cung: đi từ u sang v có chi phí 0, còn đi ngược lại có chi phí 1. Tổng chi phí khi gốc tạm là 1 chính là số cạnh cần đảo.
Thuật toán: Duyệt từ gốc 1 để tính chi phí ban đầu và ghi chi phí của cạnh cha-con. Khi chuyển gốc từ cha u sang con v, chỉ yêu cầu đối với cạnh u-v đổi chiều: nếu trước đó cạnh đúng thì chi phí tăng 1, nếu trước đó sai thì chi phí giảm 1. Sau khi có chi phí của mọi gốc, lấy minimum và quét chỉ số tăng dần để in.
Chứng minh: Hai gốc kề nhau nằm khác phía chỉ đối với cạnh nối chúng; với mọi cạnh khác, hướng đi ra xa gốc vẫn yêu cầu cùng một chiều. Vì vậy công thức cộng hoặc trừ một phản ánh đúng toàn bộ thay đổi. Khởi đầu ở gốc 1 được đếm trực tiếp, nên quy nạp qua các cạnh cho chi phí đúng ở mọi đỉnh; việc lấy minimum và in mọi vị trí đạt minimum hoàn tất yêu cầu.
Độ phức tạp: Thời gian O(n), bộ nhớ O(n).