Team Arrangement with Bipartite Check

You are given a set of p people numbered from 1 to p, and c connections (each representing a relationship between two people). Additionally, an integer m is provided which indicates the intended number of teams. Your task is to determine if it is possible to arrange these people into teams such that no two people who are directly connected end up in the same team.

This problem reduces to checking whether the undirected graph formed by the connections is bipartite. A graph is bipartite if and only if it is possible to split the set of nodes into two disjoint groups such that every edge connects a node in one group to a node in the other.

Note: Although an integer m is given, the solution only requires checking the bipartite property of the graph.

The input is read from standard input and the output should be sent to standard output.

The answer should be YES if it is possible to arrange the teams under the given condition, and NO otherwise.

inputFormat

The first line contains three integers m, p, and c separated by spaces, representing the number of teams, the number of people, and the number of connections respectively. Each of the following c lines contains two integers u and v indicating that person u is connected to person v (and vice versa).

You can assume 1 ≤ u, v ≤ p.

outputFormat

Output a single line containing either YES or NO indicating whether the people can be arranged into teams such that no connected people are on the same team.

2 8 7
1 2
2 3
4 5
5 6
6 7
3 4
7 8

YES