Tập Hợp Đàn Bò

Có $N$ con bò kết nối với nhau qua $N-1$ cặp bạn bè tạo thành cây (mọi bò đều kết nối với nhau qua chuỗi bạn bè). Các bò phải rời đi lần lượt từng con theo quy tắc: chừng nào còn ít nhất hai con bò, mỗi con còn lại phải có ít nhất một bạn cũng còn lại (tức là bò rời đi phải là lá của cây con còn lại).

Ngoài ra có $M$ ràng buộc thứ tự: mỗi ràng buộc $(a_i,b_i)$ yêu cầu bò $a_i$ phải rời đi trước bò $b_i$.

Với mỗi con bò $i$ từ $1$ đến $N$, hãy xác định: liệu bò $i$ có thể là con cuối cùng rời đi (thỏa mãn tất cả ràng buộc) hay không?

Dữ liệu vào

• Dòng 1: hai số nguyên $N$ và $M$ ($1\le N,M\le {10}^5$)
• $N-1$ dòng tiếp theo: mỗi dòng hai số nguyên $x_i,y_i$ — cặp bạn bè (cạnh của cây)
• $M$ dòng tiếp theo: mỗi dòng hai số nguyên $a_i,b_i$ — bò $a_i$ phải rời trước bò $b_i$

Dữ liệu ra

• $N$ dòng, dòng $i$ chứa $1$ nếu bò $i$ có thể là con cuối cùng, ngược lại chứa $0$.

Ràng buộc

• $1\le N,M\le {10}^5$

Ví dụ