Cho một đồ thị vô hướng gồm \(N\) đỉnh và \(M\) cạnh. Mỗi đỉnh \(i\) được phép tô bằng một trong hai màu \(c_{i,1}\) và \(c_{i,2}\) cho trước (từ tập ba màu \(\{0, 1, 2\}\)). Yêu cầu hai đầu mỗi cạnh phải có màu khác nhau.

Hãy xác định xem có cách tô màu thỏa mãn hay không.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 10^5\), \(1 \le M \le 2 \cdot 10^5\)).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(a_i, b_i\) (\(0 \le a_i < b_i \le 2\)), hai màu được phép cho đỉnh \(i\).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) (\(1 \le u < v \le N\)) mô tả một cạnh.

Định dạng đầu ra

• In ra YES nếu có cách tô màu, NO nếu không.

Ví dụ

Input:

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

Output:

YES