Кәсіпкер Ергежейлі Вроцлавта туристік гид бизнесін бастағысы келеді. Оның экскурсиялары қала ішімен жүретін автобуспен өткізіледі, және автобус қызықты көрікті жердің жанынан өткен сайын, автобустың дыбыс жүйесі арқылы сол жердің жазып алынған сипаттамасы ойнатылады.

Ергежейлі $1$-ден $N$-ге дейін нөмірленген $N$ көрікті жерді және әрқайсысы жұп көрікті жерді қосатын $M$ екі бағытты көшені қамтитын карта дайындады. Оның картасының таңғаларлық ерекшелігі — әрбір көрікті жер ең көбі $7$ көшемен ғана шектеседі. Әрбір экскурсия $3$ әртүрлі көрікті жерден тұратын тізбек болады, мұнда әрбір екі көршілес көрікті жер көшемен жалғанған.

Енді экскурсияларды таңдамас бұрын, ергежейлі көрікті жерлердің жазылған сипаттамаларын дайындап, кәсіби дикторларды жалдауы керек. Оның тек $4$ дикторды жалдауға ғана шамасы жетеді және ол әрбір көрікті жердің сипаттамасын бір диктордың көмегімен тек бір рет қана жаза алады. Алайда Кәсіпкер тіпті ең үздік диктордың дауысы да тыңдармандар үшін бірсарынды болып кетуі мүмкін деп алаңдайды, сондықтан ол кез келген мүмкін экскурсияда барлық $3$ сипаттаманы бір ғана диктор оқымауы керек деп шешті.

Ергежейлі әлі нақты бір экскурсияны таңдаған жоқ, ал дыбыс жазу студиясына бронь ертеңге белгіленген. Кез келген мүмкін экскурсияда оларды бір ғана диктор дыбыстамайтындай етіп, көрікті жерлерге дикторларды бөліп беруге оған көмектесіңіз.

Кіріс деректер

Кіріс деректердің бірінші жолында ергежейлінің картасындағы көрікті жерлер мен көшелер санын білдіретін бос орын арқылы бөлінген екі бүтін сан $N$ және $M$ берілген.

Келесі $M$ жол көрікті жерлерді қосатын көшелерді сипаттайды, мұнда $i$-ші жолда осы көшемен жалғанған көрікті жерлердің нөмірлерін білдіретін бос орын арқылы бөлінген екі бүтін сан $a_i$ және $b_i$ берілген.

Шығыс деректер

Бос орын арқылы бөлінген $N$ бүтін саннан тұратын $c_1, \dots, c_N$ жалғыз жолын шығарыңыз, мұндағы $c_i$ ($1 \le c_i \le 4$) — $i$-ші көрікті жердің сипаттамасын жазуы тиіс диктордың идентификаторы.

Егер шешімдер көп болса, олардың кез келгенін шығарыңыз. Әрбір тест жағдайында қандай да бір шешім бар деп есептей аласыз.

Шектеулер

$1 \le N \le 10^6$

$1 \le M \le 3.5 \cdot 10^6$

$1 \le a_i, b_i \le N$

$a_i \neq b_i$

ешбір көше көрікті жерді өзімен-өзі қоспайды,

ешбір көрікті жерлер жұбы бірден артық көшемен қосылмаған,

әрбір көрікті жер ең көбі $7$ көшемен шектеседі.

Мысалдар

Кіріс деректер 1

3 3
1 2
2 3
3 1

Шығыс деректер 1

2 1 1

Кіріс деректер 2

8 13
1 2
1 3
1 4
1 5
1 6
1 7
2 3
3 4
4 5
5 6
6 7
7 8
8 2

Шығыс деректер 2

2 3 1 3 1 3 1 1