Problems

# Shortest even path

# Shortest even path

Undirected unweighted graph is given. Find the shortest path between two vertices of even length.

#### Input

First line contains four integers: number of vertices **n**, number of edges **m** (**n**, **m** ≤ `10`

), source ^{5}**s** and destination **d** (**1** ≤ **s**, **d** ≤ **n**). Each of the next **m** lines contains two integers **a** and **b** describing an undirected edge (**a**, **b**).

#### Output

Print the shortest distance from **s** to **d**. The length of the path (number of edges in the path) must be even. If there is no path of even length between **s** and **d**, print **-1**.

Input example #1

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

Output example #1

6

Input example #2

6 5 1 6 1 2 2 3 3 4 4 5 5 6

Output example #2

-1