DMOPC '15 Contest 3 P3 - Dimethylbenzene

View as PDF
Submit solution
Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M
Author:
Xyene
Problem types

Xyene really likes the organic compound xylene, also known as dimethylbenzene. He has received an organic molecule as a present, and would like to know if there exists a dimethylbenzene somewhere in it.

However, organic chemistry is a struggle for Xyene, so he'll settle for knowing whether or not his molecule contains six carbons atoms arranged in a ring, or cycle. There may be multiple cycles in Xyene's present, but he's only interested in finding out if there is at least one that is six atoms long.

Xyene has numbered the carbon atoms in his present from 1 \dots N, and has given you M distinct pairs of the form (u, v), representing a bond between atoms u and v.

Does his present contain at least one cycle of length six?

Input Specification

The first line of input will contain two space-separated integers N (2 \le N \le 20) and M (1 \le M \le 20).
The next M lines will contain two integers u and v, defining a u \longleftrightarrow v bond.

Output Specification

YES if the given molecule contains a cycle that is six carbon atoms long, NO otherwise.

Sample Input 1

6 6
1 2
2 3
3 4
4 5
5 6
6 1

Sample Output 1

YES

Explanation for Sample 1

This is a ring of six carbons: 1 \longleftrightarrow 2 \longleftrightarrow 3 \longleftrightarrow 4 \longleftrightarrow 5 \longleftrightarrow 6 \longleftrightarrow 1.

Sample Input 2

3 3
1 2
2 3
3 1

Sample Output 2

NO

Explanation for Sample 2

Though this may be a cycle, it is only of length three.

Sample Input 3

2 1
1 2

Sample Output 3

NO

Explanation of Sample 3

This is not a cycle!

Sample Input 4

8 8
1 2
2 3
3 4
4 5
5 6
6 1
6 7
7 8

Sample Output 4

YES

Sample Input 5

8 9
1 2
2 3
3 4
4 5
5 6
6 1
6 7
7 8
8 1

Sample Output 5

YES

Comments


  • 2
    Jerry_Gu  commented on Dec. 22, 2017, 6:14 p.m.

    can there be lines in between the circles? what would this output: 6 7 1 2 2 3 3 4 4 5 5 6 6 1 1 4


  • 0
    Haxxx0r  commented on Jan. 1, 2016, 4:48 a.m.

    I noticed that the ladderane structure is possible, but I'm confused on whether a ladderane contains a 'simple cycle' of length 6.

    Example Case:

    8 10
1 2
2 3
3 4
4 1
3 5
5 6
6 4
5 7
7 8
8 6

    What is the proper answer? Do the AC submissions disagree over this?


    • 0
      Sagnik  commented on Feb. 26, 2016, 12:33 a.m.

      aren't the carbon atoms supposed to be placed in increasing order?


    • 0
      r3mark  commented on Jan. 1, 2016, 4:57 a.m.

      1 2, 2 3, 3 5, 5 6, 6 4, and 4 1 gives a simple cycle of length 6.


  • 0
    FatalEagle  commented on Dec. 8, 2015, 5:28 p.m.

    Cycle means simple cycle)