/*
　Hi,I am warabi.
 
 Welcome to my coding space.
 Let me give you a great word of advice.
 
 "The pen is mightier than the sword" 
            -by Edward Bulwer-Lytton
 
　　_,,....,,_　 ＿人人人人人人人人人人人人人人人人人人＿
-''":::::::::::::｀''＞　　　ゆっくりできるとでも?　　＜
ヽ:::::::::::::::::::::￣^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ￣
　|::::::;ノ´￣＼:::::::::::＼_,. -‐ｧ　　　　　＿_　　 _____　　 ＿_____
　|::::ﾉ　　　ヽ､ヽr-r'"´　　（.__　　　　,´　_,, '-´￣￣｀-ゝ 、_ イ、
_,.!イ_　　_,.ﾍｰｧ'二ﾊ二ヽ､へ,_7　　　'r ´　　　　　　　　　　ヽ、ﾝ、
::::::rｰ''7ｺ-‐'"´　 　 ;　 ',　｀ヽ/｀7　,'＝=─-　　　 　 -─=＝',　i
r-'ｧ'"´/　 /!　ﾊ 　ハ　 !　　iヾ_ﾉ　i　ｲ　iゝ、ｲ人レ／_ルヽｲ i　|
!イ´ ,' |　/__,.!/　V　､!__ﾊ　 ,'　,ゝ　ﾚﾘｲi (ﾋ_] 　　 　ﾋ_ﾝ ).| .|、i .||
`! 　!/ﾚi'　(ﾋ_] 　　 　ﾋ_ﾝ ﾚ'i　ﾉ　　　!Y!""　  ,＿__, 　 "" 「 !ﾉ i　|
,'　 ﾉ 　 !'"　   ,＿__,　 "' i .ﾚ'　　　　L.',. ヽ _ﾝ　　　　L」 ﾉ| .|
　（　　,ﾊ　　　　ヽ _ﾝ　 　人! 　　　　 | ||ヽ、　　　　　　 ,ｲ| ||ｲ| /
,.ﾍ,）､　　）＞,､ _____,　,.イ　 ハ　　　　レ ル｀ ー--─ ´ルﾚ　ﾚ´
 
　Take your time.
　
　GIVE ME AC!!!!!!!!!!!!!!!!!!!!!!!!!
　
*/
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define V vector
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define brep(i,a,b) for(ll i=a;i>=b;i--)
#define reph(i,vec) for(auto &i:vec)
#define FI first
#define SE second
#define P pair
#define PB push_back
#define INS insert
#define all(vec) vec.begin(),vec.end()
#define in(name) ll name;cin >> name
#define ins(name) string name;cin >> name;
#define inc(name) char name;cin >> name
#define ing(name,size,E) vector<vector<ll>> name(size);rep(i,0,E){in(a);in(b);a--;b--;name[a].PB(b);name[b].PB(a);}
#define ing_on(name,size,E) vector<vector<long long>> name(size);rep(i,0,E){in(a);in(b);a--;b--;name[a].PB(b);}
#define ing_cost(name,size,E) vector<vector<P<ll,ll>>> name(size);rep(i,0,E){in(a);in(b);in(c);a--;b--;name[a].PB({b,c});name[b].PB({a,c});}
#define invll(name,size) vector<ll> name(size);reph(i,name)cin >> i
#define invvll(name,size1,size2) vector<vector<long long>> name(size1,vector<long long>(size2));reph(v,name)reph(i,v)cin>>i;
#define invp(name,size) vector<P<ll,ll>> name(size);for(ll i=0;i<size;i++)cin >> name[i].FI >> name[i].SE
#define out(n) cout << (n) << endl
#define _out(n) cout << " " << (n) << endl;
#define notout(n) cout << (n)
#define out_(n) cout << (n) << " "
#define set_out(n,k) cout << fixed << setprecision(k) << (n) << endl;
#define set_notout(n,k) cout << fixed << setprecision(k) << (n) << endl;
#define set_out_(n,k) cout << fixed << setprecision(k) << (n) << " ";
#define vout(vec) for(int i=0;i<vec.size();i++)cout<<(i?" ":"")<<(vec[i]);cout<<endl;
#define nl cout << endl
#define getbit(n,k) (((1LL<<(k))&(n))>0)

