Can not resolve symbol "FirebaseMessagingService"

You have to add another dependency:

dependencies {
     compile 'com.google.firebase:firebase-messaging:10.0.1'
}

Check the official doc.

you also need to add

compile "com.google.firebase:firebase-messaging:$PLAY_SERVICES_VERSION"