Боење
Дадени се N точки, означени со целите броеви од 1 до N. Дадени се и E отсечки, при што секоја од нив поврзува две од дадените точки.
Ваша задача е да ја избоите секоја од отсечките или во црвена или во сина боја. Притоа, треба да внимавате од секоја точка која е крајна точка на повеќе од една отсечка, мора да излегуваат отсечки од двете бои (треба да има по барем една отсечка обоена со црвена и барем една отсечка обоена со сина боја која излегува од таа точка).
Најдете едно решение за валидно обојување (обојување кое одговара на горното правило) на сите Е отсечки. Ако не постои валидно обојување, треба да се отпечати 0.
Влез
Во првиот ред се наоѓаат броевите N и E одделени со едно празно место (1 <= N, E <= 100 000).
Во секој од следните E редови се опишани отсечките по редослед. Така, во секој ред се наоѓаат по два броја Ai и Bi, одделени со по едно празно место, кои означуваат дека i-тата отсечка ги поврзува точката Ai и точката Bi (1 <= Аi, Bi <= N, Ai <> Bi).
Меѓу кои било две точки ќе има најмногу една отсечка.
За тест случаи кои носат најмногу 60% од поените ќе важи: N <= 1 000 и E <= 5 000.
Излез
Ако не постои валидно обојување, тогаш во првиот ред се печати 0.
Ако постои валидно обојување, тогаш, во еден ред се печатат точно E знаци. Притоа, i-тиот знак ја претставува бојата со која што треба да се обои i-тата отсечка. Ако отсечката е обоена со црвена боја тогаш i-тиот знак е ‘1’, а ако е обоена со сина боја тогаш i-тиот знак е ‘2’ (1 <= i <= E).
Ако има повеќе валидни решенија, треба да се отпечати кое било валидно решение.
Ограничувања
Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes
Примери
влез 5 6 1 2 2 3 3 1 3 4 1 4 4 5 | излез 212211 |
влез 7 7 1 2 2 3 3 1 4 5 5 6 6 7 7 4 | излез 0 |
Објаснување за првиот тест пример:Пример на валидно обојување е даден на сликата. Отсечките 1-2, 3-1 и 3-4 се обоени со сина боја, а сите други со црвена боја. Од точките 1, 3 и 4 има по 3 отсечки и важи дека има по најмалку една отсечка во црвена и најмалку една отсечка во сина боја. Од точката 2 има 2 отсечки: една во црвена, а друга во сина боја. Од точката 5 има една отсечка.
Да забележиме дека ова не е единствено валидно обојување.
Објаснување за вториот тест пример: Не постои валидно обојување според правилата дадени во задачата. Пример на невалидно обојување е дадено на сликата. Од точката 1 има две отсечки и нема отсечка која е обоена со црвена боја. Имено, нема начин како да се обојат отсечките 1-2 , 2-3 и 1-3 така што од секоја точка да има најмалку по една отсечка со сина и една со црвена боја.