Sachverhalt: Sachverhalt: A. Die albanischen Staatsangehörigen Y._, geboren am _1976, und X._, geboren am _1974, beantragten am 5. Februar 2004 Asyl in der Schweiz. Aufgrund eines Fahndungsersuchens von Interpol Tirana wurden sie am 6. Februar 2004 in provisorische Auslieferungshaft versetzt. A. Die albanischen Staatsangehörigen Y._, geboren am _1976, und X._, geboren am _1974, beantragten am 5. Februar 2004 Asyl in der Schweiz. Aufgrund eines Fahndungsersuchens von Interpol Tirana wurden sie am 6. Februar 2004 in provisorische Auslieferungshaft versetzt. B. Am 16. Februar 2004 reichte die albanische Botschaft in Bern beim Bundesamt für Justiz ein Auslieferungsersuchen gegen Y._ und X._ ein. Y._ wird verdächtigt, zusammen mit seinem Cousin A._, eine bewaffnete Bande geleitet zu haben. Zusammen mit anderen Bandenmitgliedern habe Y._ im Zeitraum zwischen dem 2. Juni 1992 und dem 16. April 1996 in Tirana und Vlora insgesamt 15 Überfälle auf Banken, Tankstellen, Fluggesellschaften, Geschäfte und Privatpersonen begangen. Bei den Überfällen vom 15. Dezember 1993 und vom 12. April 1995 sei je eine Person getötet worden. Am 30. Juni 1993 soll er einen Polizisten in Tirana angegriffen haben, um diesem seine Dienstpistole zu entwenden; dabei sei der Polizist durch 5 Messerstiche schwer verletzt worden. Am 31. Oktober 1995 hätten er und andere Bandenmitglieder das Kind B._ in Tirana entführt, um von den Eltern USD 200'000.-- Lösegeld zu erlangen; das Kind sei am 2. November 1995 freigelassen worden, als die Täter zur Überzeugung gelangt seien, dass die Eltern den geforderten Betrag nicht zahlen könnten. Am 26. Februar 1996 habe er neben dem Supermarkt "VEFA" Sprengstoff in einem Auto deponiert; bei der Explosion der Autobombe seien 4 Personen getötet und 11 Personen verletzt worden. Schliesslich soll er am 26. Juli 1996 in Tirana den Generaldirektor der Gefängnisse Albaniens, C._, mit einer Schusswaffe getötet haben. X._ wird verdächtigt, als Mitglied der Bande an fünf Raubüberfällen in Tirana beteiligt gewesen zu sein, begangen zwischen dem 2. Juni 1992 und dem 21. Februar 1995. X._ wird verdächtigt, als Mitglied der Bande an fünf Raubüberfällen in Tirana beteiligt gewesen zu sein, begangen zwischen dem 2. Juni 1992 und dem 21. Februar 1995. C. Am 17. Februar 2004 wurde die Albanische Botschaft in Bern zur Ergänzung des formellen Auslieferungsersuchens aufgefordert. Die Ergänzungen wurden mit Note vom 25. Februar 2004 eingereicht. C. Am 17. Februar 2004 wurde die Albanische Botschaft in Bern zur Ergänzung des formellen Auslieferungsersuchens aufgefordert. Die Ergänzungen wurden mit Note vom 25. Februar 2004 eingereicht. D. Am 12. März 2004 wies das Bundesamt für Flüchtlinge die Asylanträge Y._s und X._s ab. Diese erhoben dagegen Beschwerde an die Asylrekurskommission. D. Am 12. März 2004 wies das Bundesamt für Flüchtlinge die Asylanträge Y._s und X._s ab. Diese erhoben dagegen Beschwerde an die Asylrekurskommission. E. Y._ und X._ widersetzen sich einer Auslieferung nach Albanien. Ihr gemeinsamer Rechtsvertreter reichte mehrere Stellungnahmen und zahlreiche Unterlagen ein und beantragte mit Schreiben vom 17. März und vom 13. April 2004 die Einholung ergänzender Unterlagen. E. Y._ und X._ widersetzen sich einer Auslieferung nach Albanien. Ihr gemeinsamer Rechtsvertreter reichte mehrere Stellungnahmen und zahlreiche Unterlagen ein und beantragte mit Schreiben vom 17. März und vom 13. April 2004 die Einholung ergänzender Unterlagen. F. Am 23. April 2004 bewilligte das Bundesamt für Justiz in zwei getrennten Verfügungen die Auslieferung von Y._ und von X._ für die dem Auslieferungsersuchen der Albanischen Botschaft vom 16. Februar 2004 zugrunde liegenden Straftaten unter Vorbehalt eines rechtskräftigen ablehnenden Asylentscheids. F. Am 23. April 2004 bewilligte das Bundesamt für Justiz in zwei getrennten Verfügungen die Auslieferung von Y._ und von X._ für die dem Auslieferungsersuchen der Albanischen Botschaft vom 16. Februar 2004 zugrunde liegenden Straftaten unter Vorbehalt eines rechtskräftigen ablehnenden Asylentscheids. G. Dagegen erhoben Y._ und X._ am 25. Mai 2004 Verwaltungsgerichtsbeschwerde ans Bundesgericht. Sie beantragen, sie seien nicht nach Albanien auszuliefern. In verfahrensrechtlicher Hinsicht beantragen sie, ihnen Gelegenheit und Frist zu gewähren, um gewisse ergänzende Unterlagen einzureichen und zur Antwort des Bundesamtes auf ihre ergänzenden Anfragen Stellung zu nehmen; die Akten der Asylrekurskommission seien beizuziehen. Sodann ersuchen sie um die gemeinsame Behandlung ihrer Beschwerden. Das Bundesamt für Justiz beantragt, die Beschwerden seien abzuweisen. Das Bundesamt für Justiz beantragt, die Beschwerden seien abzuweisen. H. Mit Eingabe vom 11. Juni 2004 beantragten die Beschwerdeführer, es sei das Bundesamt zu ersuchen, Stellung zu nehmen zur Frage, wie die schweizerische Vertretung in Albanien sich konkret für ein korrektes Verfahren nach den Grundsätzen des albanischen Rechts und unter Wahrung der Menschenrechte der Inhaftierten verwenden und einsetzen könne, und es sei ihrem Rechtsvertreter danach die Möglichkeit zur Stellungnahme zu gewähren. Am 15. Juni 2004 reichten die Beschwerdeführer eine Stellungnahme von Prof. D._, Präsident des albanischen Anwaltsverbands und Mitglied des europäischen Anwaltsverbands, ein.