Поликарпу недавно подарили набор из \(n\) (число \(n\) — чётное) костяшек домино. На каждой костяшке написаны два целых числа от \(1\) до \(n\).
Сможет ли он разделить все костяшки на два набора так, чтобы все числа на костяшках каждого набора были различны? Каждая костяшка должна войти ровно в один из двух наборов.
Например, если у него есть \(4\) костяшки: \(\{1, 4\}\), \(\{1, 3\}\), \(\{3, 2\}\) и \(\{4, 2\}\), то Поликарп сможет разделить их на два набора требуемым образом. В первый набор может войти первая и третья костяшка (\(\{1, 4\}\) и \(\{3, 2\}\)), а во второй — вторая и четвёртая (\(\{1, 3\}\) и \(\{4, 2\}\)).
Выходные данные
Для каждого набора входных данных выведите:
- YES, если возможно разделить \(n\) костяшек на два набора так, что числа на костяшках каждого набора различны;
- NO, если сделать это невозможно.
Вы можете выводить YES и NO в любом регистре (например, строки yEs, yes, Yes и YES будут распознаны как положительный ответ).
Примечание
В первом наборе входных данных костяшки можно разделить так:
- Первый набор: \([\{1, 2\}, \{4, 3\}]\)
- Второй набор: \([\{2, 1\}, \{3, 4\}]\)
Иными словами в первый набор берём костяшки с номерами
\(1\) и
\(2\), а во второй набор берём костяшки с номерами
\(3\) и
\(4\).
Во втором наборе входных данных как костяшки не раздели на \(2\) набора, хотя бы в одном будут повторяющиеся числа.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
4
1 2
4 3
2 1
3 4
6
1 2
4 5
1 3
4 6
2 3
5 6
2
1 1
2 2
2
1 2
2 1
8
2 1
1 2
4 3
4 3
5 6
5 7
8 6
7 8
8
1 2
2 1
4 3
5 3
5 4
6 7
8 6
7 8
|
YES
NO
NO
YES
YES
NO
|