E - League

Contest Duration: 2019-09-01(Sun) 12:00 - 2019-09-01(Sun) 13:40 (local time) (100 minutes) Back to Home

E - League Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $500$ 点

問題文

$N$ 人の選手がテニスの大会に参加します。彼らを選手 $1$ 、選手 $2$ 、 $\ldots$ 、選手 $N$ と呼びます。

大会は総当たり戦で、合計 $N(N-1)/2$ 試合が行われます。これらの試合の日程を、以下の条件をすべて満たすように決めることは可能でしょうか。可能である場合、必要な最小の日数も求めてください。

各選手は一日に最大で一試合を行う。
各選手 $i$ $(1 \leq i \leq N)$ は、選手 $A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1}$ とこの順に一度ずつ試合を行う。

制約

$3 \leq N \leq 1000$
$1 \leq A_{i, j} \leq N$
$A_{i, j} \neq i$
$A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1}$ はすべて異なる。

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $A_{1, 1}$   $A_{1, 2}$   $\ldots$   $A_{1, N-1}$ 
 $A_{2, 1}$   $A_{2, 2}$   $\ldots$   $A_{2, N-1}$ 
 $:$ 
 $A_{N, 1}$   $A_{N, 2}$   $\ldots$   $A_{N, N-1}$

出力

条件をすべて満たすように全試合の日程を決めることが可能なら必要な最小の日数を、不可能なら -1 を出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

$3$ 日間で次のように試合を行えばすべての条件を満たせます。

$1$ 日目: 選手 $1$ 対選手 $2$
$2$ 日目: 選手 $1$ 対選手 $3$
$3$ 日目: 選手 $2$ 対選手 $3$

これが必要な最小日数です。

入力例 2Copy

Copy

出力例 2Copy

Copy

$4$ 日間で次のように試合を行えばすべての条件を満たせます。

$1$ 日目: 選手 $1$ 対選手 $2$ 、選手 $3$ 対選手 $4$
$2$ 日目: 選手 $1$ 対選手 $3$
$3$ 日目: 選手 $1$ 対選手 $4$ 、選手 $2$ 対選手 $3$
$4$ 日目: 選手 $2$ 対選手 $4$

これが必要な最小日数です。

入力例 3Copy

Copy

出力例 3Copy

Copy

-1

どのような日程で試合を行っても何らかの条件に違反します。

Score : $500$ points

Problem Statement

$N$ players will participate in a tennis tournament. We will call them Player $1$ , Player $2$ , $\ldots$ , Player $N$ .

The tournament is round-robin format, and there will be $N(N-1)/2$ matches in total. Is it possible to schedule these matches so that all of the following conditions are satisfied? If the answer is yes, also find the minimum number of days required.

Each player plays at most one matches in a day.
Each player $i$ $(1 \leq i \leq N)$ plays one match against Player $A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1}$ in this order.

Constraints

$3 \leq N \leq 1000$
$1 \leq A_{i, j} \leq N$
$A_{i, j} \neq i$
$A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1}$ are all different.

Input

Input is given from Standard Input in the following format:

 $N$ 
 $A_{1, 1}$   $A_{1, 2}$   $\ldots$   $A_{1, N-1}$ 
 $A_{2, 1}$   $A_{2, 2}$   $\ldots$   $A_{2, N-1}$ 
 $:$ 
 $A_{N, 1}$   $A_{N, 2}$   $\ldots$   $A_{N, N-1}$

Output

If it is possible to schedule all the matches so that all of the conditions are satisfied, print the minimum number of days required; if it is impossible, print -1.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

All the conditions can be satisfied if the matches are scheduled for three days as follows:

Day $1$ : Player $1$ vs Player $2$
Day $2$ : Player $1$ vs Player $3$
Day $3$ : Player $2$ vs Player $3$

This is the minimum number of days required.

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy

All the conditions can be satisfied if the matches are scheduled for four days as follows:

Day $1$ : Player $1$ vs Player $2$ , Player $3$ vs Player $4$
Day $2$ : Player $1$ vs Player $3$
Day $3$ : Player $1$ vs Player $4$ , Player $2$ vs Player $3$
Day $4$ : Player $2$ vs Player $4$

This is the minimum number of days required.

Sample Input 3Copy

Copy

Sample Output 3Copy

Copy

-1

Any scheduling of the matches violates some condition.