Хайди устала расшифровывать древние пророчества и решила отправиться в штаб, чтобы отдохнуть и попытаться снова. Разумеется, она не может выкорчевать дерево и взять его с собой, поэтому он сделала точный рисунок дерева на бумаге. Подумав ещё, она сделала ещё несколько рисунков, которых суммарно получилось n (по числу вершин в Древе Жизни) — кто знает что может случиться?
В самом деле, по пути назад Хайди была атакована группой зомби. Хотя она и смогла с ними справиться, рисункам был причинён очень странный урон: с i-й копии пропала вершина с номером i, вместе со всеми своими рёбрами. На каждом рисунке зомби также стёрли номера вершин и перенумеровали оставшиеся n - 1 вершину произвольными числами от 1 до n (по крайней мере, номера вершин всё ещё различны). Более того, рисунки были случайным образом переупорядочены.
Теперь Хайди хочет восстановить Древо Жизни по имеющемся у неё описаниям и рисункам (спискам рёбер).
Выходные данные
Если рисунки Хайди никак не могут описывать одно и то же дерево, то выведите NO. В противном случае выведите слово YES и n - 1 строку с описанием любого дерева, которое могло послужить первоисточником для рисунков Хайди. Для каждого ребра выведите два целых числа — индексы соединённых вершин. Если подходящих решений несколько, разрешается вывести любое.
| № | Входные данные | Выходные данные |
|
1
|
1
5 5
2
4 1
2 1
1
3 1
3
4 1
4 3
2 1
3
3 1
3 2
4 1
3
2 1
3 2
4 2
|
YES
2 5
4 2
3 2
5 1
|