#define INF 1000000000000000000
#define MOD 1000000007
#define MOD2 998244353
#define CMOD MOD2
#define EPS 0.00000001

//debug
#define bug assert(false);
#define debug out("this point ok");
//

//constexpr long double PI=3.14159265358979323846;
 
//template
template<typename T>
inline bool chmax(T &a,const T b){if(a<b){a=b;return true;}return false;}
template<typename T>
inline bool chmin(T &a,const T b){if(a>b){a=b;return true;}return false;}
//

namespace Warabi{

//常備変数のコーナー
V<bool> primes(3001000,true);
V<ll> prime_list;
V<ll> prime_rui(3001000,0LL);
V<bool> visiteded(300100);
V<bool> afed(300100,false);
V<ll> k1(200100,0ll);
V<ll> k2(200100,0ll);
//
 
//常備構造体宣言のコーナー
class UnionFind {
private:
    ll NumberOfElements;
    ll Not1NumberOfelements;
public:
	vector<ll> par;
	vector<ll> SIZE;
 
	void init(ll sz) {
		par.resize(sz, -1LL);
		SIZE.resize(sz,1LL);
		NumberOfElements=sz;
		Not1NumberOfelements=0ll;
	}
	ll root(ll pos) {
		if (par[pos] == -1) return pos;
		par[pos] = root(par[pos]);
		return par[pos];
	}
	bool same(ll u, ll v) {
		if (root(u) == root(v)) return true;
		return false;
	}
	ll SZ(ll u){
	    return SIZE[root(u)];
	}
	ll noe(){
	    return NumberOfElements;
	}
	ll nnoe(){
	    return Not1NumberOfelements;
	}
	bool unite(ll u, ll v) {
		u = root(u); v = root(v);
		if (u == v) return false;
		if(SZ(u) == 1LL and SZ(v) == 1LL)Not1NumberOfelements++;
		par[u] = v;
		SIZE[v] += SIZE[u];
		NumberOfElements--;
		return true;
	}
};
 
class SCC{
    public:
    V<V<ll>> G;
    V<V<ll>> UG;
    V<ll> order;
    V<ll> GROUP;
    V<bool> visited;
    ll sz_count;
    V<ll> groupsize;
    
    void init(ll sz){
        G.resize(sz,V<ll>(0));
        UG.resize(sz,V<ll>(0));
        GROUP.resize(sz,-1ll);
        visited.resize(sz,false);
        sz_count=0LL;
        return;
    }
    
    void dfs(ll now){
        visited[now]=true;
        reph(i,G[now]){
            if(visited[i])continue;
            dfs(i);
        }
        order.PB(now);
        return;
    }
    
    void dfs2(ll now,ll group){
        GROUP[now]=group;
        sz_count++;
        reph(i,UG[now]){
            if(GROUP[i]!=-1ll and GROUP[i]!=group)continue;
            if(GROUP[i]!=-1ll)continue;
            dfs2(i,group);
        }
        return;
    }
    
