Santa Clauses và giải bóng đá

Đất nước Treeland gồm $n$ thành phố được nối bởi $n-1$ con đường hai chiều sao cho từ bất kỳ thành phố nào cũng đi được tới mọi thành phố khác (mạng lưới tạo thành một cây).

Sắp tới có một giải bóng đá với $2k$ đội đến từ $2k$ thành phố khác nhau. Ở vòng đầu, các đội được chia thành $k$ cặp. Mỗi cặp thi đấu hai trận: một trận ở thành phố quê nhà của đội thứ nhất và một trận ở thành phố quê nhà của đội thứ hai.

Ban tổ chức cần chọn ra một số thành phố để bố trí chỗ ở cho các đội, và muốn dùng càng ít thành phố càng tốt. Ràng buộc:

• Nếu một đội thi đấu ở hai thành phố $u$ và $v$ thì đội đó phải ở tại một thành phố nằm trên đường đi ngắn nhất giữa $u$ và $v$ (có thể là chính $u$ hoặc $v$).
• Hai đội trong cùng một cặp phải ở tại cùng một thành phố.

Hãy chia $2k$ đội thành $k$ cặp và chọn số thành phố bố trí chỗ ở nhỏ nhất có thể là $m$, sao cho mỗi cặp ở tại một thành phố nằm trên đường đi giữa hai quê nhà của cặp đó.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ cho biết có một con đường nối thành phố $a$ và $b$.
• Dòng cuối chứa $2k$ số nguyên phân biệt $c_1,c_2,\dots ,c_{2k}$, trong đó $c_i$ là quê nhà của đội thứ $i$.

Dữ liệu ra

• Dòng đầu in ra số nguyên dương $m$: số thành phố ít nhất cần dùng để bố trí chỗ ở.
• Dòng thứ hai in ra $m$ số phân biệt $d_1,d_2,\dots ,d_m$: chỉ số các thành phố được chọn để bố trí chỗ ở.
• $k$ dòng tiếp theo, dòng thứ $j$ chứa ba số $u_j$, $v_j$, $x_j$: $u_j$ và $v_j$ là quê nhà của hai đội trong cặp thứ $j$, còn $x_j$ là thành phố mà cặp đó ở. Mỗi số trong $c_1,\dots ,c_{2k}$ phải xuất hiện đúng một lần trong toàn bộ các $u_j$ và $v_j$. Mỗi $x_j$ phải thuộc $\{d_1,\dots ,d_m\}$.

Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

• $2\le n\le 2·{10}^5$
• $2\le 2k\le n$
• $1\le a,b\le n$, $a\ne b$
• $1\le c_i\le n$, các $c_i$ phân biệt.

Ví dụ