module M = Map.Make (struct type t = int * int let compare = compare end)
module S = Set.Make (struct type t = int let compare = compare end)

let () =
    let split s =
        let rec loop i cur flag acc =
            if i = String.length s then ( if flag then cur :: acc else acc) else (
                match flag, s.[i] with
                | true,  ' ' -> loop (i + 1) "" false (cur :: acc)
                | false, ' ' -> loop (i + 1) "" false acc
                | true,  v   -> loop (i + 1) (Printf.sprintf "%s%c" cur v) true acc
                | false, v   -> loop (i + 1) (Printf.sprintf "%s%c" cur v) true acc
            )
        in
        List.map int_of_string (List.rev (loop 0 "" false []))
    in
    let main () =
        let n = int_of_string (read_line ()) in
        let a = Array.init n (fun _ -> Array.of_list (split (read_line ()))) in
        let add key v l map =
            let c, d = v in
            l.(c - 1).(d - 1) <- l.(c - 1).(d - 1) + 1;
            M.add key (v :: try M.find key map with _ -> []) map
        in
        let canonical (a, b) = if a < b then a, b else b, a in
        let l = Array.make_matrix n n 0 in
        let rec loop_i i map =
            let rec loop_j j map =
                if j = n - 1 then map else
                    let v = a.(i).(j) in
                    let k = canonical (i + 1, v) in
                    let map =
                        if j = 0 then (
                            if v > i + 1 then add (0, 0) k l map else map
                        ) else (
                            let vv = a.(i).(j - 1) in
                            add (canonical (i + 1, vv)) k l map
                        )
                    in
                    loop_j (j + 1) map
            in
            if i = n then map else loop_i (i + 1) (loop_j 0 map)
        in
        let map = loop_i 0 (M.singleton (0, 0) []) in
        let rec emit day rest check map next set = function
            | [] -> if rest = 0 then day else
                    if next <> [] then emit (day + 1) rest check map [] S.empty next
                    else (-1)
            | (c, d) :: tl ->
                    if S.mem c set || S.mem d set then emit day rest check map ((c, d) :: next) set tl else
                        (*
                        let () = Printf.printf "day %d: can emit %d,%d\n" day c d in
        *)
                        let set = S.add d (S.add c set) in
                        let next = List.fold_left (fun acc (c, d) ->
                            if check.(c - 1).(d - 1) = 1 then (
                                check.(c - 1).(d - 1) <- 0;
                                (c, d) :: acc
                            ) else (
                                check.(c - 1).(d - 1) <- check.(c - 1).(d - 1) - 1;
                                acc
                            )
                        ) next (try M.find (c, d) map with _ -> [])
                        in
                        emit day (rest - 1) check map next set tl
        in
        let init = List.fold_left (fun acc (c, d) ->
            if l.(c - 1).(d - 1) = 1 then (
                l.(c - 1).(d - 1) <- 0;
                (c, d) :: acc
            ) else (
                l.(c - 1).(d - 1) <- l.(c - 1).(d - 1) - 1;
                acc
            )) [] (M.find (0, 0) map)
        in
        (*
        let () = List.iter (fun (c, d) -> Printf.printf "(%d, %d) " c d) init in
        let () = print_newline () in
    *)
        let r = emit 1 (n * (n - 1) / 2) l map [] S.empty init in
        Printf.printf "%d\n" r
    in
    main ()