Sıyıq#10308
Fermer Conun inəkləri səhər yeməyində yalnız dənli bitkiləri sevirlər! Əslində, inəklərin iştahı o qədər böyükdür ki, hər biri bir oturuşda bütün bir qutu dənli bitki yeyir.
Son zamanlarda təsərrüfata fərqli növ dənli bitki partiyası gəlib.
Təəssüf ki, hər dənli bitkinin yalnız bir qutusu var! Hər bir inəyin sevimli və ikinci sevimli dənli bitkisi var. İnəklər dənli bitkiləri seçərkən aşağıdakı prosesi izləyirlər:
Əgər sevimli dənli bitkisinin qutusu hələ də mövcuddursa, onu götürür və gedir.
Əks halda, əgər ikinci sevimli dənli bitkisinin qutusu hələ də mövcuddursa, onu götürür və gedir.
Əks halda, məyus halda heç nə götürmədən gedir.
İnəklər dənli bitkilər üçün sıraya düzülüb. Hər bir i~(0 \le i \le n − 1) dəyəri üçün, fermer Con sıranın əvvəlindən ilk inəyi çıxarsa, neçə inəyin dənli bitki qutusu götürəcəyini müəyyən edin.
Birinci sətir iki tam ədəd n~(1 \le n \le 10^5) və m~(1 \le m \le 10^5) ehtiva edir. Hər bir i~(1 \le i \le n)-ci sətir iki tam ədəd f_i və s_i~(1 \le f_i, s_i \le m və f_i \ne s_i) ehtiva edir, bu da növbədəki -ci inəyin birinci və ikinci sevimli dənli bitkisini göstərir.
Hər bir i~(0 \le i \le n − 1) dəyəri üçün, üçün cavabı ehtiva edən bir sətir çıxarın.
Əgər ən azı iki inək qalarsa, onlardan ikisinə dəqiq bir qutu dənli bitki düşəcək.
Nümunə 1