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

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef pair<int,int> pii;
typedef set<int>::iterator it;
int n,fa[N],cnt;
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
set<int> *S[N],*T[N];
queue<pii> Q;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		fa[i]=i;
		S[i]=new set<int>();
		T[i]=new set<int>();
	}
	for (int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		S[u]->insert(v);
		S[v]->insert(u);
	}
	for (int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		if (S[u]->count(v)){
			Q.push(pii(u,v));
			S[u]->erase(v);
			S[v]->erase(u);
		}
		else{
			T[u]->insert(v);
			T[v]->insert(u);
		}
	}
	while (!Q.empty()){
		int u=Q.front().first,v=Q.front().second;Q.pop();
		u=find(u);v=find(v);
		//printf("merge(%d,%d)\n",u,v);
		cnt++;
		if (S[u]->size()+T[u]->size()<S[v]->size()+T[v]->size()) swap(u,v);
		fa[v]=u;
		for (it i=S[v]->begin();i!=S[v]->end();++i){
			int x=*i;
			S[x]->erase(v);
			if (T[u]->count(x)){
				Q.push(pii(u,x));
				T[u]->erase(x);
				T[x]->erase(u);
			}
			else{
				S[x]->insert(u);
				S[u]->insert(x);
			}
		}
		S[v]->clear();
		for (it i=T[v]->begin();i!=T[v]->end();++i){
			int x=*i;
			T[x]->erase(v);
			if (S[u]->count(x)){
				Q.push(pii(u,x));
				S[u]->erase(x);
				S[x]->erase(u);
			}
			else{
				T[u]->insert(x);
				T[x]->insert(u);
			}
		}
		T[v]->clear();
	}
	puts(cnt==n-1?"YES":"NO");
	return 0;
}