#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l), i##end = (r);i <= i##end;++i)
#define pb insert
using std::cin; using std::cout;
const int maxn = 200200;
typedef long long ll;
typedef std::pair<int, int> pr;
std::set<int> s[2][maxn];
std::set<std::pair<int, int>> set;
int fa[maxn];
int n, x, y;
inline void ins(int x,int y,int id) {
	if(x != y) {
		s[id][x].emplace(y), s[id][y].emplace(x);
		if(s[!id][x].count(y)) set.emplace(std::min(x, y), std::max(x, y));
	}
}
inline void del(int x,int y,int id) {
	s[id][x].erase(y), s[id][y].erase(x);
	if(s[!id][x].count(y)) set.erase(pr(std::min(x, y), std::max(x, y)));
}
inline int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	rep(i, 1, n - 1) cin >> x >> y, ins(x, y, 0);
	rep(i, 1, n - 1) cin >> x >> y, ins(x, y, 1);
	int ans = 0;
	for(;set.size();) {
		pr p = * set.begin(); set.erase(set.begin()); ++ ans;
		int x = p.first, y = p.second;
		if(s[0][x].size() + s[1][x].size() < s[0][y].size() + s[1][y].size()) 
			std::swap(x, y);
		std::vector<int> v0(s[0][y].begin(), s[0][y].end()), v1(s[1][y].begin(), s[1][y].end());
		for(int i : v0) del(y, i, 0), ins(x, i, 0);
		for(int i : v1) del(y, i, 1), ins(x, i, 1);
		fa[y] = x;
	}
	cout << (ans == n - 1 ? "YES" : "NO") << '\n';
}

### Prompt

Generate a cpp solution to the following problem:

There is a tree with N vertices numbered 1 through N. The i-th of the N-1 edges connects vertices a_i and b_i.

Initially, each edge is painted blue. Takahashi will convert this blue tree into a red tree, by performing the following operation N-1 times:

* Select a simple path that consists of only blue edges, and remove one of those edges.
* Then, span a new red edge between the two endpoints of the selected path.



His objective is to obtain a tree that has a red edge connecting vertices c_i and d_i, for each i.

Determine whether this is achievable.

Constraints

* 2 ≤ N ≤ 10^5
* 1 ≤ a_i,b_i,c_i,d_i ≤ N
* a_i ≠ b_i
* c_i ≠ d_i
* Both input graphs are trees.

Input

Input is given from Standard Input in the following format:


N
a_1 b_1
:
a_{N-1} b_{N-1}
c_1 d_1
:
c_{N-1} d_{N-1}


Output

Print `YES` if the objective is achievable; print `NO` otherwise.

Examples

Input

3
1 2
2 3
1 3
3 2


Output

YES


Input

5
1 2
2 3
3 4
4 5
3 4
2 4
1 4
1 5


Output

YES


Input

6
1 2
3 5
4 6
1 6
5 1
5 3
1 4
2 6
4 3
5 6


Output

NO

### Response

```cpp
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l), i##end = (r);i <= i##end;++i)
#define pb insert
using std::cin; using std::cout;
const int maxn = 200200;
typedef long long ll;
typedef std::pair<int, int> pr;
std::set<int> s[2][maxn];
std::set<std::pair<int, int>> set;
int fa[maxn];
int n, x, y;
inline void ins(int x,int y,int id) {
	if(x != y) {
		s[id][x].emplace(y), s[id][y].emplace(x);
		if(s[!id][x].count(y)) set.emplace(std::min(x, y), std::max(x, y));
	}
}
inline void del(int x,int y,int id) {
	s[id][x].erase(y), s[id][y].erase(x);
	if(s[!id][x].count(y)) set.erase(pr(std::min(x, y), std::max(x, y)));
}
inline int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	rep(i, 1, n - 1) cin >> x >> y, ins(x, y, 0);
	rep(i, 1, n - 1) cin >> x >> y, ins(x, y, 1);
	int ans = 0;
	for(;set.size();) {
		pr p = * set.begin(); set.erase(set.begin()); ++ ans;
		int x = p.first, y = p.second;
		if(s[0][x].size() + s[1][x].size() < s[0][y].size() + s[1][y].size()) 
			std::swap(x, y);
		std::vector<int> v0(s[0][y].begin(), s[0][y].end()), v1(s[1][y].begin(), s[1][y].end());
		for(int i : v0) del(y, i, 0), ins(x, i, 0);
		for(int i : v1) del(y, i, 1), ins(x, i, 1);
		fa[y] = x;
	}
	cout << (ans == n - 1 ? "YES" : "NO") << '\n';
}

```