#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

struct Xor128 {
    unsigned x, y, z, w;
    Xor128() : x(123456789), y(362436069), z(521288629), w(88675123) {}
    unsigned next() {
        unsigned t = x ^ (x << 11);
        x = y; y = z; z = w;
        return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
    }
    //手iき
    inline unsigned next(unsigned n) { return next() % n; }
};

//bottom upなTreap
//脱再！
//randomized binary searchにするにはchoiceRandomlyを
//    bool choiceRandomly(Ref l, Ref r) { return rng.next(l->size + r->size) < l->size; }
//にきQえるだけでよい。
template<typename Node>
struct BottomupTreap {
    Xor128 rng;
    typedef Node *Ref;
    static int size(Ref t) { return !t ? 0 : t->size; }

    unsigned nextRand() { return rng.next(); }
private:
    bool choiceRandomly(Ref l, Ref r) {
        return l->priority < r->priority;
    }
public:

    Ref join(Ref l, Ref r) {
        if(!l) return r;
        if(!r) return l;

        Ref t = NULL;
        unsigned long long dirs = 0;
        int h;
        for(h = 0; ; ++ h) {
            if(h >= sizeof(dirs) * 8 - 2) {
                //dirsのオ`バ`フロ`を防ぐために再する。
                //あくまでセ`フティガ`ドなのでバランスは多少崩れるかもしれない
                t = join(l->right, r->left);
                dirs = dirs << 2 | 1;
                h ++;
                break;
            }
            dirs <<= 1;
            if(choiceRandomly(l, r)) {
                Ref c = l->right;
                if(!c) {
                    t = r;
                    r = r->parent;
                    break;
                }
                l = c;
            } else {
                dirs |= 1;
                Ref c = r->left;
                if(!c) {
                    t = l;
                    l = l->parent;
                    break;
                }
                r = c;
            }
        }
        for(; h >= 0; -- h) {
            if(!(dirs & 1)) {
                Ref p = l->parent;
                t = l->linkr(t);
                l = p;
            } else {
                Ref p = r->parent;
                t = r->linkl(t);
                r = p;
            }
            dirs >>= 1;
        }
        return t;
    }

    typedef std::pair<Ref, Ref> RefPair;

    //l＜tQrの(l,r)に分割する
    RefPair split2(Ref t) {
        Ref p, l = t->left, r = t;
        Node::cut(l); t->linkl(NULL);
        while(p = t->parent) {
            t->parent = NULL;
            if(p->left == t)
                r = p->linkl(r);
            else
                l = p->linkr(l);
            t = p;
        }
        return RefPair(l, r);
    }
    //l＜t＜rの(l,t,r)に分割する。(l,r)を返す
    RefPair split3(Ref t) {
        Ref p, l = t->left, r = t->right;
        Node::cut(l), Node::cut(r);
        t->linklr(NULL, NULL);
        while(p = t->parent) {
            t->parent = NULL;
            if(p->left == t)
                r = p->linkl(r);
            else
                l = p->linkr(l);
            t = p;
        }
        return RefPair(l, r);
    }
    Ref cons(Ref h, Ref t) {
        assert(size(h) == 1);
        if(!t) return h;
        Ref u = NULL;
        while(true) {
            if(choiceRandomly(h, t)) {
                Ref p = t->parent;
                u = h->linkr(t);
                t = p;
                break;
            }
            Ref l = t->left;
            if(!l) {
                u = h;
                break;
            }
            t = l;
        }
        while(t) {
            u = t->linkl(u);
            t = t->parent;
        }
        return u;
    }
};

//free treeのために、xを基本としてQう
class EulerTourTreeWithMarks {
    struct Node {
        typedef BottomupTreap<Node> BST;

        Node *left, *right, *parent;
        int size;
        unsigned priority;
        char marks, markUnions;    //0ビット目がedgeMark, 1ビット目がvertexMark

        Node() : left(NULL), right(NULL), parent(NULL),
            size(1), priority(0), marks(0), markUnions(0) {
        }

        inline Node *update() {
            int size_t = 1, markUnions_t = marks;
            if(left) {
                size_t += left->size;
                markUnions_t |= left->markUnions;
            }
            if(right) {
                size_t += right->size;
                markUnions_t |= right->markUnions;
            }
            size = size_t, markUnions = markUnions_t;
            return this;
        }

