Spies Like Us

Interview

Time limit2sMemory limit512 MB

Summary

Given a bipartite graph, decide whether any two vertices on the same side share at most one common neighbor on the other side.

Level: Medium5 of 10
Topics: Graph, Hash map, Implementation, Brute force
Solved: No attempts yet

Problem

An ultra-secret spy organization is worried about a hidden conspiracy. To avoid groupthink, the organization splits its agents into two teams, and each team runs its own investigation.

Occasionally, members of different teams must interact through pre-designated contact points: pairs of agents on opposite teams who are permitted to talk to each other under special circumstances. To keep communication between the teams limited, the organization enforces one rule.

Any two agents on the same team may have at most one common contact on the other team.

You are given the planned set of contact points between the two teams. Determine whether the plan satisfies this rule.

Input

The first line contains two space-separated integers $N$ and $M$ ( $1 \le N, M \le 2000$ ), the number of agents on the first and second teams, respectively.

The second line contains an integer $K$ ( $0 \le K \le N \cdot M$ ), the number of contact points.

Each of the next $K$ lines contains two integers $i$ and $j$ ( $1 \le i \le N$ , $1 \le j \le M$ ), meaning that agent $i$ of the first team and agent $j$ of the second team are allowed to communicate.

Output

Output a single line containing YES if the plan satisfies the rule that any two agents on the same team have at most one common contact on the other team, and NO otherwise.

Examples3

Example 1
Input
```
5 3
4
1 1
2 1
3 1
4 1
```
Expected output
```
YES
```
Example 2
Input
```
2 2
4
1 1
1 2
2 1
2 2
```
Expected output
```
NO
```
Example 3
Input
```
3 3
0
```
Expected output
```
YES
```