    void make_group(V<V<ll>> Graph_function){
        G=Graph_function;
        rep(i,0,(ll)G.size()){
            reph(j,G[i]){
                UG[j].PB(i);
            }
        }
        rep(i,0,(ll)G.size()){
            if(visited[i])continue;
            dfs(i);
        }
        reverse(all(order));
        ll now_group=0LL;
        reph(i,order){
            if(GROUP[i]!=-1)continue;
            ll prev=sz_count;
            dfs2(i,now_group);
            now_group++;
            groupsize.PB(sz_count-prev);
        }
        return;
    }
};
 
template<typename X,typename M>
class SegmentTree{
    public:
    long long sz;
    using FX=function<X(X,X)>;
    using FA=function<X(X,M)>;
    using FM=function<M(M,M)>;
    const FX fx;
    const FA fa;
    const FM fm;
    const X ex;
    const M em;
    vector<X> node;
    vector<M> lazy;
    SegmentTree(long long sz_,FX fx_,FA fa_,FM fm_,X ex_,M em_):sz(),fx(fx_),fa(fa_),fm(fm_),ex(ex_),em(em_){
        long long n=1LL;
        while(n<sz_)n*=2;
        sz=n;
        node.resize(sz*2-1,ex);
        lazy.resize(sz*2-1,em);
    }
    void set(long long index,X x){
        node[index+sz-1]=x;
        return;
    }
    void build(){
        for(int i=sz-2;i>=0;i--)node[i]=fx(node[i*2+1],node[i*2+2]);
        return;
    }
    void eval(long long k){
        if(lazy[k]==em)return;
        if(k<sz-1){
            lazy[k*2+1]=fm(lazy[k*2+1],lazy[k]);
            lazy[k*2+2]=fm(lazy[k*2+2],lazy[k]);
        }
        node[k]=fa(node[k],lazy[k]);
        lazy[k]=em;
    }
    void update_sub(long long a,long long b,M x,long long k,long long l,long long r){
        //cout << " " << a << " " << b << " " << l << " " << r << endl;
        eval(k);
        if(a<=l and r<=b){
            lazy[k]=fm(lazy[k],x);
            //cout<<" "<<lazy[k]<<endl;
            eval(k);
            return;
        }
        else if(a<r and l<b){
            update_sub(a,b,x,k*2+1,l,(l+r)/2);
            update_sub(a,b,x,k*2+2,(l+r)/2,r);
            node[k]=fx(node[k*2+1],node[k*2+2]);
            return;
        }
        return;
    }
    void update(long long a,long long b,M x){
        update_sub(a,b,x,0LL,0LL,sz);
        return;
    }
    void add_sub(long long a,X x,long long k,long long l,long long r){
        eval(k);
        node[k]+=x;
        if(k<sz-1){
            long long mid=(l+r)/2;
            if(a<mid)add_sub(a,x,k*2+1,l,mid);
            else add_sub(a,x,k*2+2,mid,r);
        }
        return;
    }
    void add(long long a,X x){
        add_sub(a,x,0LL,0LL,sz);
    }
    X query_sub(long long a,long long b,long long k,long long l,long long r){
        eval(k);
        if(r<=a or b<=l)return ex;
        else if(a<=l and r<=b)return node[k];
        else{
            X Xl=query_sub(a,b,k*2+1,l,(l+r)/2);
            X Xr=query_sub(a,b,k*2+2,(l+r)/2,r);
            //cout<<" / "<<Xl<<" "<<Xr<<endl;
            return fx(Xl,Xr);
        }
    }
    X query(long long a,long long b){
        return query_sub(a,b,0LL,0LL,sz);
    }
    inline X operator [] (long long index){
        return query(index,index+1);
    }
};

template<typename T>
class multimap{
    private:
    map<T,ll> mp;
    public:
    void add(ll x){
        mp[x]++;
        return;
    }
    void del(ll x){
        mp[x]--;
        if(mp[x]<1)mp.erase(x);
        return;
    }
    T maximum(){
        return mp.rbegin()->first;
    }
    T minimum(){
        return mp.begin()->first;
    }
};

class LCA{
    public:
    vector<vector<long long>> parent;
    vector<long long> dist;
    vector<vector<long long>> G;
    LCA(const vector<vector<long long>> &gr){init(gr);}
    void dfs(long long v,long long p,long long d){
        parent[0][v]=p;
        dist[v]=d;
        for(long long next : G[v]){
            if(next==p)continue;
            dfs(next,v,d+1);
        }
        return;
    }
    void init(const vector<vector<long long>> &gr){
        G=gr;
        parent.assign(33,vector<long long>(G.size(),-1LL));
        dist.assign(G.size(),-1LL);
        dfs(0LL,-1LL,0LL);
        for(int i=0;i<32;i++){
            for(int j=0;j<(int)G.size();j++){
                if(parent[i][j]<0LL){
                    parent[i+1][j]=-1LL;
                }
                else{
                    parent[i+1][j]=parent[i][parent[i][j]];
                }
            }
        }
        return;
    }
    long long lca(long long u,long long v){
        if(dist[u]<dist[v])swap(u,v);
        long long between=dist[u]-dist[v];
        for(int i=0;i<33;i++){
            if(between&(1LL<<i)){u=parent[i][u];}
        }
        if(u==v)return u;
        for(int i=32;i>=0;i--){
            if(parent[i][u]!=parent[i][v]){
                u=parent[i][u];
                v=parent[i][v];
            }
        }
        assert(parent[0][u]==parent[0][v]);
        return parent[0][u];
    }
    long long get_dist(long long u,long long v){
        return dist[u]+dist[v]-2*dist[lca(u,v)];
    }
    bool on_path(long long u,long long v,long long a){
        return get_dist(u,v)==get_dist(u,a)+get_dist(v,a);
    }
};

class nCk {
public:
	const long long m;
	const long long MAXIMUM = 1000000;
	vector<long long> fac, facinv, inv;
	nCk(long long m_);
	~nCk();
	long long com(long long n, long long k)const;
	long long com_(vector<long long> vec)const;
};
nCk::nCk(long long m_):m(m_) {
	fac.resize(MAXIMUM + 3);
	facinv.resize(MAXIMUM + 3);
	inv.resize(MAXIMUM + 3);
	fac[0] = fac[1] = 1;
	facinv[0] = facinv[1] = 1;
	inv[1] = 1;
	for (long long i = 2; i < MAXIMUM + 2; i++) {
		fac[i] = fac[i - 1] * i % m;
		inv[i] = m - inv[m % i] * (m / i) % m;
		facinv[i] = facinv[i - 1] * inv[i] % m;
	}
}
nCk::~nCk(){}
long long nCk::com(long long n, long long k)const {
    if(k==0)return 1;
	if (n < k)return 0LL;
	assert(!(n < 0 || k < 0));
	return fac[n] * (facinv[k] * facinv[n - k] % m) % m;
}
long long nCk::com_(vector<long long> vec)const{
    long long sz=(long long)vec.size();
    long long sum=0LL;
    for(const long long v:vec)sum+=v;
    long long res=1LL;
    for(long long i=0;i<sz;i++){
        res*=com(sum,vec[i]);
        res%=m;
        sum-=vec[i];
    }
    return res;
}

//
 
//常備構造体宣言のコーナー
struct STC{
    ll s,t,cost;
};
//
 
 
//常備関数のコーナー
void Yes(bool f){cout<<(f?"Yes":"No")<<endl;}
void YES(bool f){cout<<(f?"YES":"NO")<<endl;}

