시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (언어별 추가 시간 없음) 256 MB 22 6 4 80.000%

문제

수원시에는 세 학교 A, B, C가 있는데, 다음과 같은 특징을 가지고 있다고 한다. 

특징 1. A, C는 남학생만 있는 남자고등학교이고, B는 여학생만 있는 여자고등학교이다. 

특징 2. 각 학교에는 N명의 학생들이 있다. 각 학생이 다니는 학교는 정확히 하나다. 

특징 3. 학생의 이름은 자신이 다니는 학교의 이름과 1과 N 사이의 수로 정해진 자신의 학번을 붙인 문자열이다. 즉, 

  • A에 다니는 학생들의 이름은 A1, A2, A3, A4, … AN이다. 
  • B에 다니는 학생들의 이름은 B1, B2, B3, B4,  … BN이다.
  • C에 다니는 학생들의 이름은 C1, C2, C3, C4, … CN이다. 

특징 4. 학생들은 자신과 다른 학교에 속한 학생들과 서로 친구 관계를 형성한다. 만약 학생 X가 학생 Y와 친구라면, 학생 Y도 학생 X와 친구이다.

특징 5. 만약 A 학교의 학생 a와 B 학교의 학생 b, 그리고 C 학교의 학생 c가 모두 서로 친구라면, 세 학생 a, b, c가 하나의 Love Triangle을 형성한다.

특징 6. 서로 다른 Love Triangle이 5개 이상 존재하면 세 학교가 폐교된다. 두 Love Triangle이 서로 다른 것은, Love Triangle을 이루는 학생의 집합이 서로 다른 것이다. 

이 상황을 지켜보던 관영이는, 세 학교가 폐교되지 않는다는 제한 아래에서 얼마나 많은 친구 관계가 형성될 수 있을지 궁금해졌다. 옆에 있던 규민이가 관영이에게 말하기를,

규민: “모든 학생이 각각 친구 관계를 N+1개 이상 가지고, 세 학교가 폐교되지 않는 경우도 있어! 모든 학생이 친구 관계 N+1개 이상이면 다들 완전 인싸인걸?”

관영이는 규민이의 말이 정말인지 궁금해졌다. 관영이를 위해 N=128인 경우에서 예시를 하나 들어주자.  

입력

A, B, C 각각에 다니는 학생 수 N=128이 입력된다. 

출력

모든 학생이 친구 관계를 N+1개 이상 가지고, 서로 다른 Love Triangle의 개수가 4개 이하인 경우의 예시를 다음 형식에 맞추어서 출력하시오. 

첫 줄에는 친구 관계의 수 E를 출력한다. 

둘째 줄부터 E+1번째 줄까지는 친구 관계를 형성한 두 학생의 이름을 사이에 공백으로 구분하여 각 줄에 출력한다.

예제 입력 1

1

예제 출력 1

3
A1 B1
B1 C1
C1 A1

A1, B1, C1 모두 친구 관계는 2개이고, Love Triangle은 1개 생겼다.

이 예제는 채점되지 않으며, 문제의 이해를 돕기 위하여 존재한다.  

예제 입력 2

2

예제 출력 2

10
A1 B1
A1 B2
A2 B1
A2 B2
B1 C1
B1 C2
B2 C1
B2 C2
C1 A1
C2 A2

A1, A2는 친구 관계가 3개.
B1, B2는 친구 관계가 4개.
C1, C2는 친구 관계가 3개다.

Love Triangle은 (A1, B1, C1), (A1, B2, C1), (A2, B1, C2), (A2, B2, C2)로 총 4개다. 

이 예제는 채점되지 않으며, 문제의 이해를 돕기 위하여 존재한다.  

채점

  • 예제는 채점하지 않는다.