UVa 11396

From Algorithmist
Jump to: navigation, search

Problem Number - Problem Name

Summary

Read the problem 2 to 3 times unless you understand that that it is a problem related to bipartite graph. Hint: try to imagine center node of claw to be of one color and remaining three of the other.

Explanation

Now all that is left to check is whether or not it is a bipartite graph. If it is print "YES" otherwise "NO".

Gotchas

  • Do not check for the conditions such as (number of vertices)%3==0
  • There is a blank line in between any two lines of input.

Implementations

Input

4

1 2

1 3

1 4

2 3

2 4

3 4

0 0

6

1 2

1 3

1 6

2 3

2 5

3 4

4 5

4 6

5 6

0 0

5

1 2

1 4

1 3

1 5

0 0

4

1 2

1 4

1 3

0 0

0

Output

NO
NO
YES
YES