 //木の直径を求める
STC Cdiameter(V<V<P<ll,ll>>> G,ll start,bool type){
    visiteded=afed;
    queue<ll> sirabe;
    sirabe.push(start);
    V<ll> short_load(G.size(),0LL);
    while(!sirabe.empty()){
        ll s=sirabe.front();
        sirabe.pop();
        visiteded[s]=true;
        reph(i,G[s]){
            if(visiteded[i.FI])continue;
            short_load[i.FI]=short_load[s]+i.SE;
            sirabe.push(i.FI);
        }
    }
    ll far_max=-1LL;
    ll element=-1LL;
    rep(i,0,(ll)G.size()){
        if(far_max>=short_load[i])continue;
        far_max=short_load[i];
        element=i;
    }
    if(type)return Cdiameter(G,element,false);
    else return {start,element,far_max};
}
 //素数の取得
void prime_init(){
    V<bool> at(3001000,true);
    primes=at;
    primes[0]=primes[1]=false;
    rep(i,2,3000100){
        if(!primes[i])continue;
        for(ll j=i*2;j<=300100;j+=i)primes[j]=false;
    }
    rep(i,1,3000100){
        if(primes[i]){
            prime_list.PB(i);
            prime_rui[i]=prime_rui[i-1]+1;
        }
        else{
            prime_rui[i]=prime_rui[i-1];
        }
    }
    return;
}
 
 //modpow
long long modpow(long long a, long long b, long long m) {
	long long p = 1, q = a;
	for (int i = 0; i < 63; i++) {
		if ((b & (1LL << i)) != 0) {
			p *= q;
			p %= m;
		}
		q *= q;
		q %= m;
	}
	return p;
}
 
 //逆元
long long Div(long long a, long long b, long long m) {
	return (a * modpow(b, m - 2, m)) % m;
}

 //点と点の距離を返す
long double Dis(ll ax,ll ay,ll bx,ll by){
    return sqrt(pow(ax-bx,2)+pow(ay-by,2));
}
 
