HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Graph problems and UF > problem:


50414 - Traffic

Guest
• Review clarifications (1)

Section problems

• 50261 - Roads
• 50690 - Parliament
• 50700 - Candidates for the Mayor
• 50692 - How much money?
• 50694 - The Cheapest Flight
• 50841 - My grand-grand-grandfather
• 50697 - Base Stations
• 50695 - Longest link between neurons
• 50414 - Traffic
• 50698 - Ayran Delivery
• 50978 - Albanian Coders
• 50699 - Fighting Vampires
• 50857 - Nine-Stones Game
• 50929 - Present from your uncles
• 51076 - Key person
• 51080 - Deepest Point
• 51079 - Key person - 2

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.
Question by Osman Ay.

Traffic

Question: The heavy traffic is one of the major problems of big cities. The city municipalities try to find different solutions for this problem. The solution of the Tirana municipality is to make all the roads in the city only in one direction. So that, no two cars will block a narrow road. The only issue of this solution is that if it is possible to reach from any point of the city to any other point after the transformation. Make a program that reads the current undirected road connections of the city and determines if it is possible to convert all the roads to directed roads and still possible to travel between any two places.

Input specification
The first line of the test case contains two integers C (1 < C ≤ 30000) and R (1 ≤ R ≤ 100000) where C is the number of the road conjunctions and R is the number of the roads in the city. There are no parallel roads and no road connects a junction to itself. Each of the following R lines determines a road with two integers. Those integers represent numbers of two conjunctions connected with the road. The conjunctions are numbered from 1 to C.

Output specification
The output contains a single word "YES" or "NO".

 Sample Input I   
 4 5
 1 2
 4 3
 2 4
 4 1
 2 3
 Sample Input II  
 3 3
 1 3
 2 1
 3 1
 Sample Output I  
 YES
 Sample Output II  
 NO


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

www.contester.ru