Những cô bò từ khắp nơi trên thế giới đã tập hợp về dự một cuộc tụ họp quy mô lớn. Có \(N\) cô bò và \(N-1\) cặp bò là bạn của nhau. Mỗi cô bò đều biết mọi cô bò khác thông qua một chuỗi quan hệ bạn bè nào đó.

Chúng đã có một khoảng thời gian tuyệt vời, nhưng giờ đã đến lúc lần lượt rời đi từng cô một. Chúng muốn rời đi theo một thứ tự sao cho chừng nào vẫn còn ít nhất hai cô bò, mỗi cô bò còn lại đều có ít nhất một người bạn vẫn còn ở đó. Ngoài ra, do những vấn đề về chỗ cất hành lý, có \(M\) cặp bò \((a_i, b_i)\) sao cho cô bò \(a_i\) phải rời đi trước cô bò \(b_i\). Lưu ý rằng cô bò \(a_i\) và cô bò \(b_i\) có thể là bạn hoặc không.

Hãy giúp các cô bò xác định, với mỗi cô bò, liệu cô có thể là cô bò cuối cùng rời đi hay không. Có thể không tồn tại cách nào để các cô bò rời đi mà thỏa mãn những ràng buộc trên.

Dữ liệu vào

Dòng \(1\) chứa hai số nguyên \(N\) và \(M\) cách nhau bởi dấu cách.

Mỗi dòng \(2 \leq i \leq N\) chứa hai số nguyên \(x_i\) và \(y_i\) với \(1 \leq x_i, y_i \leq N\) và \(x_i \neq y_i\), cho biết cô bò \(x_i\) và cô bò \(y_i\) là bạn.

Mỗi dòng \(N+1 \leq i \leq N+M\) chứa hai số nguyên \(a_i\) và \(b_i\) với \(1 \leq a_i, b_i \leq N\) và \(a_i \neq b_i\), cho biết cô bò \(a_i\) phải rời cuộc tụ họp trước cô bò \(b_i\).

Đảm bảo rằng \(1 \leq N, M \leq 10^5\).

Phân nhóm

Trong các trường hợp kiểm thử chiếm \(20\%\) số điểm, còn đảm bảo thêm rằng \(N, M \leq 3000\).

Dữ liệu ra

Dữ liệu ra gồm \(N\) dòng, mỗi dòng chứa một số nguyên \(d_i\) sao cho \(d_i = 1\) nếu cô bò \(i\) có thể là cô bò cuối cùng rời đi, và \(d_i = 0\) nếu không thể.

Ví dụ

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

0
0
1
1
1

Nguồn

Đề bài gốc: USACO 2018 December Contest, Platinum — The Cow Gathering

Tác giả: Dhruv Rohatgi