Kết nối đặc biệt

Cho một đồ thị vô hướng liên thông có trọng số gồm \(n\) đỉnh, \(m\) cạnh. Cạnh thứ \(i\ (1 \le i \le m)\) nối hai đỉnh \(u_i\) và \(v_i\ (1 \le u_i \neq v_i \le n)\) với trọng số là \(2^i\).

Yêu cầu: Cho \(k\) đỉnh đặc biệt \(s_1, s_2, \ldots, s_k\), hãy chọn ra các cạnh với tổng trọng số nhỏ nhất
để liên thông được \(k\) đỉnh.

Input

• Dòng đầu chứa ba số \(n, m, k\ (n, m, k \le 3.10^5)\).
• Dòng thứ \(i\) trong \(m\) dòng, mỗi dòng chứa hai số \(u_i, v_i\).
• Dòng cuối cùng chứa \(k\) số nguyên mô tả \(k\) đỉnh đặc biệt.

Output

• Gồm một dòng chứa \(m\) số, số thứ \(i\) bằng số \(1\) hoặc \(0\) tương ứng là cạnh thứ \(i\) được chọn hoặc không được chọn.

Example

4 4 2
1 2
2 3
3 4
1 4
2 4

0 1 1 0