The Hotel Rooms


The organizers of the International Olympiad in Informatics (IOI) 2014 have just booked the hotel for the IOI. The hotel only has three-person rooms, so the participants will be accommodated in triples.

The organizers want the participants to like their roommates. Hence they asked each participant for a list of at most three other people he or she prefers to share the room with. (Note that at most two people from such a list can actually be chosen.)

This preference is symmetric: if $a$ wants to share a room with $b$, you can be certain that $b$ wants to share a room with $a$ as well.

A room is happy if it contains three participants and for each of them the two roommates are both on the list he or she provided.

Now the organizers have a problem: how to distribute the contestants into rooms in such a way that the number of happy rooms is maximized?


You are given the lists of preferences provided by the participants. Design an algorithm which computes the largest possible number of happy rooms, and one possibility how the happy rooms will look like.

In other words, your algorithm has to produce a list of disjoint triples of participants. In each triple, each participant must want to share the room with each of the other two. The list must be as long as possible. (Note that some participants may be omitted from the list. Those will then live in unhappy rooms.)

Note that a significant number of points will be awarded for a proof that your algorithm is correct and always produces the maximum number of happy rooms.


The first line of the input contains a single integer $n$ – the number of participants. The participants are numbered from $1$ to $n$.

Then, $n$ lines follow. The $i$-th of these lines contains the list of preferred roommates for contestant $i$. This list is given as exactly three integers $x_i$, $y_i$ and $z_i$ separated by single spaces. If the participant $i$ has less than three preferred roommates, some of $x_i$, $y_i$ and $z_i$ will be zero (and you should ignore them).

Formally, you may assume that $0 \le x_i,y_i,z_i \le n$, $i \notin {x_i,y_i,z_i}$, and that the participant numbers in each list are distinct (i.e., lists like «6 6 0» will not appear).

You may assume that if $j$ appears in the list of participant $i$ ($i\neq j$) then also $i$ appears in the list of participant $j$.


The first line of the output should contain a single integer $r$ – the maximum number of happy rooms. (In other words, the maximum number of disjoint triples of participants that satisfy the above criteria.)

Each of the next $r$ lines should contain three integers separated by single spaces: the numbers of three participants that will stay together in one of the happy rooms.

If there are multiple optimal solutions, output any of them.

Sample test


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

1 2 3

Clearly, there cannot be more than one happy room. Still, there are other correct outputs: any of the triples $(1,2,4)$, $(1,3,4)$, and $(2,3,4)$ could also live in the happy room.


2 4 5
4 1 3
4 2 7
2 3 1
1 7 6
5 0 7
3 5 6

2 3 4
5 6 7

The input is shown in the following picture. Dots represent participants, lines connect participants who want to share a room.


Note that instead of the triple $(2,3,4)$ the triple $(1,2,4)$ can be selected. Since there are $7$ participants, it is not possible to have more than 2 happy rooms.


If you have any questions feel free to ask in the forum or send us an email at info[at]soi[dot]ch