mb

#include<bits/stdc++.h>
#define inf 0x7fffffff
#define mod 998244353
#define ll long long
#define MaxM 500010
#define MaxN 100010
#define quickly ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
int head[MaxN],dis[MaxN],cnt;
bool vis[MaxN];
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-')
			w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*w;
}
//dijkstra:
struct edge{
	int to,dis,next;
}e[MaxM];
inline void add(int u,int v,int d){
	e[++cnt].dis=d;
	e[cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
struct node{
	int dis;
	int pos;
	bool operator <(const node &x)const{
		return x.dis < dis;
	}
};
std::priority_queue<node> q;
inline void dijkstra(){
	dis[1]=0;
	q.push((node){0,1});
	while(!q.empty()){
		node tmp=q.top();
		q.pop();
		int x=tmp.pos;
		//		int d=tmp.dis;
		if(vis[x])
			continue;
		vis[x]=1;
		for(int i=head[x];i;i=e[i].next){
			int y=e[i].to;
			if(dis[y]>dis[x]+e[i].dis){
				dis[y]=dis[x]+e[i].dis;
				if(!vis[y]){
					q.push((node){dis[y],y});
				}
			}
		}
	}
}
struct bcj{ 
	int len;      
	int q[30010],si[30010];           
	void init(int lenn){       
		len=lenn;
		for(int i=1;i<=len;i++)
			q[i]=i,si[i]=1;
	}
	int Find(int t){        
		if(q[t]==t) return t;
		int tt=Find(q[t]);
		q[t]=tt;
		return tt;
	}
	void add(int a,int b){  
		int a_1=Find(a),b_1=Find(b);
		q[a_1]=b_1;
		si[b_1]+=si[a_1];
	}
	int num(){
		int ans;
		for(int i=1;i<=len;i++)
			if(q[i]==i)
				ans++;
		return ans;
	}
	int Long(int a){
		return si[Find(a)];
	}
	bool same(int a,int b){
		int a_1=Find(a),b_1=Find(b);
		return a_1==b_1;
	}
};
int main(){
	//	freopen("a.in","r",stdin);
	//	freopen("a.out","w",stdout);
	
	
	return 0;
}