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.

Input Format

The first line of the input file will contain two space-separated integers N and M (1 ≤ NM ≤ 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 NM ≤ 200.

Output Format

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 NO otherwise.

Sample Input

5 3
4
1 1
2 1
3 1
4 1

Sample Output

YES

All Submissions
Best Solutions


Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 256M
Added: Jun 06, 2011

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...