#include <functional>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <queue>
#include <map>
#include <set>
using namespace std;
 
typedef pair<int, int> pii;
const int MAXN = 1e5 + 10;
 
int N;
int fa[MAXN];
set<int> Adj[MAXN];
queue<pii> dualEdges;
map<pii, int> edgeCnt;
 
int find(int x)
{
	if (x == fa[x])
		return x;
	return fa[x] = find(fa[x]);
}
 
inline void addEdge(int u, int v)
{
	Adj[u].insert(v), Adj[v].insert(u);
	if (u > v)
		swap(u, v);
	if (++edgeCnt[make_pair(u, v)] == 2)
		dualEdges.emplace(u, v);
}
 
int main()
{
	int u, v;
	cin >> N;
 
	for (int i = 1; i <= 2 * N - 2; i++)
		cin >> u >> v, addEdge(u, v);
	iota(&fa[0], &fa[N + 1], 0);
 
	for (int i = 1; i < N; i++)
	{
		int x = 0, y = 0;
		do
		{
			if (dualEdges.empty())
			{
				puts("NO");
				return 0;
			}
			tie(x, y) = dualEdges.front();
			dualEdges.pop();
			x = find(x), y = find(y);
		} while (x == y);
 
		if (Adj[x].size() > Adj[y].size())
			swap(x, y);
		fa[x] = y, Adj[x].erase(y), Adj[y].erase(x);
		edgeCnt.erase(make_pair(min(x, y), max(x, y)));
 
		for(int z : Adj[x])
		{
			z = find(z);
			edgeCnt[make_pair(min(x, z), max(x, z))]--;
			if(z == y)
				continue;
			Adj[z].erase(x);
			addEdge(y, z);
		}
	}
 
	puts("YES");
 
	return 0;
}
### Prompt

Please provide a cpp coded solution to the problem described below:

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 <functional>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <queue>
#include <map>
#include <set>
using namespace std;
 
typedef pair<int, int> pii;
const int MAXN = 1e5 + 10;
 
int N;
int fa[MAXN];
set<int> Adj[MAXN];
queue<pii> dualEdges;
map<pii, int> edgeCnt;
 
int find(int x)
{
	if (x == fa[x])
		return x;
	return fa[x] = find(fa[x]);
}
 
inline void addEdge(int u, int v)
{
	Adj[u].insert(v), Adj[v].insert(u);
	if (u > v)
		swap(u, v);
	if (++edgeCnt[make_pair(u, v)] == 2)
		dualEdges.emplace(u, v);
}
 
int main()
{
	int u, v;
	cin >> N;
 
	for (int i = 1; i <= 2 * N - 2; i++)
		cin >> u >> v, addEdge(u, v);
	iota(&fa[0], &fa[N + 1], 0);
 
	for (int i = 1; i < N; i++)
	{
		int x = 0, y = 0;
		do
		{
			if (dualEdges.empty())
			{
				puts("NO");
				return 0;
			}
			tie(x, y) = dualEdges.front();
			dualEdges.pop();
			x = find(x), y = find(y);
		} while (x == y);
 
		if (Adj[x].size() > Adj[y].size())
			swap(x, y);
		fa[x] = y, Adj[x].erase(y), Adj[y].erase(x);
		edgeCnt.erase(make_pair(min(x, y), max(x, y)));
 
		for(int z : Adj[x])
		{
			z = find(z);
			edgeCnt[make_pair(min(x, z), max(x, z))]--;
			if(z == y)
				continue;
			Adj[z].erase(x);
			addEdge(y, z);
		}
	}
 
	puts("YES");
 
	return 0;
}
```