2011 Canadian Computing Competition, Stage 2
Day 1, Problem 3: Spies Like Us
The Ultrasecret Spy Organization is very concerned about recent leads concerning a secret conspiracy involving the use of the Comic Sans font.
In order to avoid groupthink, the Ultrasecret Spy Organization has decided to divide its agents in two groups. Each of the two groups will carry its own investigation. However, occasionally interaction between members of different groups will happen through some previously designated contact points (i.e., two people on different teams that are allowed to speak with each other in special circumstances). This has to be made in a way that preserves the fact that there is not much communication between the teams. To make this rule more exact, two people on the same team can have no more than one common contact on the other team.
You are given a plan for the contact points between the two groups. Your task is to determine whether this actually satisfies the constraint that two people on the same team can have no more than one common contact in the other team.
The first line of the input file will contain two space-separated integers N and M (1 ≤ N, M ≤ 2000). They represent the number of people in each of the teams. The next line will contain an integer K (0 ≤ K ≤ NM). Each of the following K lines will contain two integers, i (1 ≤ i ≤ N) and j (1 ≤ j ≤ M). This input will represent that person i of the first team and person j of the second team are allowed to communicate with each other.
Note: For test cases worth 25% of the marks, you may assume N, M ≤ 200.
For each input, you will output one line. Its content will be
YES, if the proposal satifies the constraint that two people on the
same team can have no more than one common contact on the other team, and
5 3 4 1 1 2 1 3 1 4 1
Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 256M
Added: Jun 06, 2011
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3