        inline Node *linkl(Node *c) {
            if(left = c) c->parent = this;
            return update();
        }
        inline Node *linkr(Node *c) {
            if(right = c) c->parent = this;
            return update();
        }
        inline Node *linklr(Node *l, Node *r) {
            if(left = l) l->parent = this;
            if(right = r) r->parent = this;
            return update();
        }
        static Node *cut(Node *t) {
            if(t) t->parent = NULL;
            return t;
        }

        static const Node *findRoot(const Node *t) {
            while(t->parent) t = t->parent;
            return t;
        }
        static std::pair<Node*, int> getPosition(Node *t) {
            int k = BST::size(t->left);
            Node *p;
            while(p = t->parent) {
                if(p->right == t)
                    k += BST::size(p->left) + 1;
                t = p;
            }
            return std::make_pair(t, k);
        }
        static const Node *findHead(const Node *t) {
            while(t->left) t = t->left;
            return t;
        }
        static void updatePath(Node *t) {
            while(t) {
                t->update();
                t = t->parent;
            }
        }
    };

    typedef Node::BST BST;
    BST bst;

    std::vector<Node> nodes;
    //各点にしてその点から出ているarcを1つだけ代表として持つ(oい龊悉-1)
    //逆にarcにして辘工腠点はたかだか1つである
    std::vector<int> firstArc;
    //x&#12539;点にする属性
    std::vector<bool> edgeMark, vertexMark;

    inline int getArcIndex(const Node *a) const { return a - &nodes[0]; }

    inline int arc1(int ei) const { return ei; }
    inline int arc2(int ei) const { return ei + (numVertices() - 1); }

public:
    inline int numVertices() const { return firstArc.size(); }
    inline int numEdges() const { return numVertices() - 1; }

    inline bool getEdgeMark(int a) const {
        return a < numEdges() ? edgeMark[a] : false;
    }
    inline bool getVertexMark(int v) const {
        return vertexMark[v];
    }
private:

    void updateMarks(int a, int v) {
        Node *t = &nodes[a];
        t->marks = getEdgeMark(a) << 0 | (v == -1 ? 0 : getVertexMark(v) << 1);
        Node::updatePath(t);
    }

    //firstArcの涓に辘袱聘新する
    void firstArcChanged(int v, int a, int b) {
        if(a != -1) updateMarks(a, -1);
        if(b != -1) updateMarks(b, v);
    }

public:
    class TreeRef {
        friend class EulerTourTreeWithMarks;
        const Node *ref;
    public:
        TreeRef() {}
        TreeRef(const Node *ref_) : ref(ref_) {}
        bool operator==(const TreeRef &that) const { return ref == that.ref; }
        bool operator!=(const TreeRef &that) const { return ref != that.ref; }
        bool isIsolatedVertex() const { return ref == NULL; }
    };

    void init(int N) {
        int M = N - 1;
        firstArc.assign(N, -1);
        nodes.assign(M * 2, Node());
        for(int i = 0; i < M * 2; i ++)
            nodes[i].priority = bst.nextRand();
        edgeMark.assign(M, false);
        vertexMark.assign(N, false);
    }

    TreeRef getTreeRef(int v) const {
        int a = firstArc[v];
        return TreeRef(a == -1 ? NULL : Node::findRoot(&nodes[a]));
    }

    bool isConnected(int v, int w) const {
        if(v == w) return true;
        int a = firstArc[v], b = firstArc[w];
        if(a == -1 || b == -1) return false;
        return Node::findRoot(&nodes[a]) == Node::findRoot(&nodes[b]);
    }

    int getTreeFirstArc(TreeRef t) const {
        assert(!t.isIsolatedVertex());
        return getArcIndex(t.ref);
    }

    static int getSize(TreeRef t) {
        if(t.isIsolatedVertex()) return 1;
        else return t.ref->size / 2 + 1;
    }

