Das Bundesgericht zieht in Erwägung:
Das Bundesgericht zieht in Erwägung:
1. Das Justiz- und Polizeidepartement des Kantons St. Gallen wies am 29. September 2005 einen Rekurs des sudanesischen Staatsangehörigen Y._ und seiner schweizerischen Lebenspartnerin X._ betreffend die Verweigerung der Aufenthaltsbewilligung für Y._ ab. Am 14. Oktober 2005 gelangten Y._ und X._ mit Beschwerde an das Verwaltungsgericht des Kantons St. Gallen. Nachdem sie zur Leistung eines Kostenvorschusses aufgefordert worden waren, ersuchte Y._ um Gewährung der unentgeltlichen Rechtspflege für das Verfahren vor dem Verwaltungsgericht. Dessen Präsident wies das Gesuch mit Verfügung vom 3. November 2005 wegen Aussichtslosigkeit der Beschwerde ab und setzte Frist zur Bezahlung des Vorschusses, verbunden mit der Androhung, dass das Verfahren im Säumnisfall abgeschrieben werden könne. Am letzten Tag der Frist, am 16. November 2005, ersuchte Y._ erneut um Gewährung der unentgeltlichen Rechtspflege. Der Verwaltungsgerichtspräsident erachtete die Eingabe als Wiedererwägungsgesuch und trat darauf nicht ein. Zugleich trat er, wegen Nichtleistens des Kostenvorschusses, gestützt auf die ihm in Art. 66 Abs. 1 lit. a des St. Galler Gerichtsgesetzes vom 2. April 1987 (GG) eingeräumte Kompetenz, auf die Beschwerde nicht ein. Y._ und X._ verlangten gestützt auf Art. 66 Abs. 2 GG innert der ihnen hiefür eingeräumten Frist von 14 Tagen am 2. Dezember 2005 einen Entscheid des Gerichts. Das Verwaltungsgericht erkannte mit Urteil vom 20. Dezember 2005, auf die Beschwerde werde wegen Nichtleistens des Kostenvorschusses nicht eingetreten; die amtlichen Kosten auferlegte es Y._ und X._.
Mit als staatsrechtliche Beschwerde und als Verwaltungsgerichtsbeschwerde bezeichneter Eingabe vom 7. Januar 2006 beantragen X._ und Y._ dem Bundesgericht, die Verfügung und den Entscheid des Präsidenten des Verwaltungsgerichts des Kantons St. Gallen vom 3. bzw. 22. November 2005 sowie das Urteil des Verwaltungsgerichts vom 20. Dezember 2005 aufzuheben und die Streitsache an die Vorinstanz zwecks materieller Behandlung des Gesuchs um Aufenthaltsbewilligung für Y._ zurückzuweisen. Für diesen wird zudem um Gewährung der unentgeltlichen Rechtspflege auch für das bundesgerichtliche Verfahren ersucht.
Es ist weder ein Schriftenwechsel noch sind andere Instruktionsmassnahmen (Einholen zusätzlicher Akten) angeordnet worden.
Es ist weder ein Schriftenwechsel noch sind andere Instruktionsmassnahmen (Einholen zusätzlicher Akten) angeordnet worden.
2. 2.1 Die Beschwerdeführer haben sowohl Verwaltungsgerichtsbeschwerde als auch staatsrechtliche Beschwerde erhoben. Die staatsrechtliche Beschwerde steht als subsidiäres Rechtsmittel nur offen, falls und soweit die Verwaltungsgerichtsbeschwerde nicht zulässig ist (vgl. Art. 84 Abs. 2 OG). Art und Zulässigkeit von Rechtsmitteln prüft das Bundesgericht von Amtes wegen (<ref-ruling> E. 1 S. 60, 571 E. 1 S. 573, je mit Hinweisen).
2.1.1 Beim Urteil vom 20. Dezember 2005 handelt es sich um einen auf kantonales Verfahrensrecht gestützten Nichteintretensentscheid. Soweit ein materieller Sachentscheid mit Verwaltungsgerichtsbeschwerde anfechtbar wäre, stünde dieses Rechtsmittel auch zur Anfechtung des Nichteintretensentscheids zur Verfügung (<ref-ruling> E. 2a S. 13; <ref-ruling> E. 2c S. 277, je mit Hinweisen).
Materieller Streitgegenstand ist die Verweigerung einer Aufenthaltsbewilligung an den Beschwerdeführer, auf welche nach Auffassung der Beschwerdeführer ein Rechtsanspruch besteht. Die Zulässigkeit der Verwaltungsgerichtsbeschwerde hängt vom Bestand eines solchen Rechtsanspruchs ab (vgl. Art. 100 Abs. 1 lit. b Ziff. 3 OG). Das Rechtsmittel, mit welchem das Bestehen eines Rechtsanspruchs behauptet wird, ist vorerst als Verwaltungsgerichtsbeschwerde entgegenzunehmen, wobei die entsprechende Frage im Rahmen der Eintretensvoraussetzungen zu prüfen ist (<ref-ruling> E. 1 S. 283; vgl. <ref-ruling> E. 3a S. 167 bzw. E. 1b S. 165). Wird ein Rechtsanspruch verneint, ist auf die Verwaltungsgerichtsbeschwerde wegen Unzulässigkeit nicht einzutreten, und (weitere) Rügen sind, soweit die Voraussetzungen erfüllt sind, im Rahmen der staatsrechtlichen Beschwerde zu behandeln.
2.1.2 Was die Verfügung vom 3. November 2005 betrifft, wäre diese für sich allein betrachtet nur mit staatsrechtlicher Beschwerde anfechtbar, unabhängig davon, welches Rechtmittel gegen den materiellen Sachentscheid offenstehen würde (BGE <ref-ruling> E. 2d S. 277 f.). Die Beschwerdefrist von 30 Tagen ist indessen nicht eingehalten; aus dem Fehlen einer Rechtsmittelbelehrung können die Beschwerdeführer nichts ableiten, besteht doch keine Pflicht, eine solche hinsichtlich des ausserordentlichen Rechtsmittels der staatsrechtlichen Beschwerde anzubringen. Nun handelt es sich bei dieser Verfügung um einen Zwischenentscheid, welcher nur unter den Voraussetzungen von Art. 87 Abs. 2 OG selbständig angefochten werden konnte; diese sind bei einem Zwischenentscheid betreffend die unentgeltliche Rechtspflege zwar grundsätzlich erfüllt. Wurde von der Möglichkeit der selbständigen Anfechtung des Zwischenentscheids nicht Gebrauch gemacht, kann dieser aber noch durch Beschwerde gegen den Endentscheid angefochten werden (Art. 87 Abs. 3 OG).
Was den Entscheid vom 22. November 2005 betrifft, ist dieser durch das Urteil vom 20. Dezember 2005 ersetzt worden, soweit damit auf die kantonale Verwaltungsgerichtsbeschwerde nicht eingetreten wurde. Bedeutung behält er insofern, als damit eine Wiedererwägung der Verfügung betreffend die unentgeltliche Rechtspflege abgelehnt worden ist; für seine diesbezügliche Anfechtung kann im Wesentlichen auf die Erwägungen zur Anfechtung der Verfügung vom 3. November 2005 verwiesen werden.
Unter den gegebenen Umständen (s. nachfolgend E. 2.2) kann die Frage offen bleiben, ob allenfalls auch hinsichtlich der Frage der unentgeltlichen Rechtspflege die Verwaltungsgerichtsbeschwerde gegeben sein könnte, weil die zwei diesbezüglichen, separat ergangenen Entscheidungen zusammen mit dem Nichteintretensurteil vom 20. Dezember 2005 angefochten werden (zu dieser besonderen Konstellation lässt sich BGE <ref-ruling> E. 2d und 2e nichts entnehmen).
2.2 Die Beschwerdeführer sind nicht miteinander verheiratet; auf Art. 7 ANAG, welcher dem ausländischen Ehegatten eines Schweizer Bürgers Anspruch auf Erteilung oder Verlängerung der Aufenthaltsbewilligung einräumt, können sie sich nicht berufen. Einen Bewilligungsanspruch glauben sie hingegen aus Art. 8 EMRK ableiten zu können, welcher das Recht auf Achtung des Privat- und Familienlebens garantiert. Sie machen dazu geltend, sie lebten seit Januar 2001 in "natürlicher Ehe", d.h. in einer Lebensgemeinschaft als Mann und Frau zusammen.
Das Bundesgericht hat anerkannt, dass der Lebenspartner eines Schweizer Bürgers unter gewissen Voraussetzungen gestützt auf das durch Art. 8 EMRK garantierte Recht auf Privatleben eine ausländerrechtliche Bewilligung beanspruchen kann. Dies ist unter Umständen der Fall bei gleichgeschlechtlichen Beziehungen (<ref-ruling> E. 4c S. 432 ff.). Bei Beziehungen zwischen Mann und Frau kann der Beweis für eine enge, auf Dauer und gegenseitige Unterstützung angelegte Beziehung durch Eingehen einer Ehe erbracht werden, und im ausländerrechtlichen Bereich kommt dann, soweit nicht unmittelbare gesetzliche Ansprüche bestehen (Art. 7 und 17 Abs. 2 ANAG), Art. 8 EMRK in seiner Ausgestaltung als Garantie des Familienlebens als anspruchbegründende Norm in Betracht. Ist hingegen trotz behaupteter enger, mehrjähriger Beziehung keine Ehe eingegangen worden, entfällt grundsätzlich die Möglichkeit, sich für das Erhältlichmachen einer ausländerrechtlichen Bewilligung auf Art. 8 EMRK zu berufen (vgl. dazu Urteil 2A.469/1995 vom 7. Februar 1996 E. 4).
Was die Beschwerdeführer bisher von einer Heirat abgehalten hat, lässt sich ihrer Beschwerde nicht entnehmen; sie legen offenbar Wert darauf, weiterhin ihre "natürliche Ehe" weiterführen zu wollen. Sie erwähnen nebenbei "unbestrittene(n) Bemühungen um eine zivilstandliche Ehe", ohne allerdings vor Bundesgericht konkretere Angaben hiezu zu machen. Sollte sich diesbezüglich eine Änderung ergeben, könnte sich dannzumal die Frage des Bewilligungsanspruchs allenfalls neu stellen. Zum heutigen Zeitpunkt, auf welchen es für die Zulässigkeit der Verwaltungsgerichtsbeschwerde ankommt, steht ihnen ein solcher Anspruch nicht zu. Die Verwaltungsgerichtsbeschwerde ist damit gemäss Art. 100 Abs. 1 lit. b Ziff. 3 OG unzulässig. Die Rügen der Beschwerdeführer sind damit im Rahmen der staatsrechtlichen Beschwerde zu prüfen.
2.3 Das Nichteintretensurteil wegen Nichtleistens des Kostenvorschusses beruht darauf, dass das Gesuch um unentgeltliche Rechtspflege im Verfahren vor dem Verwaltungsgericht abgelehnt worden ist. Es sind daher zuerst die gegen die Verfügung vom 3. November 2005 vorgebrachten Einwendungen zu prüfen.
Gemäss Art. 281 Abs. 2 lit. a des St. Galler Zivilprozessgesetzes vom 20. Dezember 1990, welcher nach Art. 99 Abs. 2 des Gesetzes des Kantons St. Gallen vom 16. Mai 1965 über die Verwaltungsrechtspflege (VRP) im Verfahren vor dem Verwaltungsgericht sachgemäss zur Anwendung kommt, wird die unentgeltliche Prozessführung nicht bewilligt, wenn das Verfahren aussichtslos erscheint. Diese Regelung hält vor <ref-law> stand und wird als solche von den Beschwerdeführern nicht bemängelt. Das Gesuch um unentgeltliche Rechtspflege ist wegen Aussichtslosigkeit der kantonalen Beschwerde abgewiesen worden. Dies ist in verfassungsrechtlicher Hinsicht nicht zu beanstanden:
Besteht kein Anspruch auf Erteilung einer fremdenpolizeilichen Aufenthaltsbewilligung, so kann gemäss <ref-law> vom Zeitpunkt der Einreichung eines Asylgesuchs bis zur Ausreise nach seiner rechtskräftigen Ablehnung oder bis zur Anordnung einer Ersatzmassnahme bei nicht durchführbarem Vollzug kein Verfahren um Erteilung einer solchen Bewilligung eingeleitet werden (Grundsatz der Ausschliesslichkeit des Asylverfahrens). Über das zweite vom Beschwerdeführer gestellte Asylgesuch ist noch nicht rechtskräftig entschieden, und er ist nicht aus der Schweiz ausgereist. Wie vorstehend dargelegt, besteht kein Rechtsanspruch auf die für den Beschwerdeführer beantragte Aufenthaltsbewilligung; er kann zurzeit die Erteilung einer Aufenthaltsbewilligung nicht erwirken. Daran konnten im kantonalen Verfahren keine ernsthaften Zweifel bestehen, nachdem <ref-law> die Aufnahme eines kantonalen Bewilligungsverfahrens vom Bestehen eines offensichtlich gegebenen grundsätzlichen Rechtsanspruchs abhängig macht (vgl. Urteil 2A.8/2005 vom 30. Juli 2005 E. 3). Das kantonale Beschwerdeverfahren durfte unter diesen Umständen als aussichtslos bezeichnet werden (zum Begriff der Aussichtslosigkeit <ref-ruling> E. 2.3.1 S. 135 f.; <ref-ruling> E. 2.5.3 S. 235 f.; <ref-ruling> E. 4b S. 275; <ref-ruling> E. 2c S. 306).
Auch die weitere gegen die Verfügung vom 3. November 2005 erhobene Rüge, diese habe keine Rechtsmittelbelehrung enthalten, ist unbegründet (s. vorne E. 2.1.2).
2.4 Keine Rügen erheben die Beschwerdeführer in Bezug auf den Entscheid vom 22. November 2005, soweit darin das Vorliegen von Wiedererwägungsgründen verneint wurde.
Sie rügen indessen eine Verletzung des Grundsatzes von Treu und Glauben, weil auf die Beschwerde nicht eingetreten worden sei, ohne dass ihnen nach Einreichung des Wiedererwägungsgesuchs am letzten Tag der Zahlungsfrist (16. November 2005) eine Notfrist für die Bezahlung des Kostenvorschusses angesetzt worden sei. Die Beschwerdeführer wurden erstmals am 14. Oktober 2005 zur Bezahlung eines Kostenvorschusses aufgefordert. Nachdem sie am 1. November 2005 allein für den Beschwerdeführer um unentgeltliche Rechtspflege ersucht hatten, wurde das Gesuch mit begründeter Verfügung vom 3. November 2005 abgewiesen, wobei ausdrücklich darauf hingewiesen wurde, dass das Verfahren bei Säumnis abgeschrieben werden könne. Ihr Wiedererwägungsgesuch vom 16. November 2005 erwies sich als untaugliche Eingabe, auf die nicht einzutreten war. Wie im Entscheid vom 22. November 2005 unter Hinweis auf Art. 27 VRP festgehalten wird, begründen Wiedererwägungsgesuche keinen Anspruch auf eine Stellungnahme der Behörde in der Sache und hemmen den Fristenlauf nicht. Die Beschwerdeführer äussern sich dazu nicht. Jedenfalls ist unter den gegebenen Umständen der Vorwurf, der Verzicht auf das Ansetzen einer neuen Zahlungsfrist verletze Treu und Glauben, unbegründet.
2.5 Inwiefern damit das mit Nichtleisten des Kostenvorschusses begründete Nichteintretensurteil vom 20. Dezember 2005 verfassungswidrig sein könnte, ist nicht ersichtlich.
2.6 Soweit auf die Beschwerde als staatsrechtliche Beschwerde eingetreten werden kann, ist sie unbegründet und abzuweisen.
2.7 Die Beschwerdeführer ersuchen darum, es sei dem Beschwerdeführer die unentgeltliche Rechtspflege vor Bundesgericht zu gewähren.
Wie sich aus den vorstehenden Erwägungen ergibt, muss die Beschwerde als aussichtslos bezeichnet werden. Das Gesuch ist schon darum abzuweisen (Art. 152 OG). Die finanziellen Verhältnisse des Beschwerdeführers müssen daher nicht geprüft werden, und es kann auch offen bleiben, wie es sich mit den finanziellen Verhältnissen der Beschwerdeführerin verhält.
Damit sind die bundesgerichtlichen Kosten, entsprechend dem Verfahrensausgang, den Beschwerdeführern aufzuerlegen (Art. 156 in Verbindung mit Art. 153 und 153a OG). Sie haben sie je zur Hälfte unter Solidarhaft für die andere Hälfte zu tragen (Art. 156 Abs. 7 OG).

Demnach erkennt das Bundesgericht:
Demnach erkennt das Bundesgericht:
1. Auf die Verwaltungsgerichtsbeschwerde wird nicht eingetreten.
1. Auf die Verwaltungsgerichtsbeschwerde wird nicht eingetreten.
2. Die staatsrechtliche Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die staatsrechtliche Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
3. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
4. Die Gerichtsgebühr von Fr. 1'000.-- wird den Beschwerdeführern unter Solidarhaft auferlegt.
4. Die Gerichtsgebühr von Fr. 1'000.-- wird den Beschwerdeführern unter Solidarhaft auferlegt.
5. Dieses Urteil wird den Beschwerdeführern, dem Justiz- und Polizeidepartement und dem Verwaltungsgericht des Kantons St. Gallen sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 13. Januar 2006
Im Namen der II. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: