Dana jest graf nieskierowany $G$. Oblicz, ile jest w nim cykli o długości $k$.
Wejście
W pierwszej linii znajdują się dwie liczby całkowite dodatnie $n$ oraz $k$, oznaczające liczbę wierzchołków w grafie oraz długość szukanych cykli.
Następnie w $n$ liniach podana jest macierz sąsiedztwa grafu, gdzie $A_{ij} = 1$ oznacza istnienie krawędzi $(i,j)$. Gwarantuje się, że graf nie posiada pętli własnych i jest nieskierowany.
Wyjście
Wypisz jedną liczbę oznaczającą liczbę cykli.
Przykład
Wejście 1
6 3 001110 001011 110011 100010 111100 011000
Wyjście 1
4
Wejście 2
6 4 001110 001011 110011 100010 111100 011000
Wyjście 2
3
Wejście 3
6 5 001110 001011 110011 100010 111100 011000
Wyjście 3
2
Wejście 4
6 6 001110 001011 110011 100010 111100 011000
Wyjście 4
1
Wejście 5
10 3 0100011001 1010101100 0101001101 0010101001 0101011000 1000100101 1111100100 0110011010 0000000101 1011010010
Wyjście 5
10
Wejście 6
10 4 0100011001 1010101100 0101001101 0010101001 0101011000 1000100101 1111100100 0110011010 0000000101 1011010010
Wyjście 6
27
Wejście 7
10 5 0100011001 1010101100 0101001101 0010101001 0101011000 1000100101 1111100100 0110011010 0000000101 1011010010
Wyjście 7
66
Wejście 8
10 6 0100011001 1010101100 0101001101 0010101001 0101011000 1000100101 1111100100 0110011010 0000000101 1011010010
Wyjście 8
123
Wejście 9
20 4 01111001011011011110 10101010100001000100 11011101010010111110 10101110110010000010 11110010001101111111 00110001000100100100 01011001111011011110 10100110110011011001 01010011000011001110 10110011001110100111 10001010010011111000 00001100010010110001 10110011111100111100 11001011101000010101 00101100011110011100 10101011001111100000 10101011101010100101 11101110110011101010 10111010110000000100 00001001010101001000
Wyjście 9
1267
Uwagi
Przykłady 1–4 oraz 5–8 pokazują wyniki dla różnych wartości $k$ przy tym samym grafie wejściowym.
Podzadania
- Dla $20\%$ punktów gwarantuje się, że $n\leq 10$.
- Dla kolejnych $10\%$ punktów gwarantuje się, że $k=3$.
- Dla kolejnych $20\%$ punktów gwarantuje się, że $k=4$.
- Dla kolejnych $30\%$ punktów gwarantuje się, że $k=5$.
- Dla $100\%$ punktów gwarantuje się, że $1\leq n\leq 300$ oraz $k\leq 6$.
Wskazówki
Pamiętaj, że cykl o długości $k$ w grafie nieskierowanym jest liczony jako ten sam zbiór krawędzi niezależnie od punktu startowego oraz kierunku przejścia. Warto rozważyć, czy Twoje podejście nie zlicza wielokrotnie tych samych cykli.