Contest problemset description

Andrzej ma permutację. A dokładniej to miał, bo żartowniś Jasio zmazał mu spacje pomiędzy liczbami. Pomóż Andrzejowi odtworzyć permutację.

Napisz program, który: wczyta permutację bez spacji, wyznaczy gdzie powinny pojawić się spacje i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (i jedynym) wierszu wejścia znajduje się ciąg cyfr – permutacja Andrzeja bez spacji.

Wyjście

W pierwszym (i jedynym) wierszu wyjścia powinna się znaleźć permutacja Andrzeja ze spacjami (pojedynczymi odstępami). Jeśli istnieje wiele rozwiązań, wypisz dowolne z nich.

Ograniczenia

Długość ciągu wejściowego nie przekracza 256 znaków.

Przykład

4111109876532

4 1 11 10 9 8 7 6 5 3 2 

Dany jest graf nieskierowany. Wypisz jego reprezentację listową.

Wejście

W pierwszym wierszu dane są dwie liczby: N, M, gdzie N oznacza liczbę wierzchołków zaś M – liczbę krawędzi. W następnych M wierszach podane są po dwie liczby: A, B oznaczające krawędź między wierzchołkami A i B.

Wyjście

W i-tym wierszu należy wypisać najpierw “i:”, a dalej numery wierzchołków połączonych krawędzią z i-tym wierzchołkiem. Numery wierzchołków należy podać w porządku rosnącym, oddzielając je pojedynczą spacją.

Ograniczenia

1 ≤ N ≤ 10⁵, 0 ≤ M ≤ 10⁵, 1 ≤ A, B ≤ N.

Przykład

9 10
2 4
7 2
6 1
9 1
1 4
6 9
6 7
8 5
5 6
2 3

1: 4 6 9 
2: 3 4 7 
3: 2 
4: 1 2 
5: 6 8 
6: 1 5 7 9 
7: 2 6 
8: 5 
9: 1 6 

Dany jest graf nieskierowany. Wypisz jego reprezentację macierzową.

Wejście

W pierwszym wierszu dane są dwie liczby: N, M, gdzie N oznacza liczbę wierzchołków zaś M – liczbę krawędzi. W następnych M wierszach podane są po dwie liczby: A, B oznaczające krawędź między wierzchołkami A i B.

Wyjście

W N wierszach powinno znaleźć się N liczb oddzielonych spacjami – macierz sąsiedztwa danego grafu. W macierzy tej na pozycji i, j powinna znaleźć się 1, jeśli istnieje krawędź między wierzchołkami i oraz j. W przeciwnym wypadku należy wypisać 0.

Ograniczenia

1 ≤ N ≤ 10³, 0 ≤ M ≤ 10⁵, 1 ≤ A, B ≤ N.

Przykład

9 10
2 4
7 2
6 1
9 1
1 4
6 9
6 7
8 5
5 6
2 3

0 0 0 1 0 1 0 0 1 
0 0 1 1 0 0 1 0 0 
0 1 0 0 0 0 0 0 0 
1 1 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 1 0 
1 0 0 0 1 0 1 0 1 
0 1 0 0 0 1 0 0 0 
0 0 0 0 1 0 0 0 0 
1 0 0 0 0 1 0 0 0 

Paul Erdos był jednym z najwybitniejszych matematyków XX w. Był znany nie tylko ze swoich niesamowitych zdolności do rozwiązywania problemów matematycznych, ale także ze swojego specyficznego stylu bycia i poczucia humoru. Jednym z żartów Erdosa, który utrwalił się jako stały element ,,matematycznego folkloru’’ jest tzw. liczba Erdosa.

Definiujemy ją w następujący sposób: Erdos w swojej własnej osobie ma liczbę Erdosa równą 0. Następnie wszyscy Ci, którzy kiedykolwiek napisali z nim jakąś pracę mają liczbę Erdosa równą 1. Wszyscy Ci, którzy napisali z nimi pracę, ale nie napisali pracy z Erdosem, mają liczbę Erdosa równą 2, itd. Jeśli zdarzy się tak, że dany matematyk nie napisał pracy ani z Erdosem, ani z nikim, komu można przypisać pewną dodatnią liczbę Erdosa, to przyjmujemy, że jego liczba Erdosa wynosi  − 1. Można powiedzieć, że w ten sposób definiujemy odległość od Erdosa do innych naukowców.

