AlgoLiga 2018

Błędna to była droga, w jarach, w gęstwach zagubiona, trudna do przebycia. Gdy się zbliżaliśmy do murów miasta, masztalerze królewscy przystanęli nagle i jeden z nich tak do mnie przemówił:
— Okazaliśmy ci gościnność i przychylność. Nie odmówiliśmy ani pokarmu, ani noclegu, ani pomocy. Nie domyślasz się nawet, że groziło ci z naszej strony niebezpieczeństwo. Z rozkazu bowiem króla Miraża jesteśmy obowiązani zabijać każdego, ktokolwiek ośmieli się dotrzeć do brzegu wyspy, do tego miejsca, gdzie konie królewskie uczą się pląsów od Konia Morskiego. Dostęp do tego miejsca jest wzbroniony pod karą śmierci. Nikomu, prócz nas, nie wolno tam stopy swojej postawić. A i my tylko raz na rok mamy prawo jednodniowego pobytu na owym brzegu. Król Miraż w ścisłej tajemnicy zachowuje istnienie Konia Morskiego i jego cudowny wpływ na ruchy koni królewskich. Każdy z poddanych podziwia te ruchy taneczne, lecz nikt nie wie, że są one naśladowaniem pląsów Konia Morskiego i nikt się nie domyśla, że w głębinie fal, u pobrzeża tej wyspy kryje się dziwny, zielonogrzywy i zielonooki zwierz, zwany Koniem Morskim. Traf i przypadek zawieruszył cię na brzegi tej wyspy. W pierwszej chwili mieliśmy zamiar zasztyletowania ciebie, jako nieproszonego gościa i widza tajemnicy królewskiej. Lecz wzruszyło nas twoje opowiadanie i postąpiliśmy wbrew rozkazowi króla Miraża. Darowaliśmy ci życie, którego powinniśmy byli ciebie pozbawić. Czeka nas śmierć za naruszenie rozkazu królewskiego. Toteż z kolei prosimy cię o zachowanie tajemnicy naszego czynu. Nikomu nie mów o tym, co się stało. Wejdziemy teraz sami do miasta, ty zaś zatrzymaj się pod jego murami. Stój cierpliwie i czekaj, aż się oddalimy. Wówczas dopiero wejdź do miasta, jako samotny wędrownik. Gdybyś nas kiedykolwiek spotkał na ulicy, udawaj, że nas nie znasz i nie witaj nas ukłonem.
— Możecie być pewni, że spełnię waszą prośbę i że tajemnicę zachowam! — odrzekłem głosem wzruszonym i uściskałem po kolei ich dłonie silne i szerokie.

Odeszli wówczas spokojnie, pędząc przed siebie konie, które wciąż poruszały się tanecznie, opętane wspomnieniem i czarem Konia Morskiego. Stałem w miejscu cierpliwie dopóty, dopóki nie znikli mi z oczu. Upewniwszy się, że są już dość daleko, wszedłem do miasta, jako wędrownik samotny.

Widok tego miasta napełnił mnie podziwem! Bruki, cegły domów, dachy, okna — wszystko było zielone, koloru fali morskiej. Zdawało mi się, że przez szkło zielone na świat spoglądam.

Mijając ulicę za ulicą, wyszedłem na plac olbrzymi. Na placu tym zastałem tłumy ludzi. Zmieszałem się z tłumem i poprzez plecy mrowiących się ludzi spojrzałem na środek placu.

Na środku placu stał tron złoty. Na tronie siedział sam król Miraż w zielonej szacie i z zieloną buławą w ręku.

Zwróciłem się do jednego z moich sąsiadów i spytałem się, co oznacza to całe zbiegowisko dookoła tronu królewskiego?

