package main import ( "bufio" "fmt" "os" "sort" "strconv" ) var sc = bufio.NewScanner(os.Stdin) var wr = bufio.NewWriter(os.Stdout) func out(x ...interface{}) { fmt.Fprintln(wr, x...) } func getI() int { sc.Scan() i, e := strconv.Atoi(sc.Text()) if e != nil { panic(e) } return i } func getF() float64 { sc.Scan() i, e := strconv.ParseFloat(sc.Text(), 64) if e != nil { panic(e) } return i } func getInts(N int) []int { ret := make([]int, N) for i := 0; i < N; i++ { ret[i] = getI() } return ret } func getS() string { sc.Scan() return sc.Text() } // min, max, asub, absなど基本関数 func max(a, b int) int { if a > b { return a } return b } func min(a, b int) int { if a < b { return a } return b } func asub(a, b int) int { if a > b { return a - b } return b - a } func abs(a int) int { if a >= 0 { return a } return -a } func lowerBound(a []int, x int) int { idx := sort.Search(len(a), func(i int) bool { return a[i] >= x }) return idx } func upperBound(a []int, x int) int { idx := sort.Search(len(a), func(i int) bool { return a[i] > x }) return idx } func main() { defer wr.Flush() sc.Split(bufio.ScanWords) sc.Buffer([]byte{}, 1000000) // this template is new version. // use getI(), getS(), getInts(), getF() N := getI() S := getInts(N) T := getInts(N) U := getInts(N) for i := 0; i < N; i++ { S[i]-- T[i]-- } ts := New(N * N) var id = func(i, j int) int { return i*N + j } for i := 0; i < N; i++ { for j := 0; j < N; j++ { switch U[i] { case 0: ts.AddClause(id(S[i], j), true, id(j, T[i]), true) case 1: ts.AddClause(id(S[i], j), false, id(j, T[i]), true) case 2: ts.AddClause(id(S[i], j), true, id(j, T[i]), false) case 3: ts.AddClause(id(S[i], j), false, id(j, T[i]), false) } } } if !ts.Satisfiable() { out("-1") return } ans := ts.Answer() // test := make([][]int, N) for i := 0; i < N; i++ { // test[i] = make([]int, N) for j := 0; j < N; j++ { if ans[id(i, j)] { fmt.Fprint(wr, 1, " ") // test[i][j] = 1 } else { fmt.Fprint(wr, 0, " ") // test[i][j] = 0 } } fmt.Fprintln(wr) } // test = [][]int{{0, 0, 0}, {1, 0, 1}, {0, 0, 0}} // out(test) // for i := 0; i < N; i++ { // for j := 0; j < N; j++ { // x := test[S[i]][j] + 2*test[j][T[i]] // if x == U[i] { // out(i, j, x, U[i]) // } // } // } } // TwoSat defines n, answer and scc type TwoSat struct { n int answer []bool scc *SccGraph } // New creates a TwoSAT of n variables and 0 clauses func New(n int) *TwoSat { ts := &TwoSat{ n: n, answer: make([]bool, n), scc: NewGraph(n * 2), } return ts } func (ts *TwoSat) internalJudge(f bool, a int, b int) int { if f { return a } return b } // AddClause adds a clause. func (ts *TwoSat) AddClause(i int, f bool, j int, g bool) { if !(0 <= i && i < ts.n) { panic("") } if !(0 <= j && j < ts.n) { panic("") } ts.scc.AddEdge(2*i+ts.internalJudge(f, 0, 1), 2*j+ts.internalJudge(g, 1, 0)) ts.scc.AddEdge(2*j+ts.internalJudge(g, 0, 1), 2*i+ts.internalJudge(f, 1, 0)) } // Satisfiable returns True if there is a truth assignment that satisfies all clauses func (ts *TwoSat) Satisfiable() bool { id := ts.scc.SccIds().Second for i := 0; i < ts.n; i++ { if id[2*i] == id[2*i+1] { return false } ts.answer[i] = id[2*i] < id[2*i+1] } return true } // Answer returns a truth assignment that satisfies all clauses of the last call of satisfiable func (ts *TwoSat) Answer() []bool { return ts.answer } type sccFromToPair struct { first, second int } type sccIdPair struct { First int Second []int } type csr struct { start []int elist []int } func initCsr(n int, edges []*sccFromToPair) *csr { var ret csr ret.start = make([]int, n+1) ret.elist = make([]int, len(edges)) for _, e := range edges { ret.start[e.first+1]++ } for i := 1; i <= n; i++ { ret.start[i] += ret.start[i-1] } counter := make([]int, len(ret.start)) copy(counter, ret.start) for _, e := range edges { ret.elist[counter[e.first]] = e.second counter[e.first]++ } return &ret } // SccGraph : type SccGraph struct { n int edges []*sccFromToPair } // NewGraph : func NewGraph(n int) *SccGraph { var s SccGraph s.n = n return &s } // AddEdge : func (s *SccGraph) AddEdge(from, to int) { s.edges = append(s.edges, &sccFromToPair{from, to}) } func (s *SccGraph) min(a, b int) int { if a > b { return b } return a } // SccIds : func (s *SccGraph) SccIds() sccIdPair { g := initCsr(s.n, s.edges) nowOrd, groupNum := 0, 0 visited := make([]int, 0, s.n) low := make([]int, s.n) ord := make([]int, s.n) ids := make([]int, s.n) for i := 0; i < s.n; i++ { ord[i] = -1 } var dfs func(v int) dfs = func(v int) { low[v] = nowOrd ord[v] = nowOrd nowOrd++ visited = append(visited, v) for i := g.start[v]; i < g.start[v+1]; i++ { to := g.elist[i] if ord[to] == -1 { dfs(to) low[v] = s.min(low[v], low[to]) } else { low[v] = s.min(low[v], ord[to]) } } if low[v] == ord[v] { for { u := visited[len(visited)-1] visited = visited[:len(visited)-1] ord[u] = s.n ids[u] = groupNum if u == v { break } } groupNum++ } } for i := 0; i < s.n; i++ { if ord[i] == -1 { dfs(i) } } for i := 0; i < len(ids); i++ { ids[i] = groupNum - 1 - ids[i] } return sccIdPair{groupNum, ids} } // Scc : func (s *SccGraph) Scc() [][]int { ids := s.SccIds() groupNum := ids.First counts := make([]int, groupNum) for _, x := range ids.Second { counts[x]++ } groups := make([][]int, ids.First) for i := 0; i < groupNum; i++ { groups[i] = make([]int, 0, counts[i]) } for i := 0; i < s.n; i++ { groups[ids.Second[i]] = append(groups[ids.Second[i]], i) } return groups }