    void link(int ti, int v, int w) {
        int a1 = arc1(ti), a2 = arc2(ti);
        //v→wがa1に辘工毪瑜Δ摔工
        if(v > w) std::swap(a1, a2);

        int va = firstArc[v], wa = firstArc[w];

        Node *l, *m, *r;
        if(va != -1) {
            //evert。番を入れ替えるだけ
            std::pair<Node*, Node*> p = bst.split2(&nodes[va]);
            m = bst.join(p.second, p.first);
        } else {
            //vが孤立点の龊
            m = NULL;
            firstArc[v] = a1;
            firstArcChanged(v, -1, a1);
        }
        if(wa != -1) {
            std::pair<Node*, Node*> p = bst.split2(&nodes[wa]);
            l = p.first, r = p.second;
        } else {
            //wが孤立点の龊
            l = r = NULL;
            firstArc[w] = a2;
            firstArcChanged(w, -1, a2);
        }
        //w→vのxをmの先^＝lの末尾にinsert
        m = bst.cons(&nodes[a2], m);
        //v→wのxをmの末尾＝rの先^にinsert
        r = bst.cons(&nodes[a1], r);

        bst.join(bst.join(l, m), r);
    }

    void cut(int ti, int v, int w) {
        //v→wがa1に辘工毪瑜Δ摔工
        if(v > w) std::swap(v, w);

        int a1 = arc1(ti), a2 = arc2(ti);
        std::pair<Node*, Node*> p = bst.split3(&nodes[a1]);
        int prsize = BST::size(p.second);
        std::pair<Node*, Node*> q = bst.split3(&nodes[a2]);
        Node *l, *m, *r;
        //a1,a2の番を判定する。a1＜a2ならp.secondが浃铯盲皮い毪悉
        if(p.second == &nodes[a2] || BST::size(p.second) != prsize) {
            l = p.first, m = q.first, r = q.second;
        } else {
            //a2＜a1の番である。v→wのxがa1であってH→子であることにする
            std::swap(v, w);
            std::swap(a1, a2);
            l = q.first, m = q.second, r = p.second;
        }

        //firstArcを必要に辘袱きQえる
        if(firstArc[v] == a1) {
            int b;
            if(r != NULL) {
                //vが根じゃないなら右趣巫畛酩无xでよい
                b = getArcIndex(Node::findHead(r));
            } else {
                //vが根なら最初のxでよい。孤立点になるなら-1
                b = !l ? -1 : getArcIndex(Node::findHead(l));
            }
            firstArc[v] = b;
            firstArcChanged(v, a1, b);
        }
        if(firstArc[w] == a2) {
            //wが根になるので最初のxでよい。孤立点になるなら-1
            int b = !m ? -1 : getArcIndex(Node::findHead(m));
            firstArc[w] = b;
            firstArcChanged(w, a2, b);
        }

        bst.join(l, r);
    }

    void changeEdgeMark(int ti, bool b) {
        assert(ti < numEdges());
        edgeMark[ti] = b;
        Node *t = &nodes[ti];
        t->marks = (b << 0) | (t->marks & (1 << 1));
        Node::updatePath(t);
    }
    void changeVertexMark(int v, bool b) {
        vertexMark[v] = b;
        int a = firstArc[v];
        if(a != -1) {
            Node *t = &nodes[a];
            t->marks = (t->marks & (1 << 0)) | (b << 1);
            Node::updatePath(t);
        }
    }

    template<typename Callback>
    bool enumMarkedEdges(TreeRef tree, Callback callback) const {
        return enumMarks<0, Callback>(tree, callback);
    }
    //孤立点の龊悉虾簸趣扦饯雾点だけI理する必要がある
    template<typename Callback>
    bool enumMarkedVertices(TreeRef tree, Callback callback) const {
        return enumMarks<1, Callback>(tree, callback);
    }
private:
    //callback : TreeEdgeIndex×2 -> Bool
    //引数は点をそこからのincident arcで示し、"(正方向 ? 0 : N-1) + treeEdgeIndex"を表す。方向はv,wの大小でI理すればよい
    //callbackは@Aするかどうかをboolで返す。最後まで列い方Kえたかどうかを返す。
    template<int Mark, typename Callback>
    bool enumMarks(TreeRef tree, Callback callback) const {
        if(tree.isIsolatedVertex()) return true;
        const Node *t = tree.ref;
        if(t->markUnions >> Mark & 1)
            return enumMarksRec<Mark, Callback>(t, callback);
        else
            return true;
    }

