Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Prepared by Ibrahim Mesecan.
Connected?
Shqip
In an undirected graph G, two vertices u and v are called connected if G contains a path from u to v. Otherwise, they are called
disconnected. If the two vertices are additionally connected by a path of length 1, i.e. by a single edge, the vertices are
called adjacent. A graph is said to be connected if every pair of vertices in the graph is connected.
In the figure left, we have an undirected graph with 3 vertices and one edge; between the vertices 2 and 5.
When the graph is undirected, then, having a path from u to v, means that there is also a path from v to u. Thus, we have a path
from 2 to 5 means that we also have a path from 5 to 2. But there is no path from 1 to any other.
Write a program that will read the number of vertices and the edge configuration from the input. And then,
for an undirected graph, it will decide if there is path between two given vertices.
Input specification
The first line will contain two numbers n (2 ≤ n ≤ 20 ) and e (1 ≤ e ≤ 400 ),
where n is the number of vertices and e is the number of edges.
The following e lines contain two numbers u and v where 1 ≤ u, v ≤ n. And, u is the source vertex, v is the destination vertex.
That means u is adjacent to v (There is an edge from u to v).
In the last line, there will be two numbers a and b (1 ≤ a, b ≤ n ), which represent the source and destionation for
which you are asked to decide whether there exists a path or not.
Output specification
You give a single line containing either the word "YES", if there is a path from a and b, or "NO".
Sample input I
4 3
4 2
1 3
3 4
1 2
| |
Sample output I
YES
Sample input II
4 4
1 3
1 4
3 4
2 1
3 2
|
|
Sample output II
YES
Для отправки решений необходимо выполнить вход.
|