Problem G. Siblings ≡

• problems
• en ru
 Author: Anton Karabanov Time limit: 1 sec Input file: Standard input Memory limit: 512 Mb Output file: Standard output

Statement

Siblings is a term used in social anthropology and other studies, meaning children who have the same parents. Full siblings are the ones who have the same mother and father, and half siblings only have one parent in common. Psychologists, studying sibling rivalry, got their hands on a database, containing data on people living in the same building. Help them find the largest group of full siblings for further studies.

The data is represented as a table with n rows and 3 columns. The first column is a person id. The second and third columns are ids of that person's parents in any order.

Input format

The first line of the input contains a single positive integer n — number of rows in the database. The next n lines each have three positive integers xi, yi, zi, separated by a whitespace, — ids as described above.

Output format

In the first line output a single positive integer — the largest number of full siblings (it's guaranteed to be unique). In the second line output their ids in ascending order.

Constraints

2 ≤ n ≤ 105

1 ≤ xi, yi, zi ≤ 109

Notes on the sample

It's convenient to represent the table from the sample as a graph. It shows that four people (with ids 207, 208, 411 и 511) have common parents. The other groups aren't as large.

Sample tests

No. Standard input Standard output
1
11
104 48 60
511 130 120
111 1 2
112 2 1
208 120 130
120 2 1
130 32 17
207 120 130
170 32 17
191 104 111
411 130 120
4
207 208 411 511

0.101s 0.016s 17