#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rg register

template <typename _Tp> inline _Tp read(_Tp&x){
	char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();
	while(isdigit(c11))x=x*10+c11-'0',c11=getchar();return x;
}

const int N=101000,ae=20;
struct Edge{int v,nxt;}a[N*ae*2];
int qx[N*ae],qy[N*ae],dad[N];
int head[N],_,sz[N];
int n,he=1,ta=0;

inline int find(int x){return dad[x]?dad[x]=find(dad[x]):x;}

inline void ins(int u,int v){++sz[u],a[++_].v=v,a[_].nxt=head[u],head[u]=_;}

map <ll,int> cnt;

#define h(x,y) (x+1ll*n*y)
inline void add(int x,int y){
	if(x>y)swap(x,y);
	ins(x,y),ins(y,x);
	if((++cnt[h(x,y)])==2)
		++ta,qx[ta]=x,qy[ta]=y;
}

int main(){
	read(n);int x,y,p;
	for(rg int i=n-2+n;i;--i)read(x),read(y),add(x,y);
	for(rg int i=1;i<n;++i){
		do	x=qx[he],y=qy[he],++he;
		while(find(x)==find(y)&&he<=ta);
		x=find(x),y=find(y);
		if(x==y){puts("NO");return 0;}
		if(sz[x]>sz[y])swap(x,y);
		--sz[y];cnt.erase(x<y?h(x,y):h(y,x));
		for(rg int j=head[x];j;j=a[j].nxt){
			p=find(a[j].v);
			if(p^y)if(p!=find(x))add(p,y);
		}
		dad[x]=y;
	}puts("YES");
}
### Prompt

Please create a solution in Cpp 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>
using namespace std;
typedef long long ll;
#define rg register

template <typename _Tp> inline _Tp read(_Tp&x){
	char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();
	while(isdigit(c11))x=x*10+c11-'0',c11=getchar();return x;
}

const int N=101000,ae=20;
struct Edge{int v,nxt;}a[N*ae*2];
int qx[N*ae],qy[N*ae],dad[N];
int head[N],_,sz[N];
int n,he=1,ta=0;

inline int find(int x){return dad[x]?dad[x]=find(dad[x]):x;}

inline void ins(int u,int v){++sz[u],a[++_].v=v,a[_].nxt=head[u],head[u]=_;}

map <ll,int> cnt;

#define h(x,y) (x+1ll*n*y)
inline void add(int x,int y){
	if(x>y)swap(x,y);
	ins(x,y),ins(y,x);
	if((++cnt[h(x,y)])==2)
		++ta,qx[ta]=x,qy[ta]=y;
}

int main(){
	read(n);int x,y,p;
	for(rg int i=n-2+n;i;--i)read(x),read(y),add(x,y);
	for(rg int i=1;i<n;++i){
		do	x=qx[he],y=qy[he],++he;
		while(find(x)==find(y)&&he<=ta);
		x=find(x),y=find(y);
		if(x==y){puts("NO");return 0;}
		if(sz[x]>sz[y])swap(x,y);
		--sz[y];cnt.erase(x<y?h(x,y):h(y,x));
		for(rg int j=head[x];j;j=a[j].nxt){
			p=find(a[j].v);
			if(p^y)if(p!=find(x))add(p,y);
		}
		dad[x]=y;
	}puts("YES");
}
```