In Markandeya Purana there is this chapter where Rishi Jaimini asks the same question to the Holy Birds viz-"How could Draupadi marry the Pancha Pandavas?."
Quoting from the above link:
Apprehending the severe penance of Trishira, the son of powerful
Brahmana Twashta, Indra suspected danger of his own position and thus
killed Trishira. Twashta went into a rage and plucked a strand of hair
from his head and offered it in the homa kunda (Fire Pit) by his
mantrik power and created the mighty Vritrasura whose mission was to
kill Indra, who had already lost his sheen since he committed a
Brahmana. Indra deputed the Sapta Rishis to strike a deal with Vritra
so that he would not put Indra to immediate danger; but Vritra was
killed unawares by Indra.
These actions angered the community of Rakshasas resulting in
continuous warfare against Devas and Prithvi felt great burden of the
atrocities by the demons. Prithvi appealed to Indra and the Deities
who in turn took the forms of Pandavas.
Yadindradeham cha Tejasthanmumocha Swayam Vrishah, Kunthyamjaatho
Mahatejaastatho Raja Yudhishtarah/ Balam mumocha Pavanastatho Bhimo
vyajaayat, Shakraveeryardhatas chaiva jajney Paarthom Dhananjayah/
Utpanno Yamalou Maadriyam Shaka Rupou Mahadyuti, Panchadhaa
Bhagavannityamavateernah Shatukratuh/ Tasyotpanna Mahabhaaga Patni
KrishnaHutaashanat, Shakrasyaikasya sa Patni Krishna naanyascha
kasyachit/ Yogeeswaraah shareeraani Kurvati bahulaanyapi,
Panchaanaameka Patnitwamityetatkathitham tav
Meaning-Dharmaraja himself from the body of Indra deposited his
virility into Kunti from which was created Yudhishtara. The Deity of
Wind viz. Pavan deposited Indra’s radiance into Kunti as a result of
which Bhima was born. Indra gave away half of his ‘Shakti’ to Kunti
and Dhananjaya was thus born. Indra’s virility was transferred through
the two Ashwani Kumars to Devi Maadri and was born the pair of Nakul
and Sahadeva. Indra’s ‘Amshas’ (alternatives) were manifested among
all the five Pandava brothers clearly. Moreover, Indra’s wife Shachi
Devi as Yagnaseni was created from ‘Agni’ and hence Draupadi was
Indra’s own better half.Yogeswar Purush Indra could divide his own
radiance into as many parts as per his volition.
Hence, it was amply justified that Draupadi was indeed the common wife
of the five Pandavas.
The portion in bold in the above quote is the justification you're looking for.
If you want to know about the Holy Birds and how they came into existence then read this chapter of the same Purana.