No dobrze, historyjka ładna, ale pewnie chciałbyś już coś zaimplementować (w końcu po coś jest ten Solve). W takim razie napisz program, który dostając listę prac napisanych przez matematyków, dla każdego z nich obliczy jaka jest jego liczba Erdosa.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby naturalne: N, M oraz E pooddzielane pojedynczymi odstępami i określające odpowiednio: liczbę rozpatrywanych matematyków oraz liczbę napisanych prac oraz numer matematyka, który jest Erdosem (wszystkich rozpatrywanych matematyków numerujemy od 1 do N). W kolejnych M wierszach znajduje się opis napisanych prac. W i-tym wierszu znajdują się dwie liczby całkowite A_i i B_i, oddzielone pojedynczym odstępem, oznaczające, że matematyk o numerze A_i napisał pracę wspólnie z matematykiem B_i. Żadna para podana na wejściu nie powtarza się, matematyk nie może również napisać pracy sam ze sobą.

Wyjście

Twój program powinien wypisać dokładnie N linii. W i-tej linii wyjścia powinna znaleźć się liczba Erdosa i-tego matematyka.

Ograniczenia

1 ≤ N ≤ 1 000 000, 1 ≤ M ≤ 1 000 000, 1 ≤ A_i, B_i ≤ N.

W testach wartych łącznie 50% maksymalnej punktacji: N, M ≤ 1000.

Przykład

4 3 2
1 2
2 3
3 1

1
0
1
-1

Zadanie jest krótkie. Masz dany graf nieskierowany o N wierzchołkach i M krawędziach. Policz ile ma spójnych składowych.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne: N, M pooddzielane pojedynczymi odstępami i określające odpowiednio: liczbę wierzchołków i liczbę krawędzi rozpatrywanego grafu. W kolejnych M wierszach znajduje się opis krawędzi grafu. W i-tym wierszu znajdują się dwie liczby całkowite A_i i B_i, oddzielone pojedynczym odstępem, oznaczające, że wierzchołek A_i jest połączony krawędzią z wierzchołkiem B_i. Wszystkie krawędzie w grafie są nieskierowane, wierzchołki numerujemy od 1 do N. Żadna krawędź podana na wejściu nie powtarza się, w grafie nie ma też pętli.

Wyjście

W pierwszej i jedynej linii standardowego wyjścia powinna pojawić się jedna liczba całkowita oznaczająca liczbę spójnych składowych rozpatrywanego grafu.

Ograniczenia

1 ≤ N ≤ 1 000 000, 1 ≤ M ≤ 1 000 000, 1 ≤ A_i, B_i ≤ N. W testach wartych łącznie 50% maksymalnej punktacji: N, M ≤ 1000.

Przykład

4 2
1 2
3 4

2

Dla danego opisu labiryntu odpowiedz, czy istnieje droga do wyjścia, gdzie cyfra 1 oznacza przeszkodę, 0 dowzolone pole, a cyfra 2 oznacza wyjście z labiryntu, czyli nasz cel.

Startujemy zawsze w lewym górnym rogu, możemy poruszać się jedynie do góry, w prawo, lewo i w dół i nie możemy wejść na pole przeszkody lub wyjść poza labirynt.

Wejście

W pierwszej linii wejścia dane są W i K, oznaczające odpowiednio liczbę wierszy i liczbę kolumn kolumn labiryntu. W kolejnych W wierszach dane jest po K liczb pooddzielanych spacjami opisujących labirynt.

Wyjście

Wypisz TAK jeśli istnieje wyście z labiryntu, albo NIE w przeciwym przypadku.

Ograniczenia

1 ≤ W, K ≤ 100

Przykład

3 11
0 0 0 1 0 0 1 1 0 0 0 
0 0 0 1 0 0 0 0 0 1 0 
0 0 0 0 0 0 1 0 0 0 2 

TAK