В Межзвездном Космоаналитическом Бюро очень удивились, узнав, что сообщение от космоаналитика на Сарке получено не было. Более того, самого космоаналитика нигде не могли найти... Не могли найти в течении целого года.
Через несколько недель на Флорине, неподалеку одной из кыртовых фабрик Валлона Марч нашла человека, потерявшего память. Его подвергли психозондированию, уничтожив часть его воспоминаний и спрятав остальные в глубинах сознания. Управляющий фабрикой, резидент Мирлин Теренс, разрешил Валлоне взять найденыша себе на попечение, добился для нее дополнительного пайка и талонов на одежду — сделал все, чтобы двое взрослых (из них один незарегистрированный) могли прожить на жалованье одного. Валлону такое положение вполне устраивало: красавицей она не была, поэтому пока остальные девушки нянчили собственных детей, Валлона занималась Риком — так назвали умалишенного (и поверьте, забот с ним поначалу было не меньше).
Через некоторое время к Рику начала постепенно возвращаться память, и пусть он ничего не помнил о своем прошлом, он уже работал на фабрике. И вот сегодня утром по дороге на свое рабочее место Рик столкнулся с Валлоной. Столкнулся в прямом смысле этого слова, потому что людей на фабрике было много, и все куда-то ужасно спешили, что сильно затрудняло перемещение. Фабрика представляет собой $n$ помещений, соединенных $n -1$ двусторонними коридорами таким образом, чтобы между любыми двумя помещениями существовал ровно один путь. Рик подумал: а что если утром сделать движение по всем коридорам односторонним, чтобы избежать подобных столкновений? Идея может и неплохая, но при этом из некоторых помещений нельзя будет добраться в удаленные части фабрики. А самому Рику, Валлоне, да и остальным рабочим надо было попасть в определенные места. Рику известно про $m$ человек, что с утра они должны дойти из помещения $s_i$ в помещение $f_i$, поэтому коридоры на их пути надо ориентировать таким образом, чтобы возможность перемещения из начала пути $s_i$ в конец $f_i$ не пропадала.
Сознание Рика еще не до конца прояснилось, поэтому он просит вас узнать, можно ли ориентировать все коридоры требуемым способом?
Первая строка содержит два числа $n$ и $m$ — количество помещений на фабрике и количество знакомых Рика $(1 <= n, m <= 2 dot.op 10^5)$.
В следующих $n -1$ строке заданы номера пар помещений $u_i, v_i$, соединенных коридорами $(1 <= u_i, v_i <= n)$. Гарантируется, что из каждого помещения фабрики можно добраться до каждого.
Следующие $m$ строк содержат числа $s_i$ и $f_i$ — начальные и конечные вершины путей, возможность перемещения по которым должна сохраниться.
Если ориентировать коридоры описанным образом невозможно, выведите "NO" (без кавычек). В противном случае в первой строке выведите "YES" (без кавычек), а в следующих $n -1$ строках — описание всех коридоров в любом порядке. Для каждого коридора выведите номера двух помещений, которые он соединяет, таким образом, чтобы из первого можно было перемещаться во второе.
Рассмотрим второй пример. Опишем пути всех знакомых Рика после того, как коридоры были проориентированы.
$6 arrow.r 2 arrow.r 1 arrow.r 3 arrow.r 10$
$13 arrow.r 11 arrow.r 4 arrow.r 1$
$5 arrow.r 1 arrow.r 3 arrow.r 9 arrow.r 12 arrow.r 14$
$15 arrow.r 12$
$2 arrow.r 8$
## Входные Данные
Первая строка содержит два числа $n$ и $m$ — количество помещений на фабрике и количество знакомых Рика $(1 <= n, m <= 2 dot.op 10^5)$.В следующих $n -1$ строке заданы номера пар помещений $u_i, v_i$, соединенных коридорами $(1 <= u_i, v_i <= n)$. Гарантируется, что из каждого помещения фабрики можно добраться до каждого.Следующие $m$ строк содержат числа $s_i$ и $f_i$ — начальные и конечные вершины путей, возможность перемещения по которым должна сохраниться.
## Выходные Данные
Если ориентировать коридоры описанным образом невозможно, выведите "NO" (без кавычек). В противном случае в первой строке выведите "YES" (без кавычек), а в следующих $n -1$ строках — описание всех коридоров в любом порядке. Для каждого коридора выведите номера двух помещений, которые он соединяет, таким образом, чтобы из первого можно было перемещаться во второе.
## Примеры
Входные данные5 5
2 1
4 1
5 3
3 4
1 2
5 3
5 4
1 4
3 4
Выходные данныеYES
1 2
1 4
3 4
5 3
Входные данные15 5
1 2
1 3
1 4
1 5
2 6
2 7
2 8
3 9
3 10
4 11
9 12
11 13
12 14
12 15
6 10
13 1
5 14
15 12
2 8
Выходные данныеYES
2 1
6 2
7 2
2 8
1 3
3 9
9 12
12 14
15 12
3 10
4 1
11 4
13 11
5 1
Входные данные5 5
1 3
5 1
4 2
3 4
4 3
4 3
3 2
1 2
5 4
Выходные данныеNO
## Примечание
Рассмотрим второй пример. Опишем пути всех знакомых Рика после того, как коридоры были проориентированы.$6 arrow.r 2 arrow.r 1 arrow.r 3 arrow.r 10$$13 arrow.r 11 arrow.r 4 arrow.r 1$$5 arrow.r 1 arrow.r 3 arrow.r 9 arrow.r 12 arrow.r 14$$15 arrow.r 12$$2 arrow.r 8$
[samples]
**Definitions**
Let $ S = \{P_1, P_2, \dots, P_n\} \subset \mathbb{Z}^2 $ be a finite set of distinct points in the 2D integer lattice, where $ P_i = (x_i, y_i) $.
The **Voronoi region** of point $ P_i $ is defined as:
$$
R_i = \left\{ K \in \mathbb{R}^2 \mid \forall j \in \{1, \dots, n\}, \; d(P_i, K) \leq d(P_j, K) \right\}
$$
where $ d(P_i, K) = |x_i - k_x| + |y_i - k_y| $ is the Manhattan distance.
A region $ R_i $ is **unbounded** if for every $ R > 0 $, there exists a point $ K \in R_i $ such that $ \|K\|_2 > R $ (i.e., it extends arbitrarily far from the origin).
**Constraints**
1. $ n \in \mathbb{Z} $, $ 1 \leq n \leq 100 $
2. For all $ i \in \{1, \dots, n\} $, $ x_i, y_i \in \mathbb{Z} $, $ |x_i|, |y_i| \leq 10^4 $
**Objective**
Compute the number of unbounded regions in the Manhattan-distance Voronoi diagram of $ S $.