HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Graph problems and UF > problem:


50704 - Connected?

Guest
• Review clarifications (1)

Section problems

• 50929 - Present from your uncles
• 51076 - Key person
• 51080 - Deepest Point
• 51079 - Key person - 2
• 50464 - From Tirana to Durres
• 50691 - The traveling salesman prob...
• 50701 - Cell Removal
• 50703 - The Shortest Path
• 50704 - Connected?
• 50705 - Student Clubs

Feedback

If you notice incorrect translations in Contester, please let author know.

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

Для отправки решений необходимо выполнить вход.

www.contester.ru