G = [] def add_vertile(value) G.push({value: value, edges: []}) G.size - 1 end def add_edge(u,v) G[u][:edges].push(v) G[v][:edges].push(u) end n = gets.to_i U = n.times.map {|u| add_vertile(u)} V = n.times.map {|v| add_vertile(v)} A = n.times.map { gets.to_i } n.times do |u| n.times do |v| add_edge(U[u],V[v]) unless v == A[u] end end M = Array.new(G.size, nil) def dfs(v, used = {}) used[v] = true G[v][:edges].find do |u| w = M[u] if !w || !used[w] && dfs(w,used) M[v] = u M[u] = v true else false end end end m = G.size.times.inject(0) do |s, v| M[v] || !dfs(v) ? s : s+1 end if m == n puts U.map {|u| M[u]}.map {|v| G[v][:value] } else puts -1 end