İnəklərin Toplantısı#10404
Dünyanın hər yerindən inəklər böyük bir toplantı üçün bir araya gəliblər. inək və bir-biri ilə dost olan n - 1 cüt inək var. Hər inək digər bütün inəkləri hansısa dostluq zənciri vasitəsilə tanıyır.
Onlar çox əyləniblər, amma indi onlar üçün bir-bir ayrılmaq vaxtıdır. Onlar elə bir ardıcıllıqla ayrılmaq istəyirlər ki, ən azı iki inək qaldığı müddətcə, qalan hər inəyin ən azı bir qalan dostu olsun. Bundan əlavə, baqajın saxlanması ilə bağlı problemlərə görə, cüt inək (a_i, b_i) var ki, a_i inəyi b_i inəyindən əvvəl ayrılmalıdır. Qeyd edək ki, a_i və b_i inəkləri dost ola da bilər, olmaya da bilər.
Hər bir inək üçün, inəklərə onun sonuncu ayrılan ola bilib-bilməyəcəyini müəyyən etməkdə kömək edin. Yuxarıdakı bütün şərtləri ödəyən heç bir ayrılma ardıcıllığının olmaması mümkündür.
Birinci sətirdə iki tam ədəd və m~(1 \le n, m \le 10^5) verilir.
Sonrakı n - 1 sətirin hər birində iki tam ədəd x_i və y_i~(1 \le x_i, y_i \le n, x_i \ne y_i) verilir, bu da x_i və y_i inəklərinin dost olduğunu bildirir.
Sonrakı sətirin hər birində iki tam ədəd a_i və b_i~(1 \le a_i, b_i \le n, a_i \ne b_i) verilir, bu da a_i inəyinin b_i inəyindən əvvəl toplantını tərk etməli olduğunu bildirir.
sətir çap edin. -ci sətir, əgər inəyi sonuncu ayrıla bilərsə , əks halda olmalıdır.
Nümunə 1