KOI 동물원에는 마리의 원숭이가 있고, 이 원숭이들을 수용할 수 있는 두 개의 큰 우리가 있다. 모든 원숭이들은 1부터 까지의 번호가 매겨져 있다.

원숭이들 사이에는 유달리 서로 앙숙관계인 원숭이들이 있어서 같은 우리에 두었을 경우 서로 싸우는 경우가 많다. 두 원숭이 와 가 앙숙관계라는 것은 두 원숭이 , 가 서로 싫어하는 관계임을 의미한다. 또한, 각각의 한 원숭이에 대해 앙숙관계에 있는 원숭이들의 수는 기껏해야 세 마리라고 가정한다. 동물원에서는 원숭이들의 앙숙관계를 조사하여 아래의 두 조건을 만족하도록 원숭이들을 두 개의 우리에 나누어 수용하려고 한다.

• (조건 1) 각 원숭이에 대해 같은 우리 안에 있으며 앙숙관계인 원숭이는 한 마리 이하이다.
• (조건 2) 비어있는 우리는 없다. (즉, 하나의 우리에 원숭이를 모두 수용 가능한 경우가 있더라도 각각의 우리에는 적어도 한 마리 이상의 원숭이를 수용하여야 한다.)

예를 들어, N = 5 인 경우에 1번 원숭이는 {2, 3, 4}와 2는 {1, 3, 5}와 앙숙관계이고, 그리고 3은 {1, 2, 4}와 4는 {1, 3, 5}, 그리고 5는 {2, 4}와 앙숙관계라고 하자. 위의 조건을 만족하도록 원숭이들을 두 개의 우리로 나누려면 {1, 3, 5}를 하나의 우리에, 그리고 {2, 4}를 다른 우리에 수용하면 된다.

원숭이들의 수와 각 원숭이들의 앙숙관계가 입력으로 주어질 때, 위의 조건을 만족하도록 원숭이들을 두 개의 우리에 나누어 수용하는 프로그램을 작성하시오.

실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.

입력

• 첫째 줄에는 원숭이들의 수를 나타내는 하나의 정수 N 이 주어진다. 단, N 은 3이상 100,000이하의 정수이다.
• 둘째 줄부터 N 개의 줄에는 1번부터 번호순서대로 각 원숭이에 대해 앙숙관계에 있는 원숭이의 수 M 이 주어지고, 이어서 각 원숭이 번호 M 개가 오름차순으로 하나의 줄에 주어진다. 모든 정수들 사이에는 빈칸이 있다. 조건에 맞도록 원숭이들을 나누지 못하는 경우는 존재하지 않는다.

출력

• 첫째 줄에는 하나의 우리에 수용되는 원숭이들의 번호를 빈칸을 사이에 두고 임의의 순서대로 출력하고,
• 둘째 줄에는 또 다른 하나의 우리에 수용되는 원숭이들의 번호를 빈칸을 사이에 두고 임의의 순서대로 출력한다.

입출력 예

입력

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

출력

1 3 5
2 4

입력

6
1 2
1 1
0
1 5
2 4 6
1 5

출력

1 2 3 4 6
5

출처:제29회한국정보올림피아드(2012.7.13) 중등 3/4
special judge:ps1111