#include <iostream>
#include <fstream>
#include <random>
#include <time.h>
#include <assert.h>
#include <set>
#include <queue>
#include <limits.h>
#include <unordered_set>
#include <algorithm>
using namespace std;
namespace author {
    struct edge {
        int ver;
        long long dist;
        const bool operator<(const edge &a) const {
            return dist>a.dist;
        }
    };

    long long dist[200000];
    int start[200000];
    int pref[200000];
    vector<edge> v[200000];
    // custom findportals
    int q1 = 0, q3 = 0;
    int find_portals(int l, int r)
    {
        q1++;
        return pref[r] - pref[l - 1];
    }
    void dnc(int l, int r, int br) {
        if(br==0) return;
        if(r-l+1==br) {
            //for(int i = l; i <= r; i++) p.push_back(i);
            return;
        }
        int mid = (l+r)>>1;
        int left = find_portals(l, mid);
        dnc(l, mid, left);
        dnc(mid+1, r, br-left);
    }
    void portals(int n, int k, vector<int> portals) {
        q1=0;
        for(int i = 0; i <= n; i++) pref[i]=0;
        for(auto x : portals) pref[x]++;
        for (int i = 1; i <= n; i++)
        {
            pref[i] += pref[i - 1];
        }
        vector<int> p;
        dnc(1, n, k);
        /*
        int curr = 1;
        for(int i = 1; i <= k; i++) {
            int l = curr, r = n, mid, ans=-1;
            while(l<=r) {
                mid=(l+r)/2;
                if(find_portals(curr, mid)>=1) {
                    ans=mid;
                    r = mid - 1;
                }
                else {
                    l = mid + 1;
                }
            }
            curr = ans + 1;
        }
        */
    }
    set<pair<int,int>> minimal_danger(int n, vector<pair<int, pair<int,int>>> paths, vector<int> portals, vector<int> fortresses) {
        for(int i = 1; i <= n; i++) v[i].clear();
        for(auto x : paths) {
            v[x.second.first].push_back({x.second.second, x.first});
            v[x.second.second].push_back({x.second.first, x.first});
        }
        for(int i = 1; i <= n; i++) {start[i]=0;dist[i]=4e18;}
        priority_queue<edge> q;
        for(auto x : portals) {
            q.push({x, 0});
            dist[x]=0;
            start[x]=x;
        }
        while(!q.empty()) {
            edge w = q.top();
            q.pop();
            for(auto x : v[w.ver]) {
                if(dist[x.ver]>dist[w.ver]+x.dist) {
                    dist[x.ver]=dist[w.ver]+x.dist;
                    start[x.ver]=start[w.ver];
                    x.dist=dist[x.ver];
                    q.push(x);
                }
            }
        }
        int mnFortress = fortresses[0];
        for(auto x : fortresses) {
            if(dist[x]<dist[mnFortress]) {
                mnFortress = x;
            }
        }
        set<pair<int,int>> anses;
        for(auto x : fortresses) {
            if(dist[x]==dist[mnFortress]) anses.insert({start[x], x});
        }
        return anses;
    }
    // custom throweye
    int x,y;
    string throw_eye(pair<int, int> coordinates)
    {
        q3++;
        int x2 = coordinates.first;
        int y2 = coordinates.second;
        if (x2 == x && y2 == y)
        {
            return "NONE";
        }
        if (x2 > x)
        {
            if (y2 > y)
            {
                return "SW";
            }
            if (y2 == y)
            {
                return "W";
            }
            if (y2 < y)
            {
                return "NW";
            }
        }
        if (x2 == x)
        {
            if (y2 > y)
            {
                return "S";
            }
            else
            {
                return "N";
            }
        }
        if (x2 < x)
        {
            if (y2 > y)
            {
                return "SE";
            }
            if (y2 == y)
            {
                return "E";
            }
            if (y2 < y)
            {
                return "NE";
            }
        }
    }
    void find_end_portal(int L, int x, int y) {
        q3=0;
        author::x=x;
        author::y=y;
        pair<int,int> tl={1,1}, br={L,L}, mid;
        while(tl.first<=br.first || tl.second<=br.second) {
            mid={(tl.first+br.first)/2, (tl.second+br.second)/2};
            string res = throw_eye(mid);
            if(res=="NONE") {
                break;
            }
            if(res=="NE" || res=="E" || res=="SE") {
                tl.first=mid.first+1;
            }
            else if(res=="NW" || res=="W" || res=="SW") {
                br.first=mid.first-1;
            }
            else {
                tl.first = mid.first;
                br.first = mid.first;
            }

            if(res=="NE"||res=="N"||res=="NW") {
                tl.second=mid.second+1;
            }
            else if(res=="SE"||res=="S"||res=="SW") {
                br.second=mid.second-1;
            }
            else {
                tl.second = mid.second;
                br.second = mid.second;
            }
        }
    }
};
// random spanning tree first, then random edges up to m, so the graph is always connected
vector<pair<int, pair<int,int>>> genEdges(int n, int m, int wmax, mt19937 &mt) {
    vector<pair<int, pair<int,int>>> v;
    for(int j = 2; j <= n; j++) {
        int p = 1+mt()%(j-1);
        v.push_back({(int)(1+mt()%wmax), {p, j}});
    }
    while((int)v.size() < m) {
        int a = 1+mt()%n, b = 1+mt()%n;
        v.push_back({(int)(1+mt()%wmax), {a, b}});
    }
    shuffle(v.begin(), v.end(), mt);
    return v;
}
int main() {
    srand(time(0));
    mt19937 mt(random_device{}());
    
    // one fortress
    for(int i = 1; i <= 5; i++) {
        cout << i << endl;
        ofstream in("minecraft." + (string)(i<10?"0":"") + to_string(i) + ".in");
        ofstream out("minecraft." + (string)(i<10?"0":"") + to_string(i) + ".out");
        int n=1+mt()%100000,k=1+mt()%min(1000, n/2);
        in << n << " " << k << endl;
        set<int> portals;
        set<int> s;
        for(int j = 0; j < k; j++) {
            int x = 1+mt()%n;
            while(s.count(x)) x = 1+mt()%n;
            s.insert(x);
            portals.insert(x);
            in << x << " ";
        }
        in << endl;
        int m = n+mt()%100000;
        in << m << endl;
        vector<pair<int, pair<int,int>>> v = genEdges(n, m, 1e9, mt);
        for(auto &e : v) in << e.second.first << " " << e.second.second << " " << e.first << endl;
        int f = 1;
        in << f << endl;
        vector<int> fortresses;
        for(int j = 0; j < f; j++) {
            int x = 1+mt()%n;
            while(portals.count(x)) x=1+mt()%n;
            fortresses.push_back(x);
            in << x << " ";
        }
        in << endl;
        int l = 1+mt()%(int)1e3;
        in << l << endl;
        int x=1+mt()%(l), y=1+mt()%(l);
        in << x << " " << y << endl;
        author::portals(n, k, vector<int>(portals.begin(), portals.end()));
        author::find_end_portal(l, x, y);
        in << author::q1 << " " << author::q3 << endl;
        auto ans = author::minimal_danger(n, v, vector<int>(portals.begin(), portals.end()), fortresses);
        for(auto &x : ans)out << x.first << " " << x.second << endl;
        in.close();
        out.close();
    }
    
    // k<=5
    for(int i = 6; i <= 10; i++) {
        cout << i << endl;
        ofstream in("minecraft." + (string)(i<10?"0":"") + to_string(i) + ".in");
        ofstream out("minecraft." + (string)(i<10?"0":"") + to_string(i) + ".out");
        int n=1+mt()%100000,k=1+mt()%min(5, n/2);
        in << n << " " << k << endl;
        set<int> portals;
        set<int> s;
        for(int j = 0; j < k; j++) {
            int x = 1+mt()%n;
            while(s.count(x)) x = 1+mt()%n;
            s.insert(x);
            portals.insert(x);
            in << x << " ";
        }
        in << endl;
        int m = n+mt()%100000;
        in << m << endl;
        vector<pair<int, pair<int,int>>> v = genEdges(n, m, 1e9, mt);
        for(auto &e : v) in << e.second.first << " " << e.second.second << " " << e.first << endl;
        int f = 1+mt()%n;
        in << f << endl;
        vector<int> fortresses;
        for(int j = 0; j < f; j++) {
            int x = 1+mt()%n;
            while(portals.count(x)) x=1+mt()%n;
            fortresses.push_back(x);
            in << x << " ";
        }
        in << endl;
        int l = 1+mt()%(int)1e3;
        in << l << endl;
        int x=1+mt()%(l), y=1+mt()%(l);
        in << x << " " << y << endl;
        author::portals(n, k, vector<int>(portals.begin(), portals.end()));
        author::find_end_portal(l, x, y);
        in << author::q1 << " " << author::q3 << endl;
        auto ans = author::minimal_danger(n, v, vector<int>(portals.begin(), portals.end()), fortresses);
        for(auto &x : ans)out << x.first << " " << x.second << endl;
        in.close();
        out.close();
    }

    for(int i = 11; i <= 20; i++) {
        cout << i << endl;
        ofstream in("minecraft." + (string)(i<10?"0":"") + to_string(i) + ".in");
        ofstream out("minecraft." + (string)(i<10?"0":"") + to_string(i) + ".out");
        int n=1+mt()%100,k=1+mt()%(n/2);
        in << n << " " << k << endl;
        set<int> portals;
        set<int> s;
        for(int j = 0; j < k; j++) {
            int x = 1+mt()%n;
            while(s.count(x)) x = 1+mt()%n;
            s.insert(x);
            portals.insert(x);
            in << x << " ";
        }
        in << endl;
        int m = n+mt()%100;
        in << m << endl;
        vector<pair<int, pair<int,int>>> v = genEdges(n, m, 1e5, mt);
        for(auto &e : v) in << e.second.first << " " << e.second.second << " " << e.first << endl;
        int f = 1+mt()%n;
        in << f << endl;
        vector<int> fortresses;
        for(int j = 0; j < f; j++) {
            int x = 1+mt()%n;
            while(portals.count(x)) x=1+mt()%n;
            fortresses.push_back(x);
            in << x << " ";
        }
        in << endl;
        int l = 1+mt()%(int)1e2;
        in << l << endl;
        int x=1+mt()%(l), y=1+mt()%(l);
        in << x << " " << y << endl;
        author::portals(n, k, vector<int>(portals.begin(), portals.end()));
        author::find_end_portal(l, x, y);
        in << author::q1 << " " << author::q3 << endl;
        auto ans = author::minimal_danger(n, v, vector<int>(portals.begin(), portals.end()), fortresses);
        for(auto &x : ans)out << x.first << " " << x.second << endl;
        in.close();
        out.close();
    }

    for(int i = 21; i <= 50; i++) {
        cout << i << endl;
        ofstream in("minecraft." + (string)(i<10?"0":"") + to_string(i) + ".in");
        ofstream out("minecraft." + (string)(i<10?"0":"") + to_string(i) + ".out");
        int n=1+mt()%100000,k=1+mt()%min(1000, n/2);
        in << n << " " << k << endl;
        set<int> portals;
        set<int> s;
        for(int j = 0; j < k; j++) {
            int x = 1+mt()%n;
            while(s.count(x)) x = 1+mt()%n;
            s.insert(x);
            portals.insert(x);
            in << x << " ";
        }
        in << endl;
        int m = n+mt()%100000;
        in << m << endl;
        vector<pair<int, pair<int,int>>> v = genEdges(n, m, 1e9, mt);
        for(auto &e : v) in << e.second.first << " " << e.second.second << " " << e.first << endl;
        int f = 1+mt()%n;
        in << f << endl;
        vector<int> fortresses;
        for(int j = 0; j < f; j++) {
            int x = 1+mt()%n;
            while(portals.count(x)) x=1+mt()%n;
            fortresses.push_back(x);
            in << x << " ";
        }
        in << endl;
        int l = 1+mt()%(int)1e3;
        in << l << endl;
        int x=1+mt()%(l), y=1+mt()%(l);
        in << x << " " << y << endl;
        author::portals(n, k, vector<int>(portals.begin(), portals.end()));
        author::find_end_portal(l, x, y);
        in << author::q1 << " " << author::q3 << endl;
        auto ans = author::minimal_danger(n, v, vector<int>(portals.begin(), portals.end()), fortresses);
        for(auto &x : ans)out << x.first << " " << x.second << endl;
        in.close();
        out.close();
    }
}