    //平衡木なので深さは深くないので再して}ない
    template<int Mark, typename Callback>
    bool enumMarksRec(const Node *t, Callback callback) const {
        const Node *l = t->left, *r = t->right;
        if(l && (l->markUnions >> Mark & 1))
            if(!enumMarksRec<Mark, Callback>(l, callback)) return false;
        if(t->marks >> Mark & 1)
            if(!callback(getArcIndex(t))) return false;
        if(r && (r->markUnions >> Mark & 1))
            if(!enumMarksRec<Mark, Callback>(r, callback)) return false;
        return true;
    }

public:
    //デバッグ用
    void debugEnumEdges(std::vector<int> &out_v) const {
        int M = numEdges();
        for(int ti = 0; ti < M; ti ++) {
            const Node *t = &nodes[ti];
            if(t->left || t->right || t->parent)
                out_v.push_back(ti);
        }
    }
};

//treeEdgeにはそれぞれ0～N-1のインデックスが与えられる。これは全てのレベルで共通。
//ところで"level up"って和u英Zなんだ。promoteでいいかな。
//Sampling heuristic ランダムケ`スで超速く(4倍とか)なったんだけど！いいね！
class HolmDeLichtenbergThorup {
    typedef HolmDeLichtenbergThorup This;
    typedef EulerTourTreeWithMarks Forest;
    typedef Forest::TreeRef TreeRef;

    int numVertices_m;
    int numSamplings;

    //DynamicTreeはコピ`できないけどまあその状Bで使わなきゃいいじゃんということで…
    std::vector<Forest> forests;

    std::vector<char> edgeLevel;
    std::vector<int> treeEdgeIndex;    // : EdgeIndex -> TreeEdgeIndex
    std::vector<int> treeEdgeMap;    // : TreeEdgeIndex -> EdgeIndex
    std::vector<int> treeEdgeIndexFreeList;    // : [TreeEdgeIndex]

                                            //arcも方向はEulerTourTreeと同じようにv,wの大小に合わせる
    std::vector<int> arcHead;

    std::vector<std::vector<int> > firstIncidentArc;
    std::vector<int> nextIncidentArc, prevIncidentArc;

    //一r的に使う。使い回して使う
    std::vector<bool> edgeVisited;
    std::vector<int> visitedEdges;    // : [EdgeIndex | TreeEdgeIndex]

    int arc1(int ei) const { return ei; }
    int arc2(int ei) const { return numMaxEdges() + ei; }
    int arcEdge(int i) const { return i >= numMaxEdges() ? i - numMaxEdges() : i; }

    bool replace(int lv, int v, int w) {
        Forest &forest = forests[lv];

        TreeRef vRoot = forest.getTreeRef(v), wRoot = forest.getTreeRef(w);
        assert(vRoot.isIsolatedVertex() || wRoot.isIsolatedVertex() || vRoot != wRoot);

        int vSize = forest.getSize(vRoot), wSize = forest.getSize(wRoot);

        int u; TreeRef uRoot; int uSize;
        if(vSize <= wSize)
            u = v, uRoot = vRoot, uSize = vSize;
        else
            u = w, uRoot = wRoot, uSize = wSize;

        //replacement edgeを探す
        int replacementEdge = -1;
        enumIncidentArcs(forest, uRoot, u, lv, FindReplacementEdge(uRoot, &replacementEdge));

        //"Sampling heuristic"
        //早いr点でつかったならT_u,他のincident arcsをレベルアップさせなくても算量的に}ない
        if(replacementEdge != -1 && (int)visitedEdges.size() + 1 <= numSamplings) {
            //replacementEdgeをI理する
            deleteNontreeEdge(replacementEdge);
            addTreeEdge(replacementEdge);
            for(int i = 0; i < (int)visitedEdges.size(); i ++)
                edgeVisited[visitedEdges[i]] = false;
            visitedEdges.clear();
            return true;
        }

        //つけたincident arcsを一扭衰欹佶毳ップさせる。edgeVisitedの後I理もする
        for(int i = 0; i < (int)visitedEdges.size(); i ++) {
            int ei = visitedEdges[i];
            edgeVisited[ei] = false;

            deleteNontreeEdge(ei);

            ++ edgeLevel[ei];

            insertNontreeEdge(ei);
        }
        visitedEdges.clear();

        //このレベルのT_uのxを列い工
        forest.enumMarkedEdges(uRoot, EnumLevelTreeEdges(this));
        //列い筏T_uのxを一扭衰欹佶毳ップさせる
        for(int i = 0; i < (int)visitedEdges.size(); i ++) {
            int ti = visitedEdges[i];

            int ei = treeEdgeMap[ti];
            int v = arcHead[arc2(ei)], w = arcHead[arc1(ei)];
            int lv = edgeLevel[ei];

            edgeLevel[ei] = lv + 1;

            forests[lv].changeEdgeMark(ti, false);
            forests[lv + 1].changeEdgeMark(ti, true);

            forests[lv + 1].link(ti, v, w);
        }
        visitedEdges.clear();

        if(replacementEdge != -1) {
            //T_uのx列い吻挨造が浃铯毪壤Г毪韦replacementEdgeはこのタイミングでI理する
            deleteNontreeEdge(replacementEdge);
            addTreeEdge(replacementEdge);
            return true;
        } else if(lv > 0) {
            return replace(lv - 1, v, w);
        } else {
            return false;
        }
    }

