Love Triangles
Time limit1sMemory limit256 MB
Build a tripartite friendship graph on 128 students per school where every student has at least 129 friends and at most four love triangles exist.
- Level
Medium7 of 10
- Topics
- Graph, Combinatorics, Math
- Solved
- No attempts yet
Problem
There are three schools in Suwon, A, B, and C, with the following features.
Feature 1. A and C are all-boys high schools, and B is an all-girls high school.
Feature 2. Each school has students. Each student attends exactly one school.
Feature 3. A student's name is the school name followed by a student number from 1 to . That is, students at A are named A1, A2, A3, A4, ..., AN; students at B are named B1, B2, B3, B4, ..., BN; and students at C are named C1, C2, C3, C4, ..., CN.
Feature 4. Students form friendships with students at the other schools. If student X is friends with student Y, then Y is also friends with X.
Feature 5. If student a at A, student b at B, and student c at C are all friends with each other, then a, b, and c form a Love Triangle.
Feature 6. If five or more distinct Love Triangles exist, all three schools are closed. Two Love Triangles are distinct if the sets of students forming them differ.
Guan-young watched this situation and wondered how many friendships could form while the three schools stay open. Gyu-min, who was standing beside him, said:
Gyu-min: “There is a case where every student has at least friends and all three schools stay open! If everyone has or more friends, they are all completely popular, right?”
Guan-young wondered whether Gyu-min was right. For , give one example to help him.
Input
The number of students at each of schools A, B, and C is given as input.
Output
Print an example in which every student has at least friendships and the number of distinct Love Triangles is at most 4, in the following format.
On the first line, print the number of friendships . From the second line through line , print the names of two friends separated by a space, one pair per line.