How do you shuffle a dictionary with list of strings as values such that no key is adjacent?

# Please write a function to generate a random, 8-character password.
# It should satisfy the following requirements:

# 1) There should be exactly two characters from each of the following categories:
# - Uppercase letters
# - Lowercase letters
# - Numerals 0 - 9
# - Special Characters from the string “!@#$%^&*”

# 2) No two character categories should be adjacent.
# bad example: AXyu74$^

# 3) The categories should be randomly ordered.
# good example: 8b&U6Nz!  NLSUNULS
# */
import random, string
def generate_password():
    store = {}
    for category in 'ULSN':
        store[category] = []
    for i in range(2):
        store['U'].append(random.choice(string.ascii_letters).upper())
        store['L'].append(random.choice(string.ascii_letters).lower())
        store['N'].append(str(random.randint(0,9)))
        store['S'].append("!@#$%^&*"[random.randrange(0,7) + 1])
    print("".join([item for sublist in store.values() for item in sublist]))
    for item in store.items():
        print(item)
     # shuffle and eliminate adjacency
generate_password()

There is a dictionary with four keys. Each key maps to a different category, and each key has a list of 2 characters as the value.
How do you shuffle the dictionary to build a string in random order, such that no key is adjacent?
The goal is to efficiently return an 8 character long string with no adjacent values.
Examples and test cases are in the problem statement