## DMOPC '15 Contest 3 P3 - Dimethylbenzene

View as PDF

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 , and has given you distinct pairs of the form , representing a bond between atoms and .

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

#### Input Specification

The first line of input will contain two space-separated integers and .
The next lines will contain two integers and , defining a 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: .

#### 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

• commented on Dec. 22, 2017, 1: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

• commented on Dec. 31, 2015, 11:48 p.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?

• commented on Feb. 25, 2016, 7:33 p.m.

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

• commented on Dec. 31, 2015, 11:57 p.m.

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

• commented on Dec. 8, 2015, 12:28 p.m.

Cycle means simple cycle)