### PROBLEM LINK

**Author:** Hanlin Ren

**Tester:** Jakub Safin

**Editorialist:** Jakub Safin

### DIFFICULTY

SIMPLE

### PREREQUISITIES

none

### PROBLEM

Given the sequence of numbers on the top face of a die rolled 90^\circ at a time, find one possible configuration of numbers on the faces of the die or determine that it doesn’t exist.

### QUICK EXPLANATION

Bruteforce all possible answers, check if no step corresponds to rotation to the same face or the opposite face.

### EXPLANATION

This problem can be misleading, since it may seem at first that the orientation of the die matters. Actually, it doesn’t, since if the number on the top of the die is x and the number on the bottom face is y, then it’s possible to get any of the remaining 4 numbers can be on top after exactly one step; of course, it’s impossible to get y on top after one step and we can’t keep x on top either.

We don’t actually know the pairs of numbers on opposite faces, but there aren’t many choices, so we can bruteforce them - pick three unordered pairs and ensure they contain each number 1 through 6 exactly once. There are only \frac{1}{3!}\frac{6\cdot5}{2}\frac{4\cdot3}{2}\frac{2\cdot1}{2}=15 such triples of disjoint pairs.

Therefore, all we need to do is try all possible configurations of numbers on the die and for each of them, check if the conditions A_i eq A_{i+1}, A_i eq o(A_{i+1}) hold for all 1 \le i < N. We actually found all possible configurations this way, not just one.

There are O(1) configurations, so the time complexity is O(N), same with memory complexity. We can improve this to O(1) memory either by checking which configurations satisfy the constraints as we read the input, or by remembering only how many times each pair (A_i,A_{i+1}) appeared.