Sevimli rənglər
Hər bir fermer Conun inəyinin sevimli rəngi var. İnekler 1-dən n-ə qədər nömrələnib (həmişə olduğu kimi) və hər bir rəng 1-dən n-ə qədər tam ədədlə təmsil oluna bilər.
m cüt inək (a, b) mövcuddur ki, inək b inək a-ya heyran olur (1 ≤ m ≤ 2 * 10^5). Ola bilər ki, a = b, bu halda inək özünə heyran olur. Hər hansı bir rəng c üçün, əgər inəklər x və y sevimli rəngi c olan inəyə heyran olursa, o zaman x və y eyni sevimli rəngə malikdir.
Bu məlumat əsasında inəklərə sevimli rənglərin təyin edilməsini elə müəyyən edin ki, bütün inəklər arasında müxtəlif sevimli rənglərin sayı maksimum olsun. Bu xüsusiyyəti təmin edən bir neçə təyinat mövcud olduğundan, onlardan leksikoqrafik olaraq ən kiçiyini çıxarın (bu o deməkdir ki, 1 .. n inəklərinə təyin olunan rəngləri bu sırada minimallaşdırmalısınız).
Giriş məlumatları
Birinci sətir n (1 ≤ n ≤ 2 * 10^5) və m-i ehtiva edir. Növbəti m sətirdən hər biri iki tam ədəd a və b (1 ≤ a, b ≤ n) ehtiva edir, bu da inək b-nin inək a-ya heyran olduğunu göstərir. Eyni cütlük giriş məlumatlarında bir neçə dəfə görünə bilər.
Çıxış məlumatları
1..n-dən hər bir i üçün, istənilən təyinatda inək i-nin rəngini yeni sətirdə çıxarın.
Nümunə
Aşağıdakı şəkildə qalın sərhədli dairələr sevimli rəngi 1 olan inəkləri təmsil edir.
