Peaceful seating: hints, no solution

A wedding has guests numbered 0 to guests - 1 who must sit at one round table with exactly guests seats. Some pairs of guests are feuding and refuse to sit in neighbouring seats. Every seat has a left and a right neighbour, and the seats form a circle.

The list feuds holds pairs [a, b] of feuding guests; a pair may be listed twice or in both orders. Count the seatings in which no feuding pair sit next to each other. Two seatings are the same when one is a rotation of the other, so guest 0 can be treated as sitting in a fixed seat. A seating and its mirror image are counted separately, unless they are identical. With one guest there is one seating.

Examples

Input

guests = 4, feuds = [[0, 1], [2, 3]]

Output

2

Note

Guest 1 must sit opposite guest 0, and guests 2 and 3 may then take the other two seats in either order.

Input

guests = 3, feuds = [[0, 2]]

Output

0

Note

With three guests everyone sits next to everyone, so the single feud rules out every seating.

Constraints

• 1 <= guests <= 10
• 0 <= number of feuds <= 45
• Each feud names two different guests from 0 to guests - 1

Hint 1: a nudge

Why can one guest be placed first without losing any seatings, and what does that do to the number of arrangements you need to look at?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing