Theo truyền thuyết Ba Tư cổ đại trong sử thi Shahnameh, Zal, người anh hùng huyền thoại của Ba Tư, yêu say đắm Rudaba, công chúa của Kabul. Khi Zal cầu hôn Rudaba, cha nàng đã đưa ra một thử thách.

Ở Ba Tư có \(n\) thành phố, được đánh số từ \(0\) đến \(n-1\), và \(m\) con đường hai chiều, được đánh số từ \(0\) đến \(m-1\). Mỗi con đường nối hai thành phố phân biệt. Giữa mỗi cặp thành phố có nhiều nhất một con đường. Một số con đường là đường hoàng gia, được hoàng gia sử dụng để đi lại. Nhiệm vụ của Zal là xác định tất cả các con đường hoàng gia.

Zal có một bản đồ thể hiện tất cả các thành phố và con đường ở Ba Tư. Anh không biết những con đường nào là đường hoàng gia, nhưng có thể nhờ Simurgh, chú chim nhân từ huyền thoại luôn bảo vệ anh, giúp đỡ. Simurgh không muốn tiết lộ trực tiếp tập các đường hoàng gia. Thay vào đó, Simurgh cho biết tập tất cả các đường hoàng gia là một bộ vàng. Một tập các con đường là bộ vàng khi và chỉ khi thỏa mãn cả hai điều kiện sau:

• Tập đó gồm đúng \(n-1\) con đường.
• Với mỗi cặp thành phố, có thể đi từ thành phố này đến thành phố kia chỉ bằng các con đường thuộc tập đó.

Như vậy, một bộ vàng là một cây khung của mạng lưới đường. Zal có thể đặt câu hỏi cho Simurgh. Trong mỗi câu hỏi, Zal chọn một bộ vàng, rồi Simurgh cho biết có bao nhiêu con đường trong bộ vàng đó là đường hoàng gia.

Hãy giúp Zal tìm tập tất cả các đường hoàng gia bằng cách đặt nhiều nhất \(q\) câu hỏi. Trình chấm sẽ đóng vai Simurgh. Giới hạn \(q\) được quy định riêng cho từng subtask.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau, được khai báo trong tệp simurgh.h:

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v);

• n: số thành phố.
• u, v: hai mảng có độ dài \(m\). Với mọi \(0 \le i \le m-1\), con đường \(i\) nối hai thành phố \(u[i]\) và \(v[i]\).
• Hàm phải trả về một mảng có độ dài \(n-1\), chứa nhãn của tất cả các đường hoàng gia, theo thứ tự tùy ý.

Trong quá trình thực hiện, hàm find_roads được gọi hàm sau của trình chấm nhiều nhất \(q\) lần:

int count_common_roads(const std::vector<int>& r);

• r: mảng có độ dài \(n-1\), chứa nhãn các con đường của một bộ vàng, theo thứ tự tùy ý.
• Hàm trả về số đường hoàng gia trong bộ vàng được mô tả bởi r.

Mỗi truy vấn phải hợp lệ: các phần tử của r phải là \(n-1\) nhãn phân biệt trong khoảng từ \(0\) đến \(m-1\), và các con đường tương ứng phải nối được tất cả \(n\) thành phố. Chỉ có đủ \(n-1\) nhãn là chưa đủ để tạo thành một bộ vàng.

Ví dụ

Xét lời gọi:

find_roads(4, {0, 0, 0, 1, 1, 2}, {1, 2, 3, 2, 3, 3});

Trong ví dụ này có \(4\) thành phố và \(6\) con đường. Ký hiệu \((a,b)\) là con đường nối hai thành phố \(a\) và \(b\). Các đường mang nhãn từ \(0\) đến \(5\) lần lượt là \((0,1)\), \((0,2)\), \((0,3)\), \((1,2)\), \((1,3)\) và \((2,3)\). Mỗi bộ vàng gồm \(n-1=3\) con đường.

Giả sử các đường hoàng gia mang nhãn \(0\), \(1\) và \(5\), tức là các đường \((0,1)\), \((0,2)\) và \((2,3)\). Khi đó:

• count_common_roads({0, 1, 2}) trả về \(2\). Truy vấn này chọn các đường \((0,1)\), \((0,2)\) và \((0,3)\), trong đó có hai đường hoàng gia.
• count_common_roads({5, 1, 0}) trả về \(3\). Truy vấn này chọn đúng tập tất cả các đường hoàng gia.

Hàm find_roads phải trả về mảng [5, 1, 0] hoặc một mảng độ dài \(3\) chứa đúng ba phần tử đó theo thứ tự khác.

Các lời gọi sau không hợp lệ:

• count_common_roads({0, 1}): mảng r không có độ dài \(3\).
• count_common_roads({0, 1, 3}): các đường \((0,1)\), \((0,2)\) và \((1,2)\) không tạo thành một bộ vàng, vì không thể đi từ thành phố \(0\) đến thành phố \(3\) chỉ bằng các đường này.

Ràng buộc

• \(2 \le n \le 500\).
• Số con đường thỏa mãn:

• Với mọi \(0 \le i \le m-1\), \(0 \le u[i],v[i] \le n-1\) và \(u[i] \ne v[i]\).
• Giữa mỗi cặp thành phố có nhiều nhất một con đường.
• Có thể đi lại giữa bất kỳ hai thành phố nào bằng các con đường đã cho.
• Tập tất cả các đường hoàng gia là một bộ vàng.
• Hàm find_roads được gọi count_common_roads nhiều nhất \(q\) lần. Trong mỗi lần gọi, các con đường được mô tả bởi r phải tạo thành một bộ vàng.
• Giới hạn thời gian: \(2\) giây. Giới hạn bộ nhớ: \(1024\) MiB.

Phân nhóm

Trình chấm mẫu

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

• Dòng \(1\): \(n\ m\).
• Dòng \(2+i\), với mọi \(0 \le i \le m-1\): \(u[i]\ v[i]\).
• Dòng \(2+m\): \(s[0]\ s[1]\ \ldots\ s[n-2]\).

Ở đây, \(s[0],s[1],\ldots,s[n-2]\) là nhãn của các đường hoàng gia.

Trình chấm mẫu in YES nếu find_roads gọi count_common_roads nhiều nhất \(30\,000\) lần và trả về đúng tập các đường hoàng gia. Ngược lại, trình chấm mẫu in NO.

Hàm count_common_roads trong trình chấm mẫu không kiểm tra đầy đủ các tính chất của bộ vàng. Nó đếm và trả về số nhãn đường hoàng gia xuất hiện trong mảng r. Tuy nhiên, nếu bài nộp gọi count_common_roads với một tập nhãn không mô tả một bộ vàng, bài nộp sẽ nhận kết quả Wrong Answer.

Dữ liệu mẫu

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

Với chương trình tìm đúng tập đường hoàng gia và tuân thủ giới hạn số lần gọi, trình chấm mẫu in:

YES

Chú ý kỹ thuật

Trong C++ và Pascal, hàm count_common_roads sử dụng cách truyền tham số bằng tham chiếu để tăng hiệu quả. Bạn vẫn có thể gọi hàm theo cách thông thường. Trình chấm bảo đảm không thay đổi giá trị của r.