İnek Toplantısı#10404
Dünyanın dört bir yanından inekler büyük bir toplantı için bir araya geldi. inek ve birbirleriyle arkadaş olan n - 1 inek çifti vardır. Her inek, bir arkadaşlık zinciri aracılığıyla diğer her ineği tanımaktadır.
Çok eğlendiler, ama şimdi birer birer ayrılma zamanı geldi. Geriye en az iki inek kaldığı sürece, kalan her ineğin en az bir arkadaşının kalan inekler arasında olması koşuluyla ayrılmak istiyorlar. Ayrıca, bagaj saklama sorunları nedeniyle, (a_i, b_i) şeklinde inek çifti vardır öyle ki a_i ineği b_i ineğinden önce ayrılmalıdır. Not: a_i ve b_i inekleri arkadaş olabilir ya da olmayabilir.
Her inek için, ineklerin son ayrılan inek olup olamayacağını belirlemelerine yardımcı olun. Yukarıdaki tüm kısıtlamaları sağlayan bir ayrılma sırasının bulunmaması mümkündür.
İlk satır iki tam sayı içerir: ve m~(1 \le n, m \le 10^5).
Sonraki n - 1 satırın her biri, x_i ve y_i~(1 \le x_i, y_i \le n, x_i \ne y_i) şeklinde iki tam sayı içerir; bu, x_i ve y_i ineklerinin arkadaş olduğu anlamına gelir.
Sonraki satırın her biri, a_i ve b_i~(1 \le a_i, b_i \le n, a_i \ne b_i) şeklinde iki tam sayı içerir; bu, a_i ineğinin b_i ineğinden önce ayrılması gerektiği anlamına gelir.
satır yazdırın. -inci satır, eğer ineği son ayrılan inek olabiliyorsa , olamıyorsa içermelidir.
Örnek 1