## TLE '16 Contest 4 P3 - Cubes

View as PDF

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 distinct corners of the frame (vertices), labelled from to . Jason is also given distinct beams. The beam can only connect corners and . 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 .

lines of input follow. The line contains the integers and . No pair 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

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

What does being able to build the table mean?

• 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.