M16, the Eagle Nebula, is an outstanding HII region where extensive high-mass star formation is taking place in the Sagittarius Arm, and hosts the remarkable pillars observed with HST. We made new CO observations of the region in the 12CO J=1--0 and J=2--1 transitions with NANTEN2. These observations revealed for the first time that a giant molecular cloud of $sim 1.3 times 10^5$ Msun is associated with M16, which is elongated vertically to the Galactic plane over 35 pc at a distance of 1.8 kpc. We found a cavity of the molecular gas of $sim 10$ pc diameter toward the heart of M16 at lbeq (16.95degree, 0.85degree), where more than 10 O-type stars and $sim 400$ stars are associated, in addition to a close-by molecular cavity toward a Spitzer bubble N19 at lbeq (17.06degree, 1.0degree). We found three velocity components which show spatially complementary distribution in the entire M16 giant molecular cloud (GMC) including NGC6611 and N19, suggesting collisional interaction between them. Based on the above results we frame a hypothesis that collision between the red-shifted and blue-shifted components at a relative of $sim 10$ kms triggered formation of the O-type stars in the M16 GMC in the last 1-2 Myr. The collision is two fold in the sense that one of the collisional interactions is major toward the M16 cluster and the other toward N19 with a RCW120 type, the former triggered most of the O star formation with almost full ionization of the parent gas, and the latter an O star formation in N19.