    struct EnumLevelTreeEdges {
        This *thisp;
        EnumLevelTreeEdges(This *thisp_) : thisp(thisp_) {}

        inline bool operator()(int a) {
            thisp->enumLevelTreeEdges(a);
            return true;
        }
    };
    void enumLevelTreeEdges(int ti) {
        visitedEdges.push_back(ti);
    }

    //孤立点のr特eなI理をするなどしなければいけないのでヘルパ`
    template<typename Callback>
    bool enumIncidentArcs(Forest &forest, TreeRef t, int u, int lv, Callback callback) {
        if(t.isIsolatedVertex())
            return enumIncidentArcsWithVertex<Callback>(lv, u, callback);
        else
            return forest.enumMarkedVertices(t, EnumIncidentArcs<Callback>(this, lv, callback));
    }

    template<typename Callback>
    struct EnumIncidentArcs {
        This *thisp;
        int lv;
        Callback callback;

        EnumIncidentArcs(This *thisp_, int lv_, Callback callback_) :
            thisp(thisp_), lv(lv_), callback(callback_) {
        }

        inline bool operator()(int tii) const {
            return thisp->enumIncidentArcsWithTreeArc(tii, lv, callback);
        }
    };

    template<typename Callback>
    bool enumIncidentArcsWithTreeArc(int tii, int lv, Callback callback) {
        int u = getTreeEdgeIndexTailVertex(tii);
        assert(firstIncidentArc[lv][u] != -1);
        return enumIncidentArcsWithVertex(lv, u, callback);
    }

    int getTreeEdgeIndexTailVertex(int tii) const {
        bool dir = tii >= numVertices() - 1;
        int ti = dir ? tii - (numVertices() - 1) : tii;
        int ei = treeEdgeMap[ti];
        int v = arcHead[arc2(ei)], w = arcHead[arc1(ei)];
        //方向を求め、そのarcのtailの点を取得する
        int u = !(dir != (v > w)) ? v : w;
        return u;
    }

    //1つの点をI理する
    template<typename Callback>
    bool enumIncidentArcsWithVertex(int lv, int u, Callback callback) {
        int it = firstIncidentArc[lv][u];
        while(it != -1) {
            if(!callback(this, it))
                return false;
            it = nextIncidentArc[it];
        }
        return true;
    }

    struct FindReplacementEdge {
        TreeRef uRoot;
        int *replacementEdge;
        FindReplacementEdge(TreeRef uRoot_, int *replacementEdge_) :
            uRoot(uRoot_), replacementEdge(replacementEdge_) {
        }

        inline bool operator()(This *thisp, int a) const {
            return thisp->findReplacementEdge(a, uRoot, replacementEdge);
        }
    };

    //1つのarcをI理する
    bool findReplacementEdge(int a, TreeRef uRoot, int *replacementEdge) {
        int ei = arcEdge(a);
        if(edgeVisited[ei]) return true;

        int lv = edgeLevel[ei];
        TreeRef hRoot = forests[lv].getTreeRef(arcHead[a]);

        if(hRoot.isIsolatedVertex() || hRoot != uRoot) {
            //eの木に渡されているならreplacement edgeである。
            *replacementEdge = ei;
            return false;
        }
        //replacement edgeはvisitedEdgesに入れたくないのでこの位置でマ`クする
        edgeVisited[ei] = true;
        visitedEdges.push_back(ei);
        return true;
    }

