TopCoder

aacpschool

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

66.7% (2/3)

Description

夏天到了！夏天，就是最適合戀愛的季節～～～

現在呢，你是相親活動的主辦活動，想要撮合 $N$ 位男生與 $N$ 位女生，各自皆從 $1$ 編號到 $N$。經過了許多輪的團康活動等等，你讓每個人都將異性依照喜好的程度排序 —— 是的，愛情是殘酷的。你想要找到一種將這 $2N$ 個人分成 $N$ 對男女，而且為了要儘量讓這些男女找到幸福，不要讓有人的伴侶找去找其他人的伴侶玩這種尷尬的事情發生，還必須滿足這個條件：

對於任何兩個異性且目前不是一對的人，他們不會兩個都想要換伴侶成對方（也就是兩個對於對方的好感比目前的伴侶都高）。

請幫忙解決這個問題吧！

Input Format

輸入有 $2N + 1$ 行。第一行是一個數字 $N(1 \leq N \leq 800)$，代表有幾個男生與女生。接下來的 $N$ 行的第 $i$ 行中的第 $j$ 個數字 $s_{ij}$ 代表編號為 $i$ 的男生第 $j$ 心儀的女生。然後也會有 $N$ 行，其中第 $i$ 行中的第 $j$ 個數字 $t_{ij}$ 代表編號為 $i$ 的女生第 $j$ 喜歡的男生。

保證所有的資料皆合法，不會出現範圍外的數字與重複的排名。

Output Format

如果有解，請輸出 $N$ 個數字，第 $i$ 個數字 $x_i$ 代表編號為 $i$ 的男生應該要和編號為 $x_i$ 的女生配對。如果無論如何都無法滿足條件，請輸出 -1。倘若有多組解，輸出任意一者即可。

Sample Input 1

3
2 1 3
3 2 1
1 3 2
2 1 3
3 2 1
1 3 2

Sample Output 1

2 3 1

Sample Input 2

2
1 2
1 2
2 1
1 2

Sample Output 2

2 1

Sample Input 3

2
1 2
2 1
1 2
2 1

Sample Output 3

1 2

Hints

Problem Source

No.	Testdata Range	Constraints	Score
1	0~2	範例測資	0
2	0~12	無額外限制	100

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	3000	524288	65536	1 2
1	3000	524288	65536	1 2
2	3000	524288	65536	1 2
3	3000	524288	65536	2
4	3000	524288	65536	2
5	3000	524288	65536	2
6	3000	524288	65536	2
7	3000	524288	65536	2
8	3000	524288	65536	2
9	3000	524288	65536	2
10	3000	524288	65536	2
11	3000	524288	65536	2
12	3000	524288	65536	2

732 . 相親問題