Accommodation Arrangement

There are n persons. For each person, you are given whether the person is a student. In addition, for each student you are given whether they are going home (denoted by 1) or staying on campus (denoted by 0). A non‐student is considered a visitor. Every student owns a bed. However, each person must sleep in the bed of someone they directly know – note that a person cannot sleep in his/her own bed.

The acquaintances between persons are given as an undirected graph. A person can only sleep in the bed of a student if there exists an edge between the person and that student. Note that if the person is a student who is staying in school (i.e. not going home), he/she still cannot use his/her own bed.

Your task is to determine whether there exists an assignment such that every person needing a bed gets one. The persons needing a bed are:

• Every student staying on campus (flag 0).
• Every visitor (non-student).

The available beds belong to all students (regardless of whether they go home or not). Formally, let $$L$$ be the set of persons requiring bed and let $$R$$ be the set of students. For any person \(i \in L\) and any student \(j \in R\), an edge exists from \(i\) to \(j\) if and only if person \(i\) and person \(j\) are directly acquainted and (if \(i\) is a student) \(i\neq j\). Determine if a matching exists that covers all vertices in \(L\).

Input Format: The first line contains two integers \(n\) and \(m\) (\(1 \le n \le 10^5\), \(0 \le m \le 10^5\)), indicating the number of persons and the number of acquaintance pairs, respectively. Then \(n\) lines follow. The \(i\)th line contains two integers:

• \(t_i\): 1 if the \(i\)th person is a student, 0 otherwise.
• \(r_i\): if \(t_i=1\), then \(r_i\) is 0 if the student is staying on campus and 1 if they are going home; if \(t_i=0\), \(r_i\) can be 0 (and is ignored).

Then \(m\) lines follow, each containing two integers \(u\) and \(v\) (1-indexed) indicating that person \(u\) and person \(v\) know each other.

Output Format: Output a single line with either YES if there exists an assignment so that every person who needs a bed gets one, or NO otherwise.

Constraints and Notes:

• The relation of knowing is mutual.
• A person cannot sleep in his/her own bed.
• You may assume that the total number of persons requiring bed does not exceed the number of student beds; if it does, the answer is NO.

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) separated by a space.

1. Each of the next \(n\) lines contains two integers \(t_i\) and \(r_i\), where \(t_i\) is 1 if the \(i\)th person is a student (0 otherwise). If \(t_i = 1\), then \(r_i\) is 0 if the student stays on campus and 1 if the student goes home. For non-students, \(r_i\) is a placeholder and can be ignored.
2. Each of the next \(m\) lines contains two integers \(u\) and \(v\) indicating that person \(u\) and person \(v\) are directly acquainted.

outputFormat

Output a single line: YES if there exists an accommodation arrangement satisfying the condition, or NO if there is no such arrangement.

sample

3 2
1 1
1 0
0 0
1 2
2 3

YES