    void addTreeEdge(int ei) {
        int v = arcHead[arc2(ei)], w = arcHead[arc1(ei)];
        int lv = edgeLevel[ei];

        int ti = treeEdgeIndexFreeList.back();
        treeEdgeIndexFreeList.pop_back();
        treeEdgeIndex[ei] = ti;
        treeEdgeMap[ti] = ei;

        forests[lv].changeEdgeMark(ti, true);

        for(int i = 0; i <= lv; i ++)
            forests[i].link(ti, v, w);
    }

    void insertIncidentArc(int a, int v) {
        int ei = arcEdge(a);
        int lv = edgeLevel[ei];
        assert(treeEdgeIndex[ei] == -1);

        int next = firstIncidentArc[lv][v];
        firstIncidentArc[lv][v] = a;
        nextIncidentArc[a] = next;
        prevIncidentArc[a] = -1;
        if(next != -1) prevIncidentArc[next] = a;

        if(next == -1)
            forests[lv].changeVertexMark(v, true);
    }

    void deleteIncidentArc(int a, int v) {
        int ei = arcEdge(a);
        int lv = edgeLevel[ei];
        assert(treeEdgeIndex[ei] == -1);

        int next = nextIncidentArc[a], prev = prevIncidentArc[a];
        nextIncidentArc[a] = prevIncidentArc[a] = -2;

        if(next != -1) prevIncidentArc[next] = prev;
        if(prev != -1) nextIncidentArc[prev] = next;
        else firstIncidentArc[lv][v] = next;

        if(next == -1 && prev == -1)
            forests[lv].changeVertexMark(v, false);
    }

    void insertNontreeEdge(int ei) {
        int a1 = arc1(ei), a2 = arc2(ei);
        insertIncidentArc(a1, arcHead[a2]);
        insertIncidentArc(a2, arcHead[a1]);
    }

    void deleteNontreeEdge(int ei) {
        int a1 = arc1(ei), a2 = arc2(ei);
        deleteIncidentArc(a1, arcHead[a2]);
        deleteIncidentArc(a2, arcHead[a1]);
    }

public:
    HolmDeLichtenbergThorup() : numVertices_m(0), numSamplings(0) {}

    int numVertices() const { return numVertices_m; }
    int numMaxEdges() const { return edgeLevel.size(); }

    void init(int N, int M) {
        numVertices_m = N;

        int levels = 1;
        while(1 << levels <= N / 2) levels ++;

        //サンプリング数をO定する。m切なはよくわからない
        numSamplings = (int)(levels * 1);

        forests.resize(levels);
        for(int lv = 0; lv < levels; lv ++)
            forests[lv].init(N);

        edgeLevel.assign(M, -1);

        treeEdgeIndex.assign(M, -1);
        treeEdgeMap.assign(N - 1, -1);

        treeEdgeIndexFreeList.resize(N - 1);
        for(int ti = 0; ti < N - 1; ti ++)
            treeEdgeIndexFreeList[ti] = ti;

        arcHead.assign(M * 2, -1);

        firstIncidentArc.resize(levels);
        for(int lv = 0; lv < levels; lv ++)
            firstIncidentArc[lv].assign(N, -1);
        nextIncidentArc.assign(M * 2, -2);
        prevIncidentArc.assign(M * 2, -2);

        edgeVisited.assign(M, false);
    }

    bool insertEdge(int ei, int v, int w) {
        assert(0 <= ei && ei < numMaxEdges() && 0 <= v && v < numVertices() && 0 <= w && w < numVertices());
        assert(edgeLevel[ei] == -1);

        int a1 = arc1(ei), a2 = arc2(ei);
        arcHead[a1] = w, arcHead[a2] = v;

        bool treeEdge = !forests[0].isConnected(v, w);

        edgeLevel[ei] = 0;
        if(treeEdge) {
            addTreeEdge(ei);
        } else {
            treeEdgeIndex[ei] = -1;
            //ル`プはたくないのでリストにも入れない
            if(v != w)
                insertNontreeEdge(ei);
        }

        return treeEdge;
    }

