Cat and Mouse: Catching Strategy on Graphs

In this problem, you are given an undirected, unweighted graph with ( n ) nodes and ( m ) edges. A cat starts at node ( s ) while a mouse starts at node ( t ). The mouse moves only every ( k ) time units (if ( k = 0 ), it stays stationary), while the cat moves one edge per time unit following the shortest path from ( s ) to ( t ).

Your task is to determine whether the cat can catch the mouse. More formally, let ( d ) be the shortest distance from ( s ) to ( t ). If ( k = 0 ), then the cat always catches the mouse (provided that ( t ) is reachable). Otherwise, if the condition $$d \mod k = 0$$ holds, then the mouse escapes; otherwise, the cat catches the mouse.

If there is no path from ( s ) to ( t ), then the cat cannot catch the mouse.

inputFormat

The input is provided via standard input (stdin) in the following format:

( n \ m \ k \ s \ t ) (all integers) on the first line, where ( n ) is the number of nodes, ( m ) the number of edges, ( k ) the time interval for the mouse's movement, ( s ) the starting node of the cat, and ( t ) the starting node of the mouse.

Then follow ( m ) lines, each containing two integers ( u ) and ( v ) representing an undirected edge between nodes ( u ) and ( v ).

outputFormat

Output a single line to standard output (stdout) containing either "Yes" if the cat can catch the mouse, or "No" otherwise.## sample

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

Yes