C Programming Language ( Code With C Programming Language)

Problem Title : Star Train

As the mayor of Jolibi city, you need to improve the local transportation system. One way you could do that is to construct a train route. Jolibi city has N districts, and each district has exactly one train station. You plan to construct M paths so that the final route has a star shape. That is, there exists a permutation p such that there is a path from district p₁ to p₂, from district p₁ to p₃, ....., and from district p₁ to p_n with no other paths.

You are a really busy mayor, so you asks Jojo as your personal assistant to construct the M routes for you. You need to determine whether the routes constructed by Jojo has a star shape!

Format Input

The first line consists of two integers N and M, the number of districts and the number of paths. The next M lines each consists of two integers U_i and V_i which means that there is a path from district U_i to district V_i. Note that the path is bidirectional which means that for a given path (U_i, V_i) it is possible to travel from district U_i to district V_i and vice versa.

Format Output

Output YES if the given route has a star shape or NO if it is not.

Constraints

• 3 N 100
• 0 M N (N 1)/2
• U_i V_i
• It is guaranteed that there will be no duplicate path in the input. The path (u, v) and (v, u) are considered as the same path.

Sample Input & Output 1 (Standard Input & Output)

4 3 3 1 2 3 4 3 YES

Sample Input & Output 2 (Standard Input & Output)

4 2 3 1 2 3 NO

Explanation

On the first sample, one of the valid star shape sequence is as follows : (3, 1, 4, 2)