TLE '16 Contest 4 P3 - Cubes

View as PDF

Submit solution


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

Author:
Problem types
Glasbord from Ikea. Note the very fashionable cubic frame.

Jason recently bought a frame from Ikea. After assembling this cubic frame, Jason will place a large piece of glass on top of the frame, forming a table for his friends to eat at during an upcoming Christmas party.

According to the Ikea instructions, there are 8 distinct corners of the frame (vertices), labelled from 1 to 8. Jason is also given N distinct beams. The i^\text{th} beam can only connect corners u_i and v_i. Jason is allowed to choose any beam to include in the frame and he can place the corners in any position in 3-D space. Can Jason build the cubic frame?

Input Specification

The first line contains the integer N (0 \le N \le 28).

N lines of input follow. The i^\text{th} line contains the integers u_i and v_i (u_i < v_i). No pair (u_i, v_i) appears twice in the input.

Output Specification

Output Ja if it is possible for Jason to build a cubic frame. Otherwise, output Nej.

Sample Input 1

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

Sample Output 1

Ja

Sample Input 2

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

Sample Output 2

Nej

Comments


  • 0
    sunnylancoder  commented on Dec. 24, 2016, 10:53 a.m. edited

    What does being able to build the table mean?


    • 2
      d  commented on Dec. 24, 2016, 11:17 a.m. edited

      "Building" means choosing the locations of the 8 corners, and picking some beams to connect these corners.

      It is possible to build a cubic frame if a cube structure can be created.