Monkeys

A zoo has N monkeys numbered from 1 to N. There are two large cages that can hold the monkeys.

Some pairs of monkeys dislike each other. If two monkeys that dislike each other are placed in the same cage, they may fight. Each monkey dislikes at most three other monkeys.

Divide the monkeys into the two cages so that all of the following conditions hold.

1. For every monkey, at most one monkey in the same cage dislikes it.
2. Neither cage is empty.

Given the number of monkeys and their dislike relationships, find any arrangement that satisfies the conditions.

The first line contains an integer N, the number of monkeys. N is an integer between 3 and 100,000, inclusive.

Each of the next N lines describes one monkey, in order from monkey 1 to monkey N. Each line first contains M, the number of monkeys disliked by this monkey, followed by M monkey numbers in increasing order. All integers are separated by spaces.

Only inputs for which a valid arrangement exists are given.

Print two lines.

On the first line, print the number of monkeys in one cage followed by their numbers, separated by spaces. On the second line, print the number of monkeys in the other cage followed by their numbers, separated by spaces.

The order of monkey numbers does not matter. If there are multiple valid arrangements, print any one of them.