input() prompts an else statement when it should be captured by the if statement

I have made a crude program that takes your music search history and makes suggestions of music for you to listen to. The program works, but there is a bug. In the code I write that 3 if the input() matches bands in the lists Rock, Pop or Classic then register that search, otherwise prompt the user to choose another band. Some of my input prompts this message even though the bands searched are in the above-mentioned lists, and if I repeat the input() it works without prompting this message. Why does this occur?

I have tried rephrasing. instead of,

else:
 print('Choose another band')

I wrote,

if music not in Rock and music not in Pop or music not in Classic:
 print('Choose another band!') 

I have also played around with the indentation.

The full code:

# Program to suggest music based on search experience.
import random

searchHistory = {'Rock':0,'Pop':0,'Classic':0}

Rock=['Metalica', 'Nirvana', 'Elvis', 'KISS', 'Robocop', 'Nightwish', 'Spawn']
Pop=['Britney', 'MJ', 'AAF', 'Siavash', 'GooGoosh', 'Justin', 'Madonna']
Classic=['Bach', 'Mozart', 'Poop', 'Moop', 'Doop', 'Zoom', 'Nevermind']

choice = []
RockSuggest=[]
PopSuggest=[]
ClassicSuggest=[]

#SearchHistory making while loop
while (searchHistory['Rock'] + searchHistory['Pop'] + searchHistory['Classic']) <= 6:
#Ask for music Band
 print('Search music.')
 music = input()


#Note number of searches according to genre
#If number of searches equel or exceed 2, give two suggestions

 if music in Rock:
  choice.append(music)
  searchHistory['Rock'] += 1

  if searchHistory['Rock']==2:
   i1=1
   while i1 < 3:
    a = random.randint(0,len(Rock)-1)
    if Rock[a] not in choice and Rock[a] not in RockSuggest:
     RockSuggest.append(Rock[a])
     i1+=1
  else:
   continue  #Loops back to the beginning

 if music in Pop:
  choice.append(music)
  searchHistory['Pop'] += 1

  if searchHistory['Pop']==2:
   i2=1
   while i2 < 3:
    b = random.randint(0,len(Pop)-1)
    if Pop[b] not in choice and Pop[b] not in PopSuggest:
     PopSuggest.append(Pop[b])
     i2+=1
  else:
   continue


 if music in Classic:
  choice.append(music)
  searchHistory['Classic'] += 1

  if searchHistory['Classic'] ==2:
   i3=1
   while i3 < 3:
    c = random.randint(0,len(Classic)-1)
    if Classic[c] not in choice and Classic[c] not in ClassicSuggest:
     ClassicSuggest.append(Classic[c])
     i3+=1
  else:
   continue

# if music not in Rock or music not in Pop or music not in Classic:
 else:
  print('Choose another band!')


#End of while loop

#Check dictionary and lists
print(searchHistory)
print(choice)
print(RockSuggest)
print(PopSuggest)
print(ClassicSuggest)

#Remove suggestions added prior to finishing choices and replace with a new suggestion
#If suggestions found in choices
#As I don't want suggestions for music I have searched for.

for i in range(len(choice)):
 if choice[i] in RockSuggest:
  RockSuggest.remove(choice[i])
  while len(RockSuggest) < 2:
   a = random.randint(0,len(Rock)-1)
   if Rock[a] not in choice and Rock[a] not in RockSuggest:
    RockSuggest.append(Rock[a])

 if choice[i] in PopSuggest:
  PopSuggest.remove(choice[i])
  while len(PopSuggest) < 2:
   b = random.randint(0,len(Pop)-1)
   if Pop[b] not in choice and Pop[b] not in PopSuggest:
    PopSuggest.append(Pop[b])

 if choice[i] in ClassicSuggest:
  ClassicSuggest.remove(choice[i])
  while len(ClassicSuggest) < 2:
   c = random.randint(0,len(Classic)-1)
   if Classic[c] not in choice and Classic[c] not in ClassicSuggest:
    ClassicSuggest.append(Classic[c])



#Print out result
if RockSuggest != []:
 print('Music suggestion of genre Rock:')
 for i in range(len(RockSuggest)):
  print(RockSuggest[i])

if PopSuggest != []:
 print('Music suggestion of genre Pop:')
 for i in range(len(PopSuggest)):
  print(PopSuggest[i])

if ClassicSuggest != []:
 print('Music suggestion of genre Classic:')
 for i in range(len(ClassicSuggest)):
  print(ClassicSuggest[i])