#include <bits/stdc++.h>

#define NS (100005)
#define FIR first
#define SEC second

using namespace std;

typedef pair<int, int> PII;

template <typename _Tp> inline void IN(_Tp& dig)
{
	char c; bool flag = 0; dig = 0;
	while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
	while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
	if (flag) dig = -dig;
}

int n, fa[NS];

map<PII, int> mp;

set<int> g[NS];

queue<PII> que;

int findf(int a) {return fa[a] == a ? a : fa[a] = findf(fa[a]);}

int main(int argc, char const* argv[])
{
	IN(n);
	for (int i = 1; i <= n; i += 1) fa[i] = i;
	for (int i = 1, a, b; i < n; i += 1)
	{
		IN(a), IN(b);
		if (a > b) swap(a, b);
		mp[PII(a, b)]++;
		g[a].insert(b), g[b].insert(a);
	}
	for (int i = 1, a, b; i < n; i += 1)
	{
		IN(a), IN(b);
		if (a > b) swap(a, b);
		if (++mp[PII(a, b)] == 2) que.push(PII(a, b));
		g[a].insert(b), g[b].insert(a);
	}
	int cnt = 0;
	while (!que.empty())
	{
		int u = findf(que.front().FIR), v = findf(que.front().SEC); que.pop();
		if (g[u].size() > g[v].size()) swap(u, v);
		for (set<int>::iterator i = g[u].begin(); i != g[u].end(); i++)
			if (*i != v)
			{
				g[*i].erase(u), g[*i].insert(v), g[v].insert(*i);
				int a = *i, b = v;
				if (a > b) swap(a, b);
				if (++mp[PII(a, b)] == 2) que.push(PII(a, b));
			}
		g[v].erase(u), fa[u] = v, cnt++;
	}
	if (cnt == n - 1) puts("YES");
	else puts("NO");
	return 0;
}
### Prompt

Please formulate 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 NS (100005)
#define FIR first
#define SEC second

using namespace std;

typedef pair<int, int> PII;

template <typename _Tp> inline void IN(_Tp& dig)
{
	char c; bool flag = 0; dig = 0;
	while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
	while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
	if (flag) dig = -dig;
}

int n, fa[NS];

map<PII, int> mp;

set<int> g[NS];

queue<PII> que;

int findf(int a) {return fa[a] == a ? a : fa[a] = findf(fa[a]);}

int main(int argc, char const* argv[])
{
	IN(n);
	for (int i = 1; i <= n; i += 1) fa[i] = i;
	for (int i = 1, a, b; i < n; i += 1)
	{
		IN(a), IN(b);
		if (a > b) swap(a, b);
		mp[PII(a, b)]++;
		g[a].insert(b), g[b].insert(a);
	}
	for (int i = 1, a, b; i < n; i += 1)
	{
		IN(a), IN(b);
		if (a > b) swap(a, b);
		if (++mp[PII(a, b)] == 2) que.push(PII(a, b));
		g[a].insert(b), g[b].insert(a);
	}
	int cnt = 0;
	while (!que.empty())
	{
		int u = findf(que.front().FIR), v = findf(que.front().SEC); que.pop();
		if (g[u].size() > g[v].size()) swap(u, v);
		for (set<int>::iterator i = g[u].begin(); i != g[u].end(); i++)
			if (*i != v)
			{
				g[*i].erase(u), g[*i].insert(v), g[v].insert(*i);
				int a = *i, b = v;
				if (a > b) swap(a, b);
				if (++mp[PII(a, b)] == 2) que.push(PII(a, b));
			}
		g[v].erase(u), fa[u] = v, cnt++;
	}
	if (cnt == n - 1) puts("YES");
	else puts("NO");
	return 0;
}
```