ThunderClan owns a vast, forested territory, made up of ~n~ numbered trees and ~m~ paths connecting them. Two wild cats, Firestar and Greystripe, need to meet up with each other to share their plans in the war against ShadowClan.

Each cat starts at some tree. Every minute, they must both move to another tree, since they're in such a hurry. However, because Firestar and Greystripe are best friends, after each move they must be at the same type of tree.

Are the cats able to visit the same tree at the same time? If so, how quickly can this happen?

Input

The first line contains two integers, ~n~ and ~m~ (~1 \leq n \leq 100~, ~1 \leq m \leq n(n-1)/2~), the number of trees in the forest, the number of paths connecting them.

The next line contains two integers, ~f~ and ~g~ (~1 \leq f, g \leq n~, ~f \neq g~), the tree numbers that Firestar and Greystripe start at, respectively.

The next ~n~ lines contain strings, ~s_1 \dots s_n~, (~1 \leq |s_i| \leq 10~), where line ~s_i~ contains the type of tree ~i~. Each tree type contains only lowercase English characters.

The next ~m~ lines contain two integers, ~a~ and ~b~ (~1 \leq a, b \leq n~, ~a \neq b~), indicating that trees ~a~ and ~b~ are connected by a bidirectional path. There are no duplicate paths or self-loops.

The cats are guaranteed to start on two trees of the same type.

Output

Output the minimum time (moves) required for Firestar and Greystripe to meet. If this is not possible, output -1.

Example

Input 1

6 6
1 6
baobab
umbrella
commiphora
baobab
commiphora
baobab
1 2
1 3
2 4
3 5
4 5
5 6

Output 1

3

The cats require 3 minutes (moves) to meet.

• Move 1: Firestar moves to tree 3, Greystripe moves to tree 5.
• Move 2: Firestar moves to tree 1, Greystripe moves to tree 4.
• Move 3: Both cats move to tree 2.

Input 2

9 8
1 9
baobab
commiphora
umbrella
commiphora
umbrella
baobab
umbrella
commiphora
baobab
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9

Output 2

5

The cats require 5 minutes (moves) to meet.

• Move 1: Firestar moves to tree 2, Greystripe moves to tree 8.
• Move 2: Firestar moves to tree 3, Greystripe moves to tree 7.
• Move 3: Firestar moves to tree 4, Greystripe moves to tree 8.
• Move 4: Firestar moves to tree 5, Greystripe moves to tree 7.
• Move 5: Both cats move to tree 6.

Input 3

7 8
7 3
fig
fig
fever
fever
whistling
whistling
fever
1 2
2 3
3 4
4 5
5 6
6 7
7 1
1 5

Output 3

-1