Caminho Par
Time limit: 2000 msMemory limit: 256 MB
Dado um grafo simples com vértices e arestas, determine mínimo de arestas em um caminho do vértice até o vértice que usa um número par de arestas. É possível usar os mesmos vértices e as mesmas arestas múltiplas vezes se necessário.
Por exemplo, o caminho: seria um caminho permitido de a , pois ele possui um número par de arestas.
Input
A primeira linha contém dois inteiros e (, ).
Output
Imprima um inteiro: o número mínimo par de travessias de arestas necessário para ir do vértice ao vértice , ou se tal rota não existir.
Samples
Sample 1
Input
3 3 1 3 1 2 2 3
Output
2
A rota usa arestas. A aresta direta de para usa um número ímpar de arestas, portanto não é válida.
Sample 2
Input
2 1 1 2
Output
-1
Toda rota do vértice ao vértice usa um número ímpar de arestas, portanto a resposta é .