 //二つのベクトルから平行四辺形の面積を返す
ll he(ll x0,ll y0,ll x1,ll y1,ll x2,ll y2){//外積を二で割る
    return abs((x1-x0)*(y2-y0)-(x2-x0)*(y1-y0));
}
//
 


template<typename T>
ll Lis_size(V<T> arr,ll sz){
    const T TINF=numeric_limits<T>::max();
    V<T> DP(sz+1,TINF);
    DP[0]=-TINF;
    rep(i,0,sz){
        *lower_bound(all(DP),arr[i])=arr[i];
    }
    ll ans=0LL;
    rep(i,1,sz+1){
        if(DP[i]!=TINF)ans=i;
    }
    return ans;
}
 
string toBinary(ll n){
    string r;
    while (n != 0LL){
        r += ( n % 2LL == 0LL ? "0" : "1" );
        n /= 2LL;
    }
    return r;
}
 
template<typename T>
V<ll> press(V<T> arr){
    V<T> X=arr;
    sort(all(X));
    X.erase(unique(all(X)),X.end());
    V<ll> ans(arr.size());
    rep(i,0LL,(ll)arr.size()){
        ans[i]=lower_bound(all(X),arr[i])-X.begin();
    }
    return ans;
}
 
P<V<V<ll>>,V<V<P<ll,ll>>>> warshall_floyd(ll N,V<V<P<ll,ll>>> G){
    V<V<ll>> DP(N,V<ll>(N,INF));
    rep(i,0,N)DP[i][i]=0LL;
    V<V<P<ll,ll>>> prev(N,V<P<ll,ll>>(N,{INF,INF}));
    rep(i,0,N){
        reph(j,G[i]){
            DP[i][j.FI]=j.SE;
            prev[i][j.FI]={i,j.FI};
        }
    }
    rep(k,0,N){
        rep(i,0,N){
            rep(j,0,N){
                if(chmin(DP[i][j],DP[i][k]+DP[k][j])){
                    prev[i][j]=prev[k][j];
                }
            }
        }
    }
    return {DP,prev};
}

template<typename T>
void to_sum(V<T> &arr){
    rep(i,0,(ll)arr.size()-1LL){
        arr[i+1]+=arr[i];
    }
    return;
}

template<typename T>
void including_map(ll H,ll W,V<V<T>> &G,T c){
    V<V<T>> new_G(H+2,V<T>(W+2));
    rep(i,0,W+2)new_G[0][i]=c;
    rep(i,1,H+1){
        new_G[i][0]=c;
        new_G[i][W+1]=c;
        rep(j,1,W+1){
            new_G[i][j]=G[i-1][j-1];
        }
    }
    rep(i,0,W+2)new_G[H+1][i]=c;
    G=new_G;
    return;
}
struct BIT {
  private:
   vector<int> bit;
   int N;
 
  public:
   BIT(int size) {
     N = size;
     bit.resize(N + 1);
   }
 
   // 一点更新です
   void add(int a, int w) {
     for (int x = a; x <= N; x += x & -x) bit[x] += w;
   }
 
