Informatica Online Judge

  재현이의 도미노 [1195 / 04AB]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 5   Total Tried : 12


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[CCC 2006 Day2]

Background

매우 많은 시간이 있는 재현이는 도미노를 가지고 기록을 세워 이름을 남기고 싶어 한다.

“가장 긴 도미노 체인” 기록을 깨기 위해 가장 긴 도미노 체인을 만들려고 하는데, 2개의 부분으로 나뉘어있는 도미노를 사용해야 한다.

아래 그림과 같이 도미노의 두 부분에는 주사위의 점 숫자와 같이, 수가 그려져 있는데, 서로 연결되는 부분의 수가 서로 같게 연결시켜야 하는 것이다.(2개의 도미노 4|5 4|6 이 있다면, 5|4 4|6 과 같은 방법으로 연결할 수 있다.)





재현이는 자기가 가지고 있는 도미노들을 사용해 체인을 만들려고 하는데, 가지고 있는 모든 도미노들을 모두 사용할 수는 없을 것 같다는 생각이 들었다.(1|2 4|5 만 있다면 연결을 못한다.)

가지고 있는 도미노들을 모두 연결하기 위해, 최소한의 도미노를 구입 할 수 있도록 재현이를 도와주자.

Input

첫 줄에 가지고 있는 도미노의 개수 n(1<= n <=10000)이 입력된다.

다음 줄 부터 n개의 도미노가 순서대로 입력되는데, A|B 도미노는 A B(0<= A <= B <=50000)로 입력된다.

Output

첫 줄에 재현이가 구입해야할 최소 도미노의 개수를 출력하고, 그 다음 줄부터 그 개수의 도미노를 A B 형태(A<=B)로 줄을 바꿔 출력한다.

단, 필요한 도미노가 0개 이면 출력하지 않고, 최소 도미노 개수로 여러 가지 경우가 있는 경우에는 구입할 도미노의 눈의 순으로 사전 순으로 가장 빠른 경우로 출력 한다.

IO Example

입력1
4
1 10
2 8
8 10
4 606

출력1
1
1 4

입력2
6
3 8
3 5
1 3
1 5
1 8
5 8

출력2
1
1 3

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]