夏天到了!夏天,就是最適合戀愛的季節~~~
現在呢,你是相親活動的主辦活動,想要撮合 N 位男生與 N 位女生,各自皆從 1 編號到 N。經過了許多輪的團康活動等等,你讓每個人都將異性依照喜好的程度排序 —— 是的,愛情是殘酷的。你想要找到一種將這 2N 個人分成 N 對男女,而且為了要儘量讓這些男女找到幸福,不要讓有人的伴侶找去找其他人的伴侶玩這種尷尬的事情發生,還必須滿足這個條件:
請幫忙解決這個問題吧!
輸入有 2N+1 行。第一行是一個數字 N(1≤N≤800),代表有幾個男生與女生。接下來的 N 行的第 i 行中的第 j 個數字 sij 代表編號為 i 的男生第 j 心儀的女生。然後也會有 N 行,其中第 i 行中的第 j 個數字 tij 代表編號為 i 的女生第 j 喜歡的男生。
保證所有的資料皆合法,不會出現範圍外的數字與重複的排名。
如果有解,請輸出 N 個數字,第 i 個數字 xi 代表編號為 i 的男生應該要和編號為 xi 的女生配對。如果無論如何都無法滿足條件,請輸出 -1。倘若有多組解,輸出任意一者即可。
-1