   // 1~Nまでの和を求める。
   int sum(int a) {
     int ret = 0;
     for (int x = a; x > 0; x -= x & -x) ret += bit[x];
     return ret;
   }
 };
ll fall_down(ll n,const V<ll> &v){
    ll ans = 0;
   BIT b(n);  // これまでの数字がどんな風になってるのかをメモる為のBIT
   for (int i = 0; i < n; i++) {
     ans += i - b.sum(v[i]); // BITの総和 - 自分より左側 ＝ 自分より右側
     b.add(v[i], 1); // 自分の位置に1を足す
   }
   return ans;
}

set<ll> factor(ll N){
    set<ll> ans;
    for(ll i=1LL;i*i<=N;i++){
        if(N%i)continue;
        ans.INS(i);
        ans.INS(N/i);
    }
    return ans;
}

V<ll> dijkstra(ll sz,V<V<P<ll,ll>>> G,ll s){
    V<ll> ans(sz,INF);ans[s]=0LL;
    priority_queue<P<ll,ll>,vector<P<ll,ll>>,greater<P<ll,ll>>> examine;
    examine.push({0LL,s});
    while(examine.size()){
        P<ll,ll> p=examine.top();
        examine.pop();
        ll now=p.SE,dist=p.FI;
        if(ans[now]<dist)continue;
        reph(i,G[now]){
            ll next=i.FI,c=i.SE;
            if(chmin(ans[next],dist+c)){
                examine.push({dist+c,next});
            }
        }
    }
    return ans;
}

set<ll> pass(const V<V<ll>> &G,ll s,ll t){
    V<bool> visited(G.size(),false);
    set<ll> ans,res;
    function<void(ll)> dfs=[&](ll now){
        visited[now]=true;
        res.INS(now);
        if(now==t){
            ans=res;
        }
        reph(next,G[now]){
            if(visited[next])continue;
            dfs(next);
        }
        res.erase(now);
        return;
    };
    dfs(s);
    return ans;
}

// 負の数にも対応した mod (a = -11 とかでも OK)
inline long long mod(long long a, long long m) {
    long long res = a % m;
    if (res < 0) res += m;
    return res;
}

// 拡張 Euclid の互除法
long long extGCD(long long a, long long b, long long &p, long long &q) {
    if (b == 0) { p = 1; q = 0; return a; }
    long long d = extGCD(b, a%b, q, p);
    q -= a/b * p;
    return d;
}
long long extGcd(long long a, long long b, long long &p, long long &q) {  
    if (b == 0) { p = 1; q = 0; return a; }  
    long long d = extGcd(b, a%b, q, p);  
    q -= a/b * p;  
    return d;  
}
// 逆元計算 (ここでは a と m が互いに素であることが必要)
long long modinv(long long a, long long m) {
    long long x, y;
    extGCD(a, m, x, y);
    return mod(x, m); // 気持ち的には x % m だが、x が負かもしれないので
}

// Garner のアルゴリズム, x%MOD, LCM%MOD を求める (m は互いに素でなければならない)
// for each step, we solve "coeffs[k] * t[k] + constants[k] = b[k] (mod. m[k])"
//      coeffs[k] = m[0]m[1]...m[k-1]
//      constants[k] = t[0] + t[1]m[0] + ... + t[k-1]m[0]m[1]...m[k-2]
long long Garner(vector<long long> b, vector<long long> m, long long Mmod) {
    m.push_back(Mmod); // banpei
    vector<long long> coeffs((int)m.size(), 1);
    vector<long long> constants((int)m.size(), 0);
    for (int k = 0; k < (int)b.size(); ++k) {
        long long t = mod((b[k] - constants[k]) * modinv(coeffs[k], m[k]), m[k]);
        for (int i = k+1; i < (int)m.size(); ++i) {
            (constants[i] += t * coeffs[i]) %= m[i];
            (coeffs[i] *= m[k]) %= m[i];
        }
    }
    return constants.back();
}
pair<long long, long long> ChineseRem(const vector<long long> &b, const vector<long long> &m) {
  long long r = 0, M = 1;
  for (int i = 0; i < (int)b.size(); ++i) {
    long long p, q;
    long long d = extGcd(M, m[i], p, q); // p is inv of M/d (mod. m[i]/d)
    if ((b[i] - r) % d != 0) return make_pair(0, -1);
    long long tmp = (b[i] - r) / d * p % (m[i]/d);
    r += M * tmp;
    M *= m[i]/d;
  }
  return make_pair(mod(r, M), M);
}

map<ll,ll> bunkai(ll n){
    map<ll,ll> ans;
    for(int i=2;i*i<=n;i++){
        while(n%i==0){
            if(n!=i)ans[n/i]++;
            n/=i;
            ans[i]++;
        }
    }
    if(n>1)ans[n]++;
    return ans;
}

}
//

//構造体宣言のコーナー
struct P2{
    ll l,r;
};
bool operator < (P2 a,P2 b){
    if(a.r<b.r)return true;
    if(a.r==b.r and a.l<b.l)return true;
    return false;
}

long long gcd(long long a,long long b){
    if(b==0LL)return a;
    return gcd(b,a%b);
}
long long lcm(long long a,long long b){
    return a*b/gcd(a,b);
}
//

//
//struct edgeが必要

typedef struct{
    long long to,cost;
}edge;

