Профессор Икс проводит биологический эксперимент над n бактериями, которые находятся в трёх колбах, которые пронумерованы от 1 до 3. Эксперимент состоит из q этапов, на каждом из них профессор берёт одну бактерию из некоторой колбы и перемещает её в другую.
Логан нашёл записи о ходе эксперимента. Профессор записал, что изначально i-я бактерия находилась в колбе номер si, на j-ом этапе он переместил бактерию из колбы номер xj в колбу номер yj, а в конце эксперимента i-я бактерия оказалась в колбе ti. Профессор не записал, какие именно бактерии перемещались в ходе эксперимента.
Логану стало интересно, не ошибся ли Профессор в своих записях. Помогите ему определить, мог ли Профессор так перемещать бактерии, чтобы ход эксперимента соответствовал его записям.
В первой строке входного файла заданы числа n и q — количество бактерий и количество стадий эксперимента (1 ≤ n ≤ 50, 0 ≤ q ≤ 100).
В следующей стоке задано n чисел s1, ..., sn — начальное положение бактерий (1 ≤ si ≤ 3).
В следующей стоке задано n чисел t1, ..., tn — конечное положение бактерий (1 ≤ ti ≤ 3).
В следующих q строках описаны этапы эксперимента. На j-й из них заданы числа xj и yj, которые означают, что на j-ом этапе Профессор переместил бактерию из колбы номер xj в колбу номер yj (1 ≤ xj, yj ≤ 3, xj ≠ yj).
Никаких дополнительных ограничений на xi и yi не накладывается. В частности, не гарантируется, что перед i-м этапом в колбе xi будет хотя бы одна бактерия.
Выведите YES, если Профессор мог перемещать бактерии так, чтобы записи соответствовали действительности, или NO в противном случае.
Первая группа тестов состоит из тестов, для которых выполняются ограничения n, q ≤ 10. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 20 балл.
Вторая группа тестов состоит из тестов, для которых выполняются ограничения n ≤ 50, q ≤ 100, 1 ≤ si, ti, xi, yi ≤ 2. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 20 балл.
Третья группа тестов состоит из тестов, для которых выполняются полные ограничения. Баллы за эту группу начисляются только при прохождении всех тестов этой и предыдущих групп. Стоимость группы составляет 60 баллов.
3 2
1 2 2
1 3 2
2 1
1 3
YES
3 2
1 2 2
3 1 2
2 1
1 3
YES
3 2
1 2 2
1 3 3
2 1
1 3
NO
В первом тесте Профессор мог на обоих этапах перемещать бактерию номер 2.
Во втором тесте на первом этапе он переместил бактерию номер 2, а на втором — 1.