Dumbo có một mê cung lớn gồm \(n\) căn phòng, đánh số từ \(1\) đến \(n\), nối với nhau bằng \(n-1\) lối đi sao cho luôn có thể đi từ phòng bất kỳ đến phòng khác. Một con chuột đã lẻn vào mê cung. Dumbo rất sợ chuột nên đặt bẫy ở phòng \(t\). Con chuột cố tránh phòng có bẫy, vì vậy Dumbo phải tìm cách dụ nó vào bẫy.

Con chuột chạy liên tục và không dừng lại nếu vẫn còn lối đi để đi. Sau khi đi qua một lối, nó để lại dấu bẩn và sẽ không tự đi qua lối đó lần nữa. Dumbo có thể làm một trong hai việc trong lượt của mình:

• Dọn sạch một lối đang bẩn.
• Chặn một lối bất kỳ bằng đá, dù lối đó sạch hay bẩn.

Dumbo không thể mở lại lối đã bị chặn. Anh ấy cũng có thể chọn không làm gì. Lượt không làm gì không được tính là một nước đi. Đến lượt chuột, nó chọn một lối sạch chưa bị chặn đi từ phòng hiện tại sang phòng kề bên. Nếu không có lối nào như vậy, chuột không di chuyển.

Ban đầu mọi lối đều sạch, chuột ở phòng \(m\), bẫy ở phòng \(t\), và Dumbo đi trước. Nếu cả hai chơi tối ưu, hãy tìm số nước đi ít nhất mà Dumbo cần thực hiện để dụ chuột vào bẫy; chuột tìm cách làm số nước đi của Dumbo lớn nhất.

Dữ liệu vào

Dòng đầu chứa ba số nguyên \(n,t,m\) (\(1\le n,t,m\le1000000\)), lần lượt là số phòng, phòng đặt bẫy và phòng ban đầu của chuột.

Mỗi dòng trong \(n-1\) dòng tiếp theo chứa hai số nguyên \(a_i,b_i\), cho biết có lối đi giữa hai phòng \(a_i\) và \(b_i\). Dữ liệu vào có kích thước lớn.

Dữ liệu ra

In số nước đi ít nhất của Dumbo.

Ví dụ

10 1 4
1 2
2 3
2 4
3 9
3 5
4 7
4 6
6 8
7 10

4

Giải thích ví dụ

Một diễn biến có thể xảy ra:

1. Dumbo chặn lối đi giữa phòng \(4\) và phòng \(7\).
2. Chuột đi đến phòng \(6\); lối đi giữa phòng \(4\) và phòng \(6\) trở nên bẩn.
3. Dumbo chặn lối đi giữa phòng \(6\) và phòng \(8\). Chuột không thể di chuyển vì lối duy nhất còn nối với phòng \(6\) đang bẩn.
4. Dumbo dọn sạch lối đi giữa phòng \(4\) và phòng \(6\).
5. Chuột quay lại phòng \(4\); lối đi giữa phòng \(4\) và phòng \(6\) lại trở nên bẩn.
6. Dumbo chặn lối đi giữa phòng \(2\) và phòng \(3\).
7. Chuột đi đến phòng \(2\); lối đi giữa phòng \(2\) và phòng \(4\) trở nên bẩn.
8. Dumbo không làm gì, nên lượt này không được tính là nước đi.
9. Chuột chỉ có thể đi đến phòng \(1\) và bị bắt.

Dumbo đã thực hiện \(4\) nước đi.

Phân nhóm

1. \(20\) điểm: \(n\le10\).
2. \(25\) điểm: Có lối đi trực tiếp giữa phòng \(m\) và phòng \(t\).
3. \(20\) điểm: \(n\le1000\).
4. \(35\) điểm: Không có ràng buộc bổ sung.