CEOI 2017 - Day 1

Ngày xưa, có một quốc gia gồm \(n\) thành phố và \(m\) con đường hai chiều nối chúng. Khi các phương tiện giao thông ngày càng lớn và nhanh hơn, đường trở nên quá hẹp để hai xe đi ngược chiều tránh nhau. Chính phủ quyết định đổi mỗi con đường thành đường một chiều.

Sau khi đổi chiều, một số cặp thành phố trước đây đi lại được có thể không còn nối được theo hướng cần thiết. Chính phủ đưa ra \(p\) cặp thành phố quan trọng; với mỗi cặp \((x_i,y_i)\), cần có đường đi có hướng từ \(x_i\) đến \(y_i\). Đề bài đảm bảo luôn tồn tại cách định hướng thỏa mãn tất cả yêu cầu.

Với một số con đường, hướng đi bị bắt buộc trong mọi cách định hướng hợp lệ. Với những con đường còn lại, có thể tồn tại một cách định hướng hợp lệ khi đi từ thành phố đầu đến thành phố cuối của đường, và cũng có thể tồn tại một cách khác khi đi theo chiều ngược lại.

Hãy xác định trạng thái của từng con đường:

• R nếu mọi cách định hướng hợp lệ đều phải cho xe đi từ thành phố đầu tiên đến thành phố thứ hai của con đường đó.
• L nếu mọi cách định hướng hợp lệ đều phải cho xe đi từ thành phố thứ hai đến thành phố đầu tiên.
• B nếu có ít nhất một cách định hướng hợp lệ theo mỗi chiều.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n,m\) (\(1\le n,m\le100000\)), lần lượt là số thành phố và số con đường.

Mỗi dòng trong \(m\) dòng tiếp theo chứa hai số nguyên \(a_i,b_i\) (\(1\le a_i,b_i\le n\)), cho biết có con đường nối thành phố \(a_i\) và \(b_i\). Có thể có nhiều con đường nối cùng một cặp thành phố; một con đường cũng có thể nối một thành phố với chính nó.

Dòng tiếp theo chứa số nguyên \(p\) (\(1\le p\le100000\)), là số cặp thành phố cần liên thông theo hướng.

Mỗi dòng trong \(p\) dòng tiếp theo chứa hai số nguyên \(x_i,y_i\) (\(1\le x_i,y_i\le n\)), yêu cầu tồn tại đường đi có hướng từ \(x_i\) đến \(y_i\).

Dữ liệu ra

In một xâu gồm \(m\) ký tự. Ký tự thứ \(i\) là trạng thái của con đường thứ \(i\) theo quy tắc trong đề bài.

Ví dụ

5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3

BBRBBL

Giải thích

Con đường thứ năm nối thành phố \(1\) và \(3\) có thể được định hướng theo cả hai chiều trong các cách định hướng hợp lệ khác nhau. Chẳng hạn, hai xâu định hướng hợp lệ tương ứng là LLRLRL và RLRRLL.

Phân nhóm

1. \(30\) điểm: \(n,m\le1000\) và \(p\le100\).
2. \(30\) điểm: \(p\le100\).
3. \(40\) điểm: Không có ràng buộc bổ sung.

May rủi là một phần quan trọng của cá cược. Một số người tìm hiểu kỹ điều mình đặt cược để tăng cơ hội thắng. Bài toán này xét một cách khác: tận dụng việc nhiều nhà cái đưa ra tỷ lệ cược khác nhau cho cùng một sự kiện.

Sự kiện có hai kết quả có thể xảy ra. Có \(n\) nhà cái. Nhà cái thứ \(i\) đưa ra tỷ lệ \(a_i\) cho kết quả thứ nhất và \(b_i\) cho kết quả thứ hai. Nếu đặt cược \(1\) euro và dự đoán đúng, bạn nhận lại số euro bằng tỷ lệ đã chọn; nếu dự đoán sai, bạn không nhận được gì. Mỗi cược luôn tốn \(1\) euro.

Bạn có thể chọn bất kỳ tập con nào trong các lựa chọn cược được đưa ra, kể cả đặt cược vào cả hai kết quả tại cùng một nhà cái. Tuy nhiên, không được đặt nhiều hơn một cược vào cùng một kết quả tại cùng một nhà cái.

Với mỗi kết quả của sự kiện, lợi nhuận bằng tổng tiền nhận được từ các cược thắng trừ tổng số tiền đã đặt cược. Hãy tìm lợi nhuận được đảm bảo lớn nhất, tức là giá trị lớn nhất mà bạn có thể đảm bảo nhận được bất kể kết quả nào xảy ra.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\) (\(1\le n\le100000\)), là số nhà cái.

Mỗi dòng trong \(n\) dòng tiếp theo chứa hai số thực \(a_i,b_i\) (\(1.0\le a_i,b_i\le1000.0\)), là tỷ lệ cược cho kết quả thứ nhất và kết quả thứ hai tại nhà cái thứ \(i\). Mỗi số có không quá \(4\) chữ số sau dấu thập phân.

Dữ liệu ra

In lợi nhuận được đảm bảo lớn nhất, làm tròn và hiển thị đúng \(4\) chữ số sau dấu thập phân.

Ví dụ

4
1.4 3.7
1.2 2
1.6 1.4
1.9 1.5

0.5000

Giải thích

Một cách đặt cược tối ưu là cược vào kết quả thứ hai tại nhà cái thứ nhất, và cược vào kết quả thứ nhất tại nhà cái thứ ba và thứ tư. Nếu kết quả thứ nhất xảy ra, lợi nhuận là \(1.6+1.9-3=0.5\) euro. Nếu kết quả thứ hai xảy ra, lợi nhuận là \(3.7-3=0.7\) euro. Vì vậy lợi nhuận được đảm bảo là \(0.5\) euro.

Phân nhóm

1. \(20\) điểm: \(n\le10\).
2. \(40\) điểm: \(n\le1000\).
3. \(40\) điểm: Không có ràng buộc bổ sung.

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.