Có bạn, bạn thứ thích địa điểm . Có yêu cầu, yêu cầu thứ là hai bạn , muốn đi cùng nhau. Chia các bạn thành nhóm sao cho tất cả yêu cầu được đảm bảo và số bạn được đi đúng địa điểm yêu thích là nhiều nhất. Duy có thể bỏ duy nhất một yêu cầu. Với mỗi yêu cầu bị bỏ, tính số bạn được đi đúng địa điểm yêu thích nhiều nhất.
Dữ liệu:
Dòng đầu chưa hai số nguyên .
Dòng thứ hai chứa số nguyên .
dòng cuối, mỗi dòng hai số nguyên .
Kết quả: Ghi ra số nguyên , với là số bạn được đi đúng địa điểm yêu thích nếu bỏ yêu cầu thứ .
Ví dụ:
Dữ liệu:
7 5
1 2 1 2 1 2 1
1 2
1 3
2 4
5 6
5 7
Kết quả:
6 5 5 5 4
Giới hạn:
Subtask 1: (10%).
Subtask 2: Mỗi bạn xuất hiện trong không quá 2 yêu cầu (20%).