    bool deleteEdge(int ei) {
        assert(0 <= ei && ei < numMaxEdges() && edgeLevel[ei] != -1);

        int a1 = arc1(ei), a2 = arc2(ei);
        int v = arcHead[a2], w = arcHead[a1];

        int lv = edgeLevel[ei];
        int ti = treeEdgeIndex[ei];

        bool splitted = false;
        if(ti != -1) {
            treeEdgeMap[ti] = -1;
            treeEdgeIndex[ei] = -1;
            treeEdgeIndexFreeList.push_back(ti);

            for(int i = 0; i <= lv; i ++)
                forests[i].cut(ti, v, w);

            forests[lv].changeEdgeMark(ti, false);

            splitted = !replace(lv, v, w);
        } else {
            //ル`プはリストに入ってない
            if(v != w)
                deleteNontreeEdge(ei);
        }

        arcHead[a1] = arcHead[a2] = -1;
        edgeLevel[ei] = -1;

        return splitted;
    }

    bool isConnected(int v, int w) const {
        return forests[0].isConnected(v, w);
    }

    int findComponentRepresent(int v) const {
        assert(0 <= v && v < numVertices());
        TreeRef t = forests[0].getTreeRef(v);
        if(t.isIsolatedVertex()) {
            return v;
        } else {
            int tii = forests[0].getTreeFirstArc(t);
            return getTreeEdgeIndexTailVertex(tii);
        }
    }
    int getComponentSize(int v) const {
        assert(0 <= v && v < numVertices());
        TreeRef t = forests[0].getTreeRef(v);
        if(t.isIsolatedVertex()) return 1;
        else return forests[0].getSize(t);
    }

    //デバッグ用
    void dbgForestO(std::ostream &o) const {
        int N = numVertices(), M = numMaxEdges();
        int levels = forests.size();
        std::vector<bool> visited(M, false);
        o << "graph {\n";
        for(int lv = 0; lv < levels; lv ++) {
            o << "subgraph cluster_" << lv << "{\n";
            o << "label = " << '"' << "level " << lv << '"' << ";\n";
            for(int u = 0; u < N; u ++) {
                o << '"' << lv << "_" << u << '"';
                o << "[label=" << u << "];\n";

                int it = firstIncidentArc[lv][u];
                while(it != -1) {
                    int ei = arcEdge(it);
                    if(!visited[ei]) {
                        visited[ei] = true;
                        int v = arcHead[arc2(ei)], w = arcHead[arc1(ei)];
                        o << '"' << lv << "_" << v << '"' << " -- " << '"' << lv << "_" << w << '"';
                        o << " [style=dotted]" << ";\n";
                    }
                    it = nextIncidentArc[it];
                }
            }
            std::vector<int> edges;
            forests[lv].debugEnumEdges(edges);
            for(int i = 0; i < (int)edges.size(); i ++) {
                int ti = edges[i];
                int ei = treeEdgeMap[ti];
                assert(ei != -1);
                int lvi = edgeLevel[ei];
                int a1 = arc1(ei), a2 = arc2(ei);
                int v = arcHead[a2], w = arcHead[a1];
                o << '"' << lv << "_" << v << '"' << " -- " << '"' << lv << "_" << w << '"';
                //                o << " [style=" << (lvi == lv ? "solid" : "dashed") << "]";
                o << ";\n";
            }
            o << "}\n";
        }
        o << "}" << std::endl;
    }

    void dbgForest() const { dbgForestO(std::cerr); }
};


int main() {
    HolmDeLichtenbergThorup dynaCon;
    int T;
    scanf("%d", &T);
    for(int ii = 0; ii < T; ++ ii) {
        int N; int M;
        scanf("%d%d", &N, &M);
        vector<pair<int, pii> > edges(M);
        rep(i, M) {
            int a; int b; int c;
            scanf("%d%d%d", &a, &b, &c), -- a, -- b;
            edges[i] = mp(c, mp(a, b));
        }
        sort(all(edges));
        dynaCon.init(N, M);
        int ccs = N;
        int ans = numeric_limits<int>::max();
        for(int i = 0, j = 0; i < M; ++ i) {
            for(; j < M && ccs > 1; ++ j)
                ccs -= dynaCon.insertEdge(j, edges[j].second.first, edges[j].second.second);
            if(ccs == 1)
                amin(ans, edges[j - 1].first - edges[i].first);
            ccs += dynaCon.deleteEdge(i);
        }
        if(ans == numeric_limits<int>::max())
            puts("-1");
        else
            printf("%d\n", ans);
    }
    return 0;
}