Secret gift assignments: hints, no solution

At a gift exchange every guest brings one wrapped gift and takes home exactly one gift that someone else brought. Guests are numbered 0 to guests - 1. Nobody may take their own gift, and every gift is taken by exactly one guest. Some guests also refuse particular gifts: each pair [g, h] in banned means guest g must not receive the gift brought by guest h.

Return every valid assignment. An assignment is a list whose i-th entry is the number of the guest whose gift guest i receives. List the assignments in ascending order, comparing entry by entry from guest 0. If none exists, return an empty list.

Examples

Input

guests = 3, banned = []

Output

[[1, 2, 0], [2, 0, 1]]

Note

Only the two rotations avoid everyone receiving their own gift.

Input

guests = 2, banned = [[0, 1]]

Output

[]

Note

Guest 0 could only take guest 1's gift, which is banned.

Constraints

• 1 <= guests <= 8
• 0 <= number of banned pairs <= 56
• The result has at most 250 assignments

Hint 1: a nudge

For one guest, which gifts are still possible once some gifts are already taken and some are banned for that guest?

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