— Jesteś zapewne cudzoziemcem — odpowiedział sąsiad — nie wiesz więc o tym, że dziś jest dzień imienin króla Miraża. W dniu tym król Miraż postanowił córkę swoją, piękną Piruzę, dać za żonę temu, kto rozwiąże jego tajemniczą zagadkę. Co rok w dniu imienin króla odbywa się ta sama uroczystość, lecz nikt dotąd zagadki rozwiązać nie potrafił. Patrz uważnie! Zaraz zjawi się piękna Piruza, aby siąść obok króla i czekać na rozwiązanie zagadki. Pała ona od dawna żądzą zamążpójścia i ma urazę do tych wszystkich rycerzy, którzy zagadki odgadnąć nie mogą. Straciła nadzieję, aby ktokolwiek kiedykolwiek i jakkolwiek zagadkę królewską rozwiązał. Toteż zazwyczaj z pogardą spogląda na tłumy, rojące się dookoła tronu.

Sąsiad mój zamilkł, a ja znowu spojrzałem na plac.

W tej chwili właśnie obok tronu złotego ustawiono drugi — srebrny i piękna Piruza zbliżyła się do srebrnego tronu. Z pogardą spojrzała na tłumy i siadła na tronie. Pogarda jej była tak wielka, że zawstydzeni rycerze spuścili oczy. Żaden z nich nie był pewien bystrości swego rozumu, chociaż każdy miał szczery zamiar rozwiązania zagadki i zawładnięcia ręką pięknej królewny.

Król Miraż wstał z tronu i, spojrzawszy po obecnych, rzekł głosem donośnym:

Dany jest graf nieskierowany o 49 wierzchołkach i 952 krawędziach. Twoim zadaniem jest pokolorowanie wierzchołków tego grafu minimalną liczbą kolorów, tak aby żadna krawędź nie łączyła wierzchołków o takim samym kolorze.

Wejście

W tym zadaniu Twoje rozwiązanie będzie testowane tylko na jednym przypadku testowym, który będzie dokładnie takim sam jak ten w przykładzie poniżej. W pierwszej linii liczba wierzchołków i krawędzi, a w kolejnych liniach wypisane krawędzie.

Wyjście

Należy wypisać ciąg 49 (oddzielonych spacjami) liczb z przedziału [1..K], gdzie K jest minimalną liczbą kolorów potrzebną do pokolorowania tego grafu. Taki ciąg ma reprezentować optymalne i poprawne kolorowanie: i-ta liczba z wyjścia oznacza kolor wierzchołka o numerze i.

Przykład

49 952
35 14
17 21
18 4
38 10
34 42
19 37
20 28
9 12
33 47
46 4
17 3
38 30
14 20
49 33
21 20
33 19
40 12
18 36
21 28
24 6
40 42
15 21
43 31
17 15
45 29
1 3
41 13
25 28
40 37
34 27
21 7
35 42
33 34
9 16
24 36
3 35
34 6
44 38
9 11
48 40
25 43
29 32
25 27
20 27
46 28
35 33
26 12
17 5
42 36
46 22
11 10
19 25
41 34
16 48
11 46
30 12
39 23
11 39
49 43
3 6
34 20
17 10
3 10
6 5
16 10
6 36
24 32
28 34
10 11
20 14
4 2
46 25
9 1
38 41
14 35
16 37
33 1
11 29
47 41
46 40
38 26
30 46
5 13
40 39
15 22
21 13
14 26
12 24
46 11
36 39
24 3
41 36
25 9
25 23
27 21
23 22
7 28
34 28
43 19
25 33
16 23
1 36
27 23
32 39
23 30
19 12
23 37
42 39
10 45
12 6
13 43
35 49
31 43
29 15
20 21
4 16
1 9
35 21
19 16
2 44
17 41
23 39
19 11
26 33
32 24
19 47
29 22
7 42
28 23
37 29
43 46
39 42
11 17
28 35
28 14
22 36
13 27
10 34
15 17
13 12
40 38
40 28
27 6
19 26
12 33
30 33
4 3
23 29
46 48
25 41
49 28
5 3
36 44
8 13
26 19
47 5
29 37
41 1
2 1
10 3
46 47
37 7
32 38
2 23
20 26
28 21
39 27
13 34
33 39
11 5
44 14
1 4
34 30
47 19
16 24
28 40
41 42
30 31
32 35
6 4
4 22
32 11
17 24
9 25
28 42
40 48
15 9
35 28
29 11
15 36
2 9
47 31
49 14
18 24
12 4
43 22
23 11
22 1
5 17
26 34
13 10
30 24
35 41
11 32
8 9
8 48
13 37
8 29
34 41
32 40
31 13
9 3
37 36
35 3
44 43
37 25
14 28
24 48
15 29
17 38
19 35
23 24
31 7
48 6
30 18
18 2
6 20
11 27
39 15
33 21
48 41
26 5
2 6
31 37
12 10
35 7
18 20
37 19
47 26
49 21
20 32
1 7
7 21
26 40
24 45
25 22
22 23
30 23
24 40
42 35
13 19
34 46
18 25
35 27
23 15
46 18
30 22
20 34
10 2
9 37
27 34
13 8
45 27
33 35
43 36
25 37
10 14
1 49
20 16
39 45
41 40
3 17
44 16
38 3
18 46
44 49
31 19
3 31
27 48
13 25
21 18
5 12
39 47
33 25
19 17
45 46
5 40
26 25
22 4
31 47
5 2
26 2
36 29
35 19
36 42
28 12
2 3
16 18
18 32
25 18
38 32
42 10
20 15
38 42
4 18
22 29
18 17
43 7
9 44
24 23
13 20
9 14
11 9
24 38
24 22
30 35
42 37
31 35
49 17
2 18
44 48
6 48
16 15
21 17
40 8
17 31
35 47
7 13
18 10
21 42
31 38
37 9
19 3
45 24
43 49
34 10
10 26
36 24
21 49
42 41
6 30
7 19
9 2
36 40
21 45
40 19
38 31
41 17
17 29
21 19
5 23
38 39
12 11
14 42
32 30
20 17
19 13
45 31
13 41
31 25
34 35
28 24
43 29
6 2
6 12
25 39
18 11
33 9
28 22
11 3
11 4
10 38
19 27
6 13
4 25
43 37
48 32
43 25
47 43
37 16
33 26
15 47
22 28
6 18
37 38
8 11
14 49
9 41
38 14
27 11
18 19
34 48
48 13
31 15
37 31
6 3
3 19
38 45
29 30
18 26
17 9
12 40
38 17
7 31
36 6
8 15
47 39
19 5
11 14
8 24
14 44
11 23
42 2
30 16
42 34
48 43
5 29
36 18
43 8
48 44
39 38
42 7
18 21
44 20
30 32
24 17
16 2
24 28
21 27
17 23
4 7
14 12
16 19
15 39
24 16
42 40
12 14
23 28
8 36
30 36
34 2
4 39
12 26
40 41
35 34
24 27
4 28
24 31
16 30
11 19
23 31
40 34
32 26
45 38
45 43
2 5
33 27
22 46
16 32
6 34
25 31
26 23
43 48
15 18
16 44
39 41
5 19
39 40
2 8
4 6
10 13
25 26
33 31
10 12
49 1
27 19
26 14
48 27
14 7
19 18
26 27
39 31
16 20
22 8
43 15
14 8
13 48
27 39
45 33
32 46
38 37
44 46
27 45
7 3
16 21
33 30
18 16
12 18
44 23
45 17
42 21
28 46
47 49
37 40
27 28
1 5
33 17
1 29
27 35
14 9
29 43
42 38
7 4
40 26
37 2
37 41
32 14
32 44
44 45
20 19
32 33
18 34
14 6
28 7
24 18
7 6
41 25
47 45
46 49
46 43
40 33
31 45
8 10
36 38
5 1
9 8
31 39
1 2
18 42
20 44
29 35
29 33
14 13
10 17
13 5
22 43
39 32
8 43
30 34
49 45
42 14
12 28
25 11
32 4
34 13
3 24
3 7
36 41
39 25
36 12
47 33
19 43
5 4
40 46
40 36
39 37
14 21
47 44
13 14
23 17
2 26
36 15
30 38
4 32
26 10
1 33
43 45
4 12
3 11
49 47
32 25
29 23
41 6
38 40
19 31
49 42
4 20
24 8
44 37
26 28
15 20
48 46
1 6
16 4
20 13
7 43
8 16
11 25
27 13
28 4
17 19
37 30
28 20
40 32
1 8
43 47
34 31
39 18
40 5
21 5
33 5
15 3
37 23
37 13
3 15
22 25
31 29
39 11
11 35
6 14
2 34
44 9
8 12
10 22
40 24
20 6
10 8
42 18
22 24
17 49
36 1
48 8
2 10
46 38
41 27
33 49
16 9
31 32
45 49
19 20
9 23
10 9
19 7
3 38
27 24
22 26
9 10
31 23
48 16
21 16
41 48
32 16
24 10
38 24
26 47
23 25
30 2
8 14
9 33
48 49
12 20
17 20
10 31
18 39
6 27
15 1
17 11
29 31
30 37
45 47
26 18
2 42
8 1
46 44
15 19
31 34
29 1
41 9
22 30
17 45
25 1
44 36
41 35
27 20
48 34
16 22
34 18
40 47
33 41
4 10
41 38
7 49
36 37
34 40
42 49
1 22
36 43
20 12
17 1
49 44
3 9
9 13
25 7
12 19
34 29
2 16
23 5
23 9
41 20
29 8
23 16
36 22
15 23
38 20
5 47
15 16
26 20
39 4
7 25
1 17
11 12
13 21
6 7
29 36
23 44
26 38
45 48
2 4
47 15
10 24
25 4
11 13
9 49
8 40
32 29
12 9
32 20
32 8
2 37
7 2
32 18
33 32
35 11
26 22
48 45
8 32
34 26
12 36
41 33
25 49
13 11
24 30
28 26
23 47
17 16
25 19
40 16
15 31
49 7
31 17
20 4
18 30
49 9
25 32
37 43
12 30
22 38
4 1
29 45
25 13
9 30
48 20
45 37
3 1
24 25
8 22
47 40
32 31
45 39
39 46
5 21
4 46
30 9
49 41
46 39
42 28
10 18
18 6
19 15
7 37
44 47
33 12
22 27
31 30
44 26
14 32
27 26
8 2
35 31
19 33
17 25
30 29
22 15
49 35
20 48
28 49
29 34
43 1
1 25
37 44
13 31
42 26
45 10
19 21
20 18
33 29
31 10
21 39
43 13
4 11
46 32
31 3
42 48
33 40
5 6
46 45
14 38
1 15
12 13
7 35
33 45
48 47
12 5
44 2
23 27
13 6
48 24
26 24
47 48
38 46
41 37
43 44
14 10
21 14
32 34
18 12
25 24
11 18
46 34
5 11
30 44
20 38
41 47
20 41
13 9
12 47
37 42
31 24
47 46
25 17
24 26
10 4
47 35
4 5
27 33
34 33
18 15
29 17
11 8
2 30
21 35
12 8
34 32
44 32
10 16
16 17
38 36
35 29
15 43
45 44
6 1
5 7
23 26
49 48
38 22
9 17
3 4
10 42
27 25
28 27
41 49
39 33
17 33
9 15
27 41
16 40
27 3
36 30
15 8
7 1
46 30
39 36
3 2
2 7
24 12
49 25
32 48
49 46
27 22
36 8
35 32
13 7
5 26
30 6
1 41
37 45
47 12
28 25
26 42
14 11
26 44
16 8
3 5
47 23
6 41
17 18
1 43
21 33
5 33
38 44
41 39
48 42
23 2
22 10
39 21
22 16
7 14
35 30
19 40
44 30
7 5
45 3
6 24
26 32
3 45
37 39
31 33
21 15
45 21
25 46
29 5
3 27