Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
The Domino Principle
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 1837Accepted: 479

Description

There is a configuration of N domino stones that is to be beautifully destroyed. For each stone i in the given configuration, we know the set Di of the stones that will fall at time t+1 (if they have not fallen before) if the stone i falls at time t.

Write a program to determine which stone should be pushed to fall at the time 0 to achieve complete destruction of the configuration that takes the longest possible time.

Input

The first line of the input contains the number of stones N in the configuration (1≤N≤1000). Next N lines describe sets Di (1≤iN). Each of these lines contains first the potency of the set Di and then the numbers of stones in the set separated by one or more spaces.

Output

The first line of the output must contain the time of fall of the last stone in the configuration, and the second line - the number of the stone that should be pushed first. If the maximal time can be achieved starting from several initial stones, output the maximal possible number. If the configuration can’t be destroyed completely, the first and only line of the file must contain the word ‘impossible’.

Sample Input

3
2 2 3
1 3
0

Sample Output

1
1

Source

Northeastern Europe 2002, Western Subregion

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator