Handshakes in a party

3.3

6 votes
Graphs, Algorithms, Breadth-first search
Problem

You are organizing a new year's party and you have invited a lot of guests. Now, you want each of the guests to handshake with every other guest to make the party interactive. Your task is to know what will be the minimum time by which every guest meets others. One person can handshake with only one other person at once following the handshake should be of 3 seconds sharp.

You have prepared some data for each guest which is the order in which the Guest(i) will meet others. If the data is inconsistent, then print -1. Otherwise, print the minimum time in seconds.

Hint: The data will be inconsistent if the handshake sequence of one person contradicts with another person, for instance:

4
2 3 4
3 1 4
4 1 2
1 3 2

G(1) wants to meet G(2) first, but G(2) will meet G(1) after meeting G(3).
G(3) will be meeting G(2) after meeting G(4) and G(1) respectively while G(4) will meet G(3) after meeting G(1) and G(1) will meet G(4) only after meeting G(2) and G(3). Hence, no one will be able to shake hands following this order as each handshake require some prior handshakes to happen. 

Note: G(i) denotes the ith guest.

Input format

  • The first line will contain an integer N denoting the number of guests invited.
  • Next N lines will container N1 integers where the ith line will denote the sequence in whichGuest(i) met other guests.

Output format

If the input data is inconsistent, print -1. Otherwise, print the minimum time required for the handshakes (in seconds).

Constraints

1G(i)N1000

Sample Input
4
2 3 4
1 3 4
4 1 2
3 1 2
Sample Output
12
Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

In the first 3 second the guest (1,2) and (3,4) will meet each other.
In next 3 seconds, guest (1,3) will meet.
In next 3 seconds, guest (1,4) and (2,3) will meet.
In next 3 seconds, guest (2,4) will meet.
So, it will take 12 seconds for every guest to meet others.

Editor Image

?