class Tree {
private:
	const long long N;
	bool LCA_inited;
	vector<vector<edge>> G;
	vector<vector<long long>> parent;
	vector<long long> dist;
	vector<long long> distC;
	void dfs(long long v, long long p, long long d, long long d2);
	void D_dfs(long long v, long long p, long long d);
public:
	Tree(long long n);
	~Tree();
	long long max_dist;
	long long s, t;
	void LCAinit();
	vector<vector<edge>> Get_Graph();
	void add_edge(long long u, long long v, long long c);
	void diameter();
	long long lca(long long u, long long v);
	long long get_dist(long long u, long long v);
	bool on_path(long long u, long long v, long long a);
};

Tree::Tree(long long n):N(n) {
	G.resize(N);
	LCA_inited = false;
	s = -1, t = -1, max_dist = -1;
	return;
}
Tree::~Tree() {}
vector<vector<edge>> Tree::Get_Graph() {
	return G;
}
void Tree::add_edge(long long u, long long v,long long c) {
	G[v].push_back({ u,c });
	G[u].push_back({ v,c });
	return;
}
void Tree::LCAinit() {
    LCA_inited=true;
	parent.assign(33, vector<long long>(N, -1LL));
	dist.assign(N, -1LL);
	distC.assign(N, -1LL);
	dfs(0LL, -1LL, 0LL, 0LL);
	for (int i = 0; i < 32; i++) {
		for (int j = 0; j < N; j++) {
			if (parent[i][j] < 0LL) {
				parent[i + 1][j] = -1LL;
			}
			else {
				parent[i + 1][j] = parent[i][parent[i][j]];
			}
		}
	}
	return;
}
void Tree::diameter() {
	D_dfs(0, -1, 0);
	s = t;
	D_dfs(s, -1, 0);
	return;
}
void Tree::D_dfs(long long v, long long p, long long d) {
	if (max_dist < d) {
		max_dist = d;
		t = v;
	}
	for (const edge e : G[v]) {
		if (e.to == p)continue;
		D_dfs(e.to, v, d + e.cost);
	}
	return;
}
void Tree::dfs(long long v, long long p, long long d, long long d2) {
	parent[0][v] = p;
	dist[v] = d;
	distC[v] = d2;
	for (edge e : G[v]) {
		if (e.to == p)continue;
		dfs(e.to, v, d + 1, d2 + e.cost);
	}
	return;
}
long long Tree::lca(long long u, long long v) {
	if (!LCA_inited)LCAinit();
	if (dist[u] < dist[v])swap(u, v);
	long long between = dist[u] - dist[v];
	for (int i = 0; i < 33; i++) {
		if (between & (1LL << i)) { u = parent[i][u]; }
	}
	if (u == v)return u;
	for (int i = 32; i >= 0; i--) {
		if (parent[i][u] != parent[i][v]) {
			u = parent[i][u];
			v = parent[i][v];
		}
	}
	assert(parent[0][u] == parent[0][v]);
	return parent[0][u];
}
long long Tree::get_dist(long long u, long long v) {
	return distC[u] + distC[v] - 2 * distC[lca(u, v)];
}
bool Tree::on_path(long long u, long long v, long long a) {
	return get_dist(u, v) == get_dist(u, a) + get_dist(v, a);
}

//

int main(){
    /*
    文章を読み落としていませんか?
    制約も隅々まで読んでいますか?
    
    注意
    ・セグ木のupdate関数はl,rの値を渡したときにl以上r未満の区間だからご注意を
    　rは含みません
    ・BITって1-indexedなんだぜ
    　イケてるよな
    ・using namespace Warabi??
    */
    
    //using namespace Warabi;
    in(N);in(M);
    Warabi::UnionFind uf;
    uf.init(N);
    rep(i,0,M){
        in(u);in(v);u--;v--;
        if(uf.SZ(u)<uf.SZ(v)){
            uf.unite(u,v);
        }
        else if(uf.SZ(u)>uf.SZ(v)){
            uf.unite(v,u);
        }
        else{
            if(uf.root(v)<uf.root(u))swap(u,v);
            uf.unite(v,u);
        }
    }
    rep(i,0,N){
        out(uf.root(i)+1);
    }
}