#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <climits>
#include <algorithm>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#define N 4
#define M 20
//N要素数
//M=シャッフルする回数

using namespace std;
bool check(int v[N]){
	for(int i=0;i<N;i++){
		if(v[i]==N)return true;
	}
	return false;
}
void showList(int manRank[N][N],int womanSuki[N][N]){
	cout << "男性希望リスト" << endl;
	for(int i=0;i<N;i++){
		cout << i << ":";
		for(int j=0;j<N;j++){
			cout << manRank[i][j];
			if(j!=N-1)cout << ",";
		}
		cout << endl;
	}

	cout << "女性希望リスト" << endl;
	int womanRank[N][N];
	for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				womanRank[i][womanSuki[i][j]]=j;
		}
	}
	for(int i=0;i<N;i++){
			cout << i << ":";
			for(int j=0;j<N;j++){
				cout << womanRank[i][j];
				if(j!=N-1)cout << ",";
			}
			cout << endl;
		}
}
void showMatch(int manMarriage[N],int womanMarriage[N]){
	cout << "男性-女性" << endl;
	for(int i=0;i<N;i++){
		cout << i << "-" << manMarriage[i] << endl;
	}
}

int main(){
	int manRank[N][N];
	int womanSuki[N][N];
	srand((unsigned) time(NULL));
	for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				manRank[i][j]=j;
				womanSuki[i][j]=j;
			}
	}
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			int hoge;
			int c1=rand() % N;
			int c2=rand() % N;
			hoge = manRank[i][c1];
			manRank[i][c1]=manRank[i][c2];
			manRank[i][c2]=hoge;
			c1=rand() % N;c2=rand() % N;
			hoge = womanSuki[i][c1];
			womanSuki[i][c1]=womanSuki[i][c2];
			womanSuki[i][c2]=hoge;
		}
	}
	showList(manRank,womanSuki);
	//誰と結婚しているか
	int womanMarriage[N];
	int manMarriage[N];
	//プロポーズ回数
	int manDraft[N];
	for(int i=0;i<N;i++){
		womanMarriage[i]=N;
		manMarriage[i]=N;
		manDraft[i]=0;
	}

	//独身男性がいる限りループ
	int cnt=0;
	while(check(manMarriage)){

		for(int i=0;i<N;i++){
			if(manMarriage[i]==N){//iが未婚男性の場合
				int hope = manRank[i][manDraft[i]];//希望女性
				if(womanMarriage[hope]==N){//希望女性が未婚
					manMarriage[i]=hope;			//結婚
					womanMarriage[hope]=i;
					manDraft[i]++;
				}
				else{//希望女性が既婚
					if(womanSuki[hope][i]<womanSuki[hope][womanMarriage[hope]]){//女性にとって今プロポーズされた男性の方が良い時
						manMarriage[womanMarriage[hope]]=N;//NTRれた人は未婚に
						womanMarriage[hope]=i;				//結婚しなおし
						manMarriage[i]=hope;
						manDraft[i]++;
					}
					else{//NTR失敗
						manDraft[i]++;//プロポーズカウント
					}
				}
			}
		}
	}
	showMatch(manMarriage,womanMarriage);
	return 0;
}