The aim of this paper is to establish a complete sample of red supergiants (RSGs) in M31 and M33. The member stars of the two galaxies are selected from the near-infrared (NIR) point sources after removing the foreground dwarfs from their obvious branch in the J - H/H - K diagram with the archival photometric data taken by the UKIRT/WFCAM. This separation by NIR colors of dwarfs from giants is confirmed by the optical/infrared color-color diagrams (r - z/z - H and B - V/V - R) and the Gaia measurement of parallax and proper motion. The RSGs are then identified by their outstanding location in the members' J - K/K diagram due to high luminosity and low effective temperature. The resultant sample has 5498 and 3055 RSGs in M31 and M33 respectively, which should be complete because the lower limiting K magnitude of RSGs in both cases is brighter than the complete magnitude of the UKIRT photometry. Analysis of the control fields finds that the pollution rate in the RSG sample is less than 1%. The by-product is the complete sample of oxygen-rich asymptotic giant branch stars (AGBs), carbon-rich AGBs, thermally pulsing AGBs, and extreme AGBs. In addition, the tip-RGB is determined together with its implication on the distance modulus to M31 and M33.