Problem
Na cidade de N, em circunstâncias pouco claras, o território de uma das fábricas se transformou em uma zona anômala. Todas as entradas do território foram bloqueadas e ela própria foi chamada de zona industrial. Existem
N edifícios na zona industrial, alguns deles ligados por estradas. Qualquer estrada pode ser percorrida em ambas as direções.
O perseguidor novato recebeu a tarefa de chegar ao depósito na zona industrial. Ele encontrou vários mapas do território da zona industrial no arquivo eletrônico. Como os mapas foram compilados por pessoas diferentes, cada um deles contém informações apenas sobre algumas estradas da zona industrial. A mesma estrada pode aparecer em vários mapas.
No caminho, o perseguidor pode baixar um cartão do arquivo para o celular. Quando você baixa um novo mapa, o anterior não é armazenado na memória do telefone. O perseguidor só pode se mover pelas estradas marcadas no mapa carregado no momento. Cada download de mapa custa 1 rublo. Para minimizar os custos, o perseguidor precisa escolher essa rota para baixar os mapas o menor número de vezes possível. Stalker pode baixar o mesmo mapa várias vezes, e você terá que pagar por cada download. Inicialmente, não há cartão na memória do celular.
É necessário escrever um programa que calcule o valor mínimo de gastos necessários para um stalker ir da entrada da zona industrial até o depósito.
Entrada:
- a primeira linha da entrada contém dois números naturais
N e
K (
\(2 <= N <= 2000 \ );
\(1 <= K <= 2000\)) — o número de edifícios da zona industrial e o número de mapas, respectivamente. A entrada para a zona industrial situa-se no edifício com o número
1, e o armazém — no edifício número
N.
- nas linhas seguintes há informações sobre os cartões disponíveis. A primeira linha da descrição do cartão
i contém o número
ri — número de estradas marcadas no mapa
i-th;
- então vêm
ri strings contendo dois números naturais
a e
b (
\(1 <= a\),
\(b <= N\);
\(a ? b\)), o que significa que há uma estrada no mapa
i-th conectando os edifícios
a e
b< /código>. O número total de estradas marcadas em todos os mapas não excede 300.000 (\(r_1 + r_2 + … + r_K <= 300.000\)).
Resultado: imprima um único número — o valor mínimo das despesas do perseguidor. Se for impossível chegar ao armazém, imprima o número –1.
Exemplos
| # |
Entrada |
Saída |
| 1 |
12 4
4
16
24
79
10 12
3
14
7 11
36
3
25
4 11
8 9
5
3 10
10 7
7 2
12 3
5 12 |
3 |