#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long LL;
const int maxn = 100005;
#define fi first
#define se second
#define pb push_back

typedef pair<int,int> mp;
vector<int> a[maxn],b[maxn];
int p[maxn],sa[maxn],sb[maxn],n,que[maxn],tail;
int findp(int u) {return p[u]?p[u]=findp(p[u]):u;}
mp mkpr(int u,int v) {u=findp(u);v=findp(v);return u<v?mp(u,v):mp(v,u);}
map<mp,int> H;
queue<mp> Q;
void insert(mp w,int o) {if (H[w]!=3) {H[w]|=o;if (H[w]==3) Q.push(w);}}

int merge(int u,int v)
{
	u=findp(u);v=findp(v);
	if (u==v) return 0;
	if (sa[u]+sb[u]<sa[v]+sb[v]) swap(u,v);
	p[v]=u;sa[u]+=sa[v];sb[u]+=sb[v];
	for (int j=0;j<sa[v];j++) {
		int x=findp(a[v][j]);a[u].pb(x);
		if (x!=u) insert(mkpr(u,x),1);
	}
	for (int j=0;j<sb[v];j++) {
		int x=findp(b[v][j]);b[u].pb(x);
		if (x!=u) insert(mkpr(u,x),2);
	}
	return 1;
}
int main()
{
	#ifdef Amberframe
		freopen("agc014e.in","r",stdin);
		freopen("agc014e.out","w",stdout);
	#endif
	scanf("%d",&n);
	for (int u,v,i=1;i<n;i++)
		scanf("%d %d",&u,&v),a[u].pb(v),a[v].pb(u),insert(mkpr(u,v),1),sa[u]++,sa[v]++;
	for (int u,v,i=1;i<n;i++)
		scanf("%d %d",&u,&v),b[u].pb(v),b[v].pb(u),insert(mkpr(u,v),2),sb[u]++,sb[v]++;
	int cnt=0;
	while (!Q.empty()) {
		mp cur=Q.front();Q.pop();
		cnt+=merge(cur.fi,cur.se);
	}
	printf("%s",cnt==n-1?"YES":"NO");
	return 0;
}
### Prompt

Your task is to create 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 <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long LL;
const int maxn = 100005;
#define fi first
#define se second
#define pb push_back

typedef pair<int,int> mp;
vector<int> a[maxn],b[maxn];
int p[maxn],sa[maxn],sb[maxn],n,que[maxn],tail;
int findp(int u) {return p[u]?p[u]=findp(p[u]):u;}
mp mkpr(int u,int v) {u=findp(u);v=findp(v);return u<v?mp(u,v):mp(v,u);}
map<mp,int> H;
queue<mp> Q;
void insert(mp w,int o) {if (H[w]!=3) {H[w]|=o;if (H[w]==3) Q.push(w);}}

int merge(int u,int v)
{
	u=findp(u);v=findp(v);
	if (u==v) return 0;
	if (sa[u]+sb[u]<sa[v]+sb[v]) swap(u,v);
	p[v]=u;sa[u]+=sa[v];sb[u]+=sb[v];
	for (int j=0;j<sa[v];j++) {
		int x=findp(a[v][j]);a[u].pb(x);
		if (x!=u) insert(mkpr(u,x),1);
	}
	for (int j=0;j<sb[v];j++) {
		int x=findp(b[v][j]);b[u].pb(x);
		if (x!=u) insert(mkpr(u,x),2);
	}
	return 1;
}
int main()
{
	#ifdef Amberframe
		freopen("agc014e.in","r",stdin);
		freopen("agc014e.out","w",stdout);
	#endif
	scanf("%d",&n);
	for (int u,v,i=1;i<n;i++)
		scanf("%d %d",&u,&v),a[u].pb(v),a[v].pb(u),insert(mkpr(u,v),1),sa[u]++,sa[v]++;
	for (int u,v,i=1;i<n;i++)
		scanf("%d %d",&u,&v),b[u].pb(v),b[v].pb(u),insert(mkpr(u,v),2),sb[u]++,sb[v]++;
	int cnt=0;
	while (!Q.empty()) {
		mp cur=Q.front();Q.pop();
		cnt+=merge(cur.fi,cur.se);
	}
	printf("%s",cnt==n-1?"YES":"NO");
	return 0;
}
```