Thành phố Baku có \(n\) điểm du lịch, được đánh số từ \(0\) đến \(n-1\). Thành phố cũng có \(m\) con đường hai chiều, được đánh số từ \(0\) đến \(m-1\). Mỗi con đường nối hai điểm du lịch khác nhau. Có thể di chuyển giữa hai điểm du lịch bất kì thông qua những con đường này.

Fatima đang lên kế hoạch thăm tất cả các điểm du lịch trong ba ngày. Cô ấy đã quyết định sẽ thăm \(a\) điểm du lịch vào ngày thứ nhất, \(b\) điểm du lịch vào ngày thứ hai và \(c\) điểm du lịch vào ngày thứ ba. Vì vậy, cô ấy sẽ phân hoạch \(n\) điểm du lịch thành ba tập \(A\), \(B\) và \(C\) có kích thước tương ứng là \(a\), \(b\) và \(c\). Mỗi điểm du lịch thuộc đúng một tập, do đó \(a+b+c=n\).

Fatima muốn tìm các tập \(A\), \(B\) và \(C\) sao cho ít nhất hai trong ba tập này liên thông. Một tập \(S\) các điểm du lịch được gọi là liên thông nếu có thể di chuyển giữa hai điểm du lịch bất kì trong \(S\) bằng cách sử dụng các con đường và không đi qua bất kì điểm du lịch nào không thuộc \(S\). Một phân hoạch các điểm du lịch thành các tập \(A\), \(B\) và \(C\) được gọi là hợp lệ nếu thỏa mãn các điều kiện trên.

Hãy giúp Fatima tìm một phân hoạch hợp lệ của các điểm du lịch với \(a\), \(b\) và \(c\) cho trước, hoặc xác định rằng không tồn tại phân hoạch hợp lệ nào. Nếu có nhiều phân hoạch hợp lệ, bạn có thể tìm bất kì phân hoạch nào trong số đó.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau trong C++, với khai báo trong tệp split.h:

std::vector<int> find_split(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q);

• \(n\): số lượng điểm du lịch.
• \(a\), \(b\) và \(c\): kích thước mong muốn của các tập \(A\), \(B\) và \(C\) tương ứng.
• \(p\) và \(q\): các mảng có độ dài \(m\), chứa các điểm đầu mút của các con đường. Với mỗi \(i\) (\(0 \leq i \leq m-1\)), \(p[i]\) và \(q[i]\) là hai điểm du lịch được nối bằng con đường \(i\).
• Hàm cần trả về một mảng có độ dài \(n\). Gọi mảng này là \(s\). Nếu không tồn tại phân hoạch hợp lệ nào, \(s\) phải chứa \(n\) số \(0\). Ngược lại, với \(0 \leq i \leq n-1\), \(s[i]\) phải nhận một trong ba giá trị \(1\), \(2\) hoặc \(3\), cho biết điểm du lịch \(i\) thuộc tập \(A\), \(B\) hoặc \(C\) tương ứng.

Các ví dụ

Ví dụ 1

Xét lời gọi hàm sau:

find_split(9, 4, 2, 3, {0, 0, 0, 0, 0, 0, 1, 3, 4, 5},
                       {1, 2, 3, 4, 6, 8, 7, 7, 5, 6});

Một kết quả đúng có thể trả về là \([1, 1, 3, 1, 2, 2, 3, 1, 3]\). Kết quả này mô tả phân hoạch sau:

• \(A=\{0, 1, 3, 7\}\).
• \(B=\{4, 5\}\).
• \(C=\{2, 6, 8\}\).

Các tập \(A\) và \(B\) liên thông.

Ví dụ 2

Xét lời gọi hàm sau:

find_split(6, 2, 2, 2, {0, 0, 0, 0, 0}, {1, 2, 3, 4, 5});

Không tồn tại phân hoạch hợp lệ nào. Vì vậy, kết quả đúng duy nhất là \([0, 0, 0, 0, 0, 0]\).

Giới hạn

• \(3 \leq n \leq 100\,000\).
• \(2 \leq m \leq 200\,000\).
• \(1 \leq a, b, c \leq n\).
• \(a+b+c=n\).
• Có nhiều nhất một con đường nối mỗi cặp điểm du lịch.
• Có thể di chuyển giữa hai điểm du lịch bất kì thông qua các con đường.
• \(0 \leq p[i], q[i] \leq n-1\) và \(p[i] \neq q[i]\) với mọi \(0 \leq i \leq m-1\).

Giới hạn thời gian: 2 giây. Giới hạn bộ nhớ: 1024 MiB.

Các subtasks

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

• Dòng \(1\): \(n\ m\).
• Dòng \(2\): \(a\ b\ c\).
• Dòng \(3+i\) (với \(0 \leq i \leq m-1\)): \(p[i]\ q[i]\).

Trình chấm mẫu in ra một dòng duy nhất chứa các phần tử của mảng do find_split trả về, cách nhau bởi dấu cách.

Dữ liệu mẫu 1

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

1 1 3 1 2 2 3 1 3

Dữ liệu mẫu 2

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

0 0 0 0 0 0

Nguồn: Đề thi chính thức IOI 2019, ngày 1, bài “Split the Attractions” (split); bản tiếng Việt, bản Markdown và gói đính kèm của ban tổ chức.