Bamboo Forest of the Lost - MarisaOJ: Marisa Online Judge

Marisa and Reimu have lost each other in the Bamboo Forest of the Lost. The forest can be represented as a undirected graph of

n

$n$ vertices and

m

$m$ edges. Marisa is currently at vertex

a

$a$ , and Reimu is currently at vertex

b

$b$ . Every

1

$1$ unit of time, Marisa and Reimu move to any adjacent vertex (they will not stand still, as they are in a hurry now). Find the earliest time when they will meet each other again. ### Input - The first line contains 2 integers

n, m

$n, m$ . - The second line contains 2 integers

a, b

$a, b$ . - The next

m

$m$ lines, each line contains 2 integers

u, v

$u, v$ , there is an edge between

u

$u$ and

v

$v$ . ### Output - Print the earliest time when they will meet each other again. Or print

- 1

$-1$ if they get lost forever... ### Constraints -

1 \leq n, m \leq 10^{5}

$1 \le n, m \le 10^5$ . -

1 \leq u, v, a, b \leq n

$1 \le u, v,a, b \le n$ . ### Example Input:

6616122334246554

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

Output:

2

$2$

#### **Note**: Marisa and Reimu will meet each other at

4

$4$ .

BFS / DFS
	Connected component
	Shortest path
	Finding the path
	Path on binary matrix
	Garden
	Operations on number
	Bipartite graph
	Tom and Jerry
	Festival 1
	Bamboo Forest of the Lost
	Radar
	Festival 2
	Go
	Escape from... dolls
	Long leg
	Lexicographically smallest path
	Graph coloring

Topic

Graph

Shortest path

Rating

1200

Solution (1)

Solution