Il raduno delle mucche#10404
Mucche da tutto il mondo si sono radunate per un grande raduno. Ci sono mucche e n - 1 coppie di mucche che sono amiche tra loro. Ogni mucca conosce ogni altra mucca attraverso qualche catena di amicizie.
Si sono divertite molto, ma ora è giunto il momento di andarsene, una alla volta. Vogliono andarsene in un ordine tale che, finché rimangono almeno due mucche, ogni mucca rimasta abbia almeno un'amica rimasta. Inoltre, a causa di problemi con il deposito bagagli, ci sono coppie di mucche (a_i, b_i) tali che la mucca a_i debba andarsene prima della mucca b_i. Si noti che le mucche a_i e b_i possono essere amiche oppure no.
Per ogni mucca, aiuta le mucche a determinare se può essere l'ultima ad andarsene. È possibile che non esista alcun ordine di partenza che soddisfi tutti i vincoli sopra indicati.
La prima riga contiene due interi e m~(1 \le n, m \le 10^5).
Ciascuna delle successive n - 1 righe contiene due interi x_i e y_i~(1 \le x_i, y_i \le n, x_i \ne y_i), a indicare che le mucche x_i e y_i sono amiche.
Ciascuna delle successive righe contiene due interi a_i e b_i~(1 \le a_i, b_i \le n, a_i \ne b_i), a indicare che la mucca a_i deve andarsene prima della mucca b_i.
Stampa righe. La -esima riga deve contenere se la mucca può essere l'ultima ad andarsene, e altrimenti.
Esempio 1