Problem G. Siblings

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


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.


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
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
207 208 411 511

0.267s 0.047s 15