We present HST spectroscopy of the nucleus of M31 obtained with STIS. Spectra taken around the CaT lines at 8500 see only the red giants in the double bright- ness peaks P1 and P2. In contrast, spectra taken at 3600-5100 A are sensitive to the tiny blue nucleus embedded in P2, the lower surface brightness red nucleus. P2 has a K-type spectrum, but the embedded blue nucleus has an A-type spectrum with strong Balmer absorption lines. Given the small likelihood for stellar collisions, a 200 Myr old starburst appears to be the most plausible origin of the blue nucleus. In stellar population, size, and velocity dispersion, the blue nucleus is so different from P1 and P2 that we call it P3. The line-of-sight velocity distributions of the red stars in P1+P2 strengthen the support for Tremaine s eccentric disk model. The kinematics of P3 is consistent with a circular stellar disk in Keplerian rotation around a super-massive black hole with M_bh = 1.4 x 10^8 M_sun. The P3 and the P1+P2 disks rotate in the same sense and are almost coplanar. The observed velocity dispersion of P3 is due to blurred rotation and has a maximum value of sigma = 1183+-201 km/s. The observed peak rotation velocity of P3 is V = 618+-81 km/s at radius 0.05 = 0.19 pc corresponding to a circular rotation velocity at this radius of ~1700 km/s. Any dark star cluster alternative to a black hole must have a half-mass radius <= 0.03 = 0.11 pc. We show that this excludes clusters of brown dwarfs or dead